Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-03-31
2003-08-05
Jung, David (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06604116
ABSTRACT:
BACKGROUND OF THE INVENTION
The different processors of the multiprocessor system typically share access with a common memory. Requests for access to the memory from the processors are routed through a memory controller. The memory controller receives a read request from one of the processors. The memory controller then reads 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.
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 the returning 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, the hardware of the system is inefficiently used.
Therefore, there is a need in the art for a memory controller that does not require large amounts of queue space, has reduced request latencies, and can efficiently use the memory bus.
SUMMARY OF THE INVENTION
These and other objects, features and technical advantages are achieved by a system and method that reduces the latency of memory data returns. The invention examines on chip resources to determine whether completed transactions exist, and if not, to predict which partially completed transaction is most likely to become completed next. The invention returns the data for completed transactions and sets up the data return for the partially completed transaction that is most likely to become completed next. 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. Also note that the partially completed transaction selected for set up may correspond to a later read request than other pending partially completed transactions. Since transactions are processed out of order, data return latency is reduced.
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 memory controller includes a storage queue for maintaining information about the pending requests until associated responses have been sent out. A state machine of the memory controller reviews the queue to determine whether any transactions have completed all of their phases. If not, the state machine will determine which of the partially completed transactions is most likely to complete all of its phases, and then will set up this transaction for return. If a different transaction is completed after a partially completed transaction has been set up, the memory controller will cancel the set up, and process the completed transaction. This prevents a deadlock situation from occurring.
The invention can operate with a system having more than one bus, with each bus comprising at least two processors. Thus, when the memory controller checks to see if another processor on the local bus has ownership of the requested data, the memory controller also performs a check on each remote bus. Note that the local bus is the bus that includes the requesting processor, and the remote buses are the remaining buses of the system. Thus, data for a particular transaction in a multiple bus system cannot be returned until both the local and remote checks are completed. The state machine would use a remote queue to track the phases of transaction on remote buses.
The inventive memory controller will batch process completed transactions to avoid forward progress issues. The memory controller uses two sub-queues, i.e. the inside queue and the outside queue, of the storage queue to hold groups of completed transactions. When the inside queue is empty, the contents of outside queue are loaded into the inside queue. The transaction in the inside queue are processed until the inside queue is empty. Any transaction that completed their phase during the processing of the inside queue are loaded into the outside queue. When the inside queue is empty again, the contents of the outside queue is loaded into the inside queue for processing, and the operations begin again. This prevents a completed transaction from being overlooked, in favor of other completed transaction for an extended period of time. Thus, forward progress issues are avoided.
Therefore, it is a technical advantage of the present invention to have a memory controller that reduces the latency in 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.
It is a still further technical advantage of the present invention that the memory controller can operate without incurring deadlocks and without forward progress issues.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention. It should be appreciated by those skilled in the art that the conception and specific embodiment disclosed may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims.
REFERENCES:
patent: 4755930 (1988-07-01), Wilson, Jr. et al.
patent: 6341288 (2002-01-01), Yach et al.
patent: 6351753 (2002-02-01), Jagadish et al.
patent: 6353877 (2002-03-01), Duncan et al.
Huang et., “A neural-fuzzy classifier for recognition of power quality disturbances”, Power Delivery, IEEE Transactions on, vol. 17, Issue 2, Apr. 2002, pp. 609-616.*
Meijster et al., “A comparison of algorithms for connected set openings and closings”, Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 24, Issue 4, Apr. 2002, pp. 484-494.*
Pendse et al., “Uprating of a sing
Hewlett--Packard Development Company, L.P.
Jung David
LandOfFree
Decreasing memory return latency by predicting the order of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Decreasing memory return latency by predicting the order of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decreasing memory return latency by predicting the order of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3093804