Electrical computers and digital data processing systems: input/ – Access arbitrating
Reexamination Certificate
1999-05-17
2002-09-10
Lefkowitz, Sumati (Department: 2181)
Electrical computers and digital data processing systems: input/
Access arbitrating
C711S147000
Reexamination Certificate
active
06449673
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This application relates in general to a memory controller for a multiprocessor computer system, and in specific to a mechanism for maximizing available bandwidth on the address bus by utilizing and “snapshot” matrix to reduce “retries” of conflicting memory data requests.
BACKGROUND OF THE INVENTION
The different processors of the multiprocessor network typically share access with a common memory, such as a shared RAM memory, that pulls a cache line of data and sends it to a processor, which then puts the line into its cache. Requests for access to the shared memory from the given processors are routed through a memory controller. This prevents concurrent accesses to the same data, and as such, a requesting processor will receive current data and not stale data from memory. The memory controller receives a read request from one of the processors. The memory controller then reads the data from the memory. The memory controller then formats a response to the request that includes the data, and then sends the response back to the requesting processor.
In doing so, the memory controller has to make sure that it has not violated coherency issues which might occur incases where, in a first instance, there is a read to a cache line and later there is another read to the same cache line from a different processor before the data for the first read was returned by the memory controller. In such situations, the memory controller has to make sure that in processing the second read it does not violate coherency by sending the old data which it has in the memory to the second read. The data that the controller returns for the first read could be modified by the processor which got the first read response. Instead, with respect to the second read, the memory controller needs to make sure that the data for the second read is from the processor that originated the first read. This problem has been solved by performing a retry operation. Accordingly, the memory controller will issue a “retry signal,” which essentially tells the microprocessor which is sending the second read request to retry the read request at a later time. Consequently, the effect of the memory controller not being ready to return the response for the data and the subsequent retry operations, is that more of the system bus bandwidth is used. Thus, the prior art retry operations does lower the system performance, because the operations will generate unnecessary transactions on the system bus.
Furthermore, prior art memory controllers are designed to process requests in order, thus the memory controllers would return a response with the requested data in the same order that the requests for data are received. Some memory controllers also issue read requests to memory in the same order as the corresponding requests are received by the memory controller. Hence, the returns from the memory are also in the same order, causing the request transactions to be always completed in the order in which they were received. The next transaction that will be available to be returned to a processor is clearly known, since the memory controller operates according to the received order of the requests. Consequently, the memory controller can perform preparation operations in anticipation of returning the data from memory. However, the order requirements of the prior art controllers have several limitations. Servicing the requests in order requires a large amount of queue space. Data received by the memory controller from the memory must be held until the request associated with the data is sequentially the current request. Thus, the data from memory must be queued. This also causes a back log of requests, as requests cannot be satisfied until their associated data is returned. As a further consequence, the prior art controllers experience long latencies, because of the queuing of the requests and the data. Also, since the requests must be processed in a particular order, the requests cannot be re-ordered by the controller to maximize bus utilization and throughput. Thus, if address
1
is followed by address
2
and then address
3
, the data supplied must be in phase accordingly (i.e. data
1
, data
2
, data
3
, etc.) As such, the hardware of the system is inefficiently used.
Therefore, there is a need in the art for a memory controller that more efficiently uses queue spaces by permitting out of order returns and avoids the bandwidth intensive “retry” scheme so as to optimize use of the memory bus. The hardware design should be simple and efficient, so that high frequency operation is possible. The design should be simple to understand, so that it is easy to verify.
SUMMARY OF THE INVENTION
These and other objects, features and technical advantages are achieved by a system and method that permits the aforementioned inefficiencies to be ameliorated by maximizing the available bandwidth through a mechanism which uses a “snapshot” matrix.
The invention is a memory controller that is connected between at least one bus and a memory, with the bus connected to at least two processors. Note the inventive memory controller can operate with a single processor, however, the advantages of the invention are realized when the bus has at least two processors. The inventive memory controller manages read requests from the processors. The memory controller fetches the data from memory and checks to see if another processor has ownership of the requested data. If so, the owning processor will respond to the requesting processor. The invention, after receiving a read request, examines on-chip resources to determine whether prior requests are pending that involve the same memory resources as the received read request, e.g a cache line of memory in RAM. The invention uses a snapshot matrix to track received transactions conflicting with the prior pending transactions. Each received transaction is assigned a unique identification, based on a maximum number of transactions the invention can manage at a certain time. The prior pending transactions are reviewed in order to determine whether any conflicts exist with the received transaction. In the event of a conflict, the received transaction is entered into a snapshot matrix. All prior conflicting transactions must be processed before data is returned for the received transaction. Note that multiple read requests may be processed out of order to maximize the memory bus utilization and throughput. Note that the completed transaction may be returned in an order that is different from the read request order. Since transactions are processed out of order, data return latency is reduced. The snapshot matrix imposes strict ordering between conflicting transactions.
Therefore, it is a technical advantage of the present invention to have a memory controller provides coherency between data requests and data returns for read request transactions, and thereby improve system performance.
It is another technical advantage of the present invention that requests can originate from multiple processors located on multiple buses.
It is a further technical advantage of the present invention that the memory controller may be implemented in hardware such that the invention can operate at high frequencies and the logic can be easily verified.
It is a still further technical advantage of the present invention that the memory controller can maximize available bandwidth on the address bus.
It is a still further technical advantage of the present invention to use a bitmap to record pending transactions such that after a pending transaction has been completed, a clear signal will be generated to clear all future transactions that are waiting for the now completed transaction to finish.
The present invention avoids retrying requests that are conflicting with already pending requests. Pending requests are requests for which the memory data has not yet been returned. If a conflicting request is retried, the request will be reissued by the processor. This wastes precious system bus address bandwidth.
Every tra
Hewlett--Packard Company
Lefkowitz Sumati
LandOfFree
Snapshot and recall based mechanism to handle read after... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Snapshot and recall based mechanism to handle read after..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Snapshot and recall based mechanism to handle read after... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2895014