Arbitration and select logic for accessing a shared memory

Details Arbitration and select logic for accessing a shared memory Arbitration and select logic for accessing a shared memory

2001-05-31

2003-09-23

Elmore, Reba I. (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Shared memory area

C711S158000, C711S163000

Reexamination Certificate

active

06625700

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention pertains to managing of shared resources in a computing environment, and, more particularly, to techniques for arbitrating and selecting one access request to a shared memory from among multiple contenders.
2. Description of the Related Art
The evolution of electronic computing systems included the development of more sophisticated techniques for utilizing their computing resources. Consider, for example, a shared memory. A shared memory may be read from and written to by more than one device, e.g., several processors. The devices perform their assigned functions, reading from and writing to the shared memory. The devices request access to the shared memory through a memory controller that controls the operation of the shared memory. Typically, several devices are trying to access the shared memory in this fashion at any given time. However, for a variety of reasons, the devices generally are permitted to access the shared memory only one at a time. The memory controller, or some electronic circuitry associated with the memory controller, must select one of the access requests to process at any given time.
Several techniques are conventionally employed by electronic computing systems for deciding the order in which simultaneously pending access requests are processed. One conventional technique is a “round robin” method, wherein access requests are handled in some round robin order depending on the hardware involved. Another conventional technique processes access requests in order of an assigned priority. Still other conventional techniques process access requests in random order, or on a first-come, first-served basis.
Each of these conventional techniques is built around and implements a rigid set of ordering rules that are predefined and then rigorously implemented. The wooden, mechanical application of the ordering rules inherent in these conventional techniques frequently adversely impacts performance. More particularly, the order in which access requests are processed can significantly impact the bandwidth of the information processed responsive to the access requests.
For instance, the internal design of dynamic random access memory (“DRAM”) devices from which shared memories are typically constructed favor accesses to data in the same “page.” A page is a block of data that the internal DRAM control logic operates on for each access. Internal DRAM data is organized as pages, so that successive accesses to data bits that are in the same page are faster than successive accesses to data bits which are not in the same page. Because of this characteristic of DRAMs, it is more optimal to select memory requests that access data bits in the same DRAM page. Higher memory bandwidth can be achieved if successive memory requests are all accessing the same page of data. Thus, increased performance can be realized by ordering accesses to maximize the number of successive accesses to the same page(s).
Similarly, the total request throughput rate may be impacted by the selection order. It is common for requesting ports to have first-in, first-out (“FIFO”) queues that buffer memory requests and FIFOs that buffer the memory data returned by read memory requests. As long as these FIFOs are not filled, additional request may be generated and new memory read data returned. If a request FIFO is filled, then the corresponding port must stop and wait until the FIFO has room again. Thus, the request throughput rate will be lower. Likewise, if the memory read data FIFO is filled, then the memory controller must stop and wait until there is room in the FIFO. Again, the request throughput rate suffers. Because of the finite capacity of FIFOs used to store requests and memory read data, it is more efficient to select requests such that the FIFOs will not be filled. By avoiding the full condition, requests may be continually processed with no interruption. Thus, a higher request throughput rate is achieved.
To maximize efficiency and throughput rate under these types of constraints, arbitration and select logic used to decide the selection order should dynamically consider these types of factors. During each operational cycle, the requests should be examined for impact on performance and the more favorable request selected. It is also desirable to adjust the importance of priority of each of these constraints. This allows the various constraints to be weighed differently in making the selection.
However, conventional arbitration and select techniques consider none of these factors in a dynamic fashion. If they are considered at all, they are considered only in a mechanical fashion. Predetermined rules are woodenly applied. If a technique considers, for instance, two successive requests access the same page, whether a third request resides in a full FIFO is considered in the same fashion every time. Thus, although the shared memory might appreciate higher utilization, its performance is typically less than what it could be.
SUMMARY OF THE INVENTION
The invention comprises a technique for arbitrating and selecting one access request to a shared memory from among multiple contenders. In a first aspect, the invention includes a method for accessing a shared memory. The method includes receiving a plurality of access requests; presenting a plurality of characteristics for each access request; ascertaining a plurality of operational characteristics; and selecting one of the access requests for processing upon consideration of the access request characteristics and the operational characteristics. In a second aspect, the invention includes an arbitration and select logic (“ASL”) unit. The ASL unit comprises a plurality of input sorting units, each input sorting unit capable of receiving a respective access request and a merge and interleave unit (“MIU”). The MIU is capable of receiving a plurality of characteristics for each access request; receiving a plurality of operational characteristics; and selecting one of the access requests for processing upon consideration of the access request characteristics and the operational characteristics.


REFERENCES:
patent: 5938749 (1999-08-01), Rusu et al.
patent: 5983301 (1999-11-01), Baker et al.
patent: 6141323 (2000-10-01), Rusu et al.
patent: 6173378 (2001-01-01), Rozario et al.
patent: 6199145 (2001-03-01), Ajanovic et al.
patent: 6202137 (2001-03-01), Ottinger
patent: 6370624 (2002-04-01), Ajanovic et al.
patent: 6389480 (2002-05-01), Kotzur et al.
patent: 6490665 (2002-12-01), Lai et al.

Affiliated with

Also associated with

Rating

Arbitration and select logic for accessing a shared memory does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Arbitration and select logic for accessing a shared memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arbitration and select logic for accessing a shared memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3076991