Electrical computers and digital processing systems: memory – Storage accessing and control – Access timing
Reexamination Certificate
1997-09-18
2001-03-13
Chan, Eddie P. (Department: 2751)
Electrical computers and digital processing systems: memory
Storage accessing and control
Access timing
C711S150000, C711S151000, C711S147000, C710S240000, C710S244000, C710S241000
Reexamination Certificate
active
06202137
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to memory arbitration schemes, and more particularly to a method and apparatus of arbitrating requests to a memory having more than one bank.
In response to consumer demand for high performance computer systems, manufacturers are developing computer systems that utilize multiple processors, instead of a single processor. The theory behind multi-processor systems is that if a one processor system provides a certain level of performance, then a two processor system could provide twice the performance of the one processor system, and a three processor system could provide three times the performance of the one processor system, etc. While in theory this may be true, the reality is that, due to various limiting factors, each additional processor that is added to a computer system only increases the performance by a fraction. As a result, a particular two processor system may only provide 1.5 times the performance of a one processor system.
One such performance limiting factor is that, these multi-processor systems typically have a common or shared memory resource in which the processors store and retrieve instructions and data. In these systems, the processors typically access the shared memory by issuing, upon a processor bus, memory requests to a memory controller. The memory controller decodes the request and then satisfies the request by controlling the transfer of information (instructions or data) between the processor and the shared memory in accordance with the type of request. However, since these multi-processor systems are typically designed such that only a single request may access the shared memory at a given time, an arbitration scheme must be implemented which grants a single request access to the shared memory.
Since these processors do not have exclusive use of the memory, at times a first processor must wait for a second processor's request to complete before the first processor's request can be satisfied. This performance limiting factor of waiting for another processor's request to complete is even further aggravated by the fact that due to physical characteristics of the shared memory certain memory accesses take longer than others. Since in the typical case, a memory controller has more than one memory request from which to select a request to process, a memory controller, which makes an informed decision as to which memory request to select, can increase the performance of the multi-processor system by reducing the amount of time that the processors, as a whole, are waiting for requests.
What is needed therefore, is a method and apparatus of arbitrating requests to a multi-banked memory which increases the performance of a computer system by reducing the amount of time that the processors, as a whole, wait for memory requests to be completed.
SUMMARY OF THE INVENTION
In accordance with one embodiment of the present invention, there is provided a method of arbitrating requests to a memory having multiple banks. The method includes the steps of (a) processing a present request to access the memory; (b) receiving a first request to access the memory and a second request to access the memory; (c) selecting from the first request and the second request, a next request to access the memory; and (d) processing the next request to access the memory. The present request includes a present bank select that maps the present request to one of the banks, the first request includes a first bank select that maps the first request to one of the banks, and the second request includes a second bank select that maps the second request to one of the banks. Furthermore, the selecting step of the method is dependent upon the present bank select, the first bank select, and the second bank select.
Pursuant to another embodiment of the present invention, there is provided a memory controller for arbitrating requests to access a memory having a number of banks. The memory controller includes a first queue, a second queue, a present bank store, and an arbiter. The first queue has at least one storage element configured to store a first request to access said memory. The first request includes a first bank select that maps said first request to one of the banks. The second queue has at least one storage element configured to store a second request to access said memory. The second request includes a second bank select that maps the second request to one of the banks. The present bank store has at least one storage element configured to store a present bank select of a present bank request that has been granted access to the memory. The present bank select maps the present request to one of the banks. The arbiter is coupled to the first queue, the second queue, and the present bank store. The arbiter grants access to the memory to a next request that is selected from the first request and the second request depending upon the first bank select, the second bank select, and the present bank select.
Pursuant to yet another embodiment of the invention, there is provided a computer system. The computer system includes a memory, a memory controller, a first group of processors, and second group of processors. The memory includes a number of banks that are identified by a number of bank identifiers wherein each bank has a separate bank identifier. The memory controller is coupled to the memory and includes a first port, a second port, and an arbiter. The first group of processors include at least one processor and each processor of the first group of processors is coupled to the first port of the memory controller via a first bus. The second group of processors includes at least one processor and each processor of the second group of processors is coupled to the second port of the memory controller via a second bus. Furthermore, the arbiter grants access to the memory to a next request that is selected from a first request received from the first group of processors and a second request received from the second group of processors. The arbiter selects the next request dependent upon (1) a first bank select of the first request, (2) a second bank select of the second request, and (3) a present bank select of a present request that has been granted access to the memory. The first bank select corresponds to one of the bank identifiers, the second bank select corresponds to one of the bank identifiers, and the present bank select corresponds to one of the bank identifiers.
It is an object of the present invention to provide an improved method and apparatus for arbitrating memory requests.
It is a further object of the present invention to provide a method and apparatus for arbitrating requests which increases system performance by reducing the overall time the system spends on waiting for requests to memory to be processed.
It is yet another object of the present invention to provide a method and apparatus for arbitrating requests which are effective in a computer system having only a few requesting agents.
It is also an object of the present invention to provide a method and apparatus for arbitrating requests which are effective in a computer system having many requesting agents.
REFERENCES:
patent: 4796232 (1989-01-01), House
patent: 5220653 (1993-06-01), Miro
patent: 5398211 (1995-03-01), Willenz et al.
patent: 5412788 (1995-05-01), Collins et al.
patent: 5426765 (1995-06-01), Stevens et al.
patent: 5440713 (1995-08-01), Lin
patent: 5509136 (1996-04-01), Korekata et al.
patent: 5530838 (1996-06-01), Hisano
patent: 5555382 (1996-09-01), Thaller et al.
patent: 5784582 (1998-07-01), Hughes
patent: 5832304 (1998-11-01), Bauman et al.
Chan Eddie P.
Intel Corporation
McLean Kimberly
Werner Ray
LandOfFree
Method and apparatus of arbitrating requests to a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus of arbitrating requests to a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus of arbitrating requests to a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2449857