Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
1999-02-08
2003-07-29
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C710S120000
Reexamination Certificate
active
06601151
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to an apparatus and method for handling memory access requests in a data processing system.
In data processing systems of simple architecture a processor is connected to a main memory through a bus. A simple architecture of this kind has severe performance limitations because of memory latency and memory bandwidth. Because of this, most modern data processing systems have a multi-level memory hierarchy. At the top of the memory hierarchy, directly below the processor, there is provided a fast and small memory element, referred to as a cache memory. There then follows main memory and mass storage. Moreover, two or more levels of cache memory may be provided, for example an internal cache memory located on the same integrated circuit as the processor and an external cache memory located on a separate integrated circuit from the processor.
A typical modern data processing system thus has a multi-level memory hierarchy, with the higher levels of memory being associated with faster access times, i.e. lower latency, and the lower levels with slower access times, i.e. higher latency. However, between each level of the memory hierarchy there still remains a latency differential, and the overall latency difference between the processor, on the one hand, and the main memory or mass storage, on the other hand, still exists, notwithstanding the multi-level memory hierarchy.
Although increasing the memory access times of memories at each level of the memory hierarchy will certainly increase system performance, it is likely that an inherent latency differential between the processor and the memory hierarchy levels will remain a feature of future data processing systems, not only for technical, but also for economic, reasons.
The present invention is thus directed to increasing the efficiency with which memory access requests are handled by a data processing system by means other than speeding up memory access times or increasing memory bandwidth.
More especially, it is an aim of the present invention to provide a method and apparatus for increasing the throughput of memory access requests in a data processing system, independent of memory access times and memory bandwidth.
SUMMARY OF THE INVENTION
Particular and preferred aspects of the invention are set out in the accompanying independent and dependent claims. Features of the dependent claims may be combined with those of the independent claims as appropriate and in combinations other than those explicitly set out in the claims.
According to a first aspect of the invention there is provided a memory access request handling unit designed to intercept and re-order the flow of memory access requests output from a source of memory access requests prior to receipt by a target data storage element. Examples of common memory access requests are read requests and write requests. The memory access request handling unit comprises an input for receiving memory access requests and an output for transmitting memory access requests. A queue comprising a plurality of queue elements is arranged to receive, and to store temporarily, memory access requests received at the input pending transmission to the output. Comparison logic is provided that is operable to perform a comparison operation on the memory access requests stored in the queue elements. The result of the comparison operation is to select at least one of the memory access requests for transmission from the queue to the output. In this way, the comparison logic dynamically re-orders the sequence with which memory access requests are supplied to the data storage element.
A memory access request handling unit may be arranged between any two levels in a multi-level system hierarchy. For example, it may be arranged, between a processor and cache memory, between two cache memories at different levels of a memory hierarchy, or between a main memory and a mass storage medium. The mass storage medium may be a CD-ROM, or other mass storage medium such as a hard disk.
In an embodiment of the first aspect of the invention, the memory access request handling unit further comprises a list store comprising a plurality of list elements. Each list element is arranged to store a list entry derived from a memory access request that has previously been transmitted from the queue to the output for as long as that memory access request is being serviced at the data storage element. The comparison logic is arranged to compare ones of the memory access requests stored in the queue elements and the list entries stored in the list store, so as to dynamically select the order in which memory access requests are transmitted from the queue to the output. In this way, the transmission of a memory access request to the data storage element can be suppressed if there is an earlier memory access request still being serviced by the data storage element of the kind which would prevent the servicing of the later memory access request. Conversely, a memory access request stored in the queue can be promoted ahead of other memory access requests stored in the queue, if it can be serviced more rapidly than normal as a result of there being a memory access request currently being serviced by the data storage element of a similar or complementary kind.
In this embodiment, when a memory access request is transmitted from the queue to the output for the data storage element, a list entry is generated. The list entry may include a memory access request-type portion derived from an address portion of the queue element being transmitted. The list entry may also include an identifier portion by which the list entry can be identified on completion of the memory access request and thereby canceled when the data storage element has serviced the memory access request. The comparison logic may be arranged to prevent transmission of any memory access request from the queue to the data storage element which has an address portion that matches the memory access request-type portion of any one of the list entries. Moreover, the comparison logic may be operable preferentially to transmit memory access requests from the queue to the data storage element which have address portions that do not match the memory access request-type portions of any of the list entries.
Taking the example of a cache memory being the data storage element, a memory access request to the same cache line as the previous memory access request can be prevented in the event that the previous memory access request resulted in a cache miss, whereas a memory access request to a different cache line may hit and may thus be allowed to transmit from the queue to the data storage element by the comparison logic.
Taking another example of a main memory being the data storage element, the comparison logic can be arranged to prevent memory access requests being transmitted to any memory bank which is still servicing a previous data request.
In an alternative embodiment of the first aspect of the invention, the queue elements each have a source priority level storage portion arranged to receive a priority value when a memory access request is received at the input. The comparison logic is arranged to compare at least the source priority values of the memory access requests stored in the queue elements, so as to dynamically select the order in which memory access requests are transmitted from the queue to the output. In this way, it is possible to cause a later-generated memory access to reach the data storage element before earlier-generated memory access requests so that memory access requests with a higher priority can be serviced more quickly. The priority value can be determined by an input stage of the memory access request handling unit from attributes of the memory access request using a standard source. Alternatively, the priority value can be explicitly specified in each memory access request by the source, which will need to be specially designed to have this capability.
In a further embodiment of the first aspect of the in
Encarnacion Yamir
Kim Matthew
Kivlin B. Noäl
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Sun Microsystems Inc.
LandOfFree
Apparatus and method for handling memory access requests in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for handling memory access requests in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for handling memory access requests in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3065749