Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2001-07-12
2003-07-01
Bragdon, Reginald G. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S141000, C711S117000
Reexamination Certificate
active
06587926
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention generally relates to system address transmission and in particular to a method and system for transmitting data access transactions to and from storage devices. Still more particularly, the present invention relates to a method and system for tagging data access transactions in a manner optimized for use by hierarchically configured storage devices.
2. Description of the Related Art
High performance data processing systems typically include a number of levels of caching between the processor(s) and system memory to improve performance, reducing latency in data access operations. When utilized, multiple cache levels are typically employed in progressively larger sizes with a trade off to progressively longer access latencies. Smaller, faster caches are employed at levels within the storage hierarchy closer to the processor or processors, while larger, slower caches are employed at levels closer to system memory. Smaller amounts of data are maintained in upper cache levels, but may be accessed faster.
A conventional symmetric multiprocessor data processing system may include a number of processors that are each coupled to a shared system bus. Each processor may include an on-board cache that provides local storage for instructions and data, execution circuitry for executing instructions, and a bus interface unit (BIU) that supports communication across the shared system bus according to a predetermined bus communication protocol.
In conventional multiprocessor data processing systems, each BIU maintains a single queue of all outstanding communication requests generated within the processor. The communication requests indicate a request address and a request source within the processor. To promote maximum utilization of the system bus, the BIUs typically service the communication requests utilizing split bus transactions, which permit multiple bus transactions to be chronologically interleaved. For example, the BIU of a first processor may gain ownership of the system bus and initiate a first bus transaction by driving an address and appropriate control signals. The first processor may then relinquish ownership of the system bus while awaiting receipt of data associated with the address in order to permit a second processor to perform a portion of a second bus transaction. Thereafter, the device from which the first processor requested data may complete the first bus transaction by driving the requested data, which is then latched by the BIU of the first processor.
To allow devices snooping the system bus to identify and properly route bus transactions a system address tag that identifies the request source is included within each data access request and returned with each corresponding response. Furthermore, each BIU assigns each of its bus transactions an arbitrary bus tag that is transmitted during each tenure of the bus transaction. The bus tags are typically assigned cyclically out of a pool of bus tags equal in number to the maximum number of concurrent bus transactions supported by the device. For example, the BIU of a device supporting a maximum of eight concurrent bus transactions assigns one of eight low order 3-bit tags to each of its bus transactions. The system address tags and bus tags are stored by the device in association with the appropriate queue entries.
As data storage systems continue to grow in terms of greater numbers of processors and additional cache layers, the required tag field within each system bus packet is required to expand accordingly to maintain a unique identification for each pending data access transaction. In the interest of maintaining minimally divided data storage access request packets as well as minimizing the need for additional bus pins, the tag size has been controlled by utilizing translation queues for inter-system memory accesses. The increasing prevalence of data processing architectures wherein multiple SMPs share memory resources via non-uniform memory access (NUMA) architectures, for example, has further proliferated the incorporation of tag translation queues within complex data storage systems. Although tag translation queues are effective in minimizing the required tag field size, the translation process itself adds an additional delay as well as requiring overhead comparator logic.
The need to maintain uniquely associated tags gives rise to another problem—the need to maintain designated queue positions for ongoing data storage access transactions. Conventional bus tagging methodologies require that detailed information related to the source of the transaction (the requesting processor, for example) be encoded in the tag field such that upon retrieval of the requested data, intermediate cache levels and bus switching logic can determine the correct destination. A typical bus tag may include bits fields designating the address source type, the highest package structure, a next package structure (chip), the requesting processor, the unit within the chip, and the specific queue from which the request was initiated. As a data access request descends through a memory hierarchy, a queue entry is often reserved to wait for and recognize a returned response to the access request. The information encoded within the bus tag is maintained by the reserved queue entry, which is non-allocatable to other transactions until the requested data has been returned bearing the same tag. This condition is a significant source of memory transaction bottlenecks since the transaction time for individual requests within any given data storage access request sequence is unpredictable.
From the foregoing, it can therefore be appreciated that a need exists for an improved technique for identifying data storage access transaction wherein tag size is minimized without the need for tag translation. The present invention addresses such a need.
SUMMARY OF THE INVENTION
A method and system for managing a data access transaction within a hierarchical data storage system are disclosed herein. In accordance with the method of the present invention, a data access request is delivered from a source device to multiple data storage devices within the hierarchical data storage system. The data access request includes a source path tag and a target address. At least one device identification tag is appended within the source path tag, wherein the at least one device identification tag uniquely identifies a data storage device within each level of the hierarchical data storage system traversed by the data access request such that the data access transaction can be processed in accordance with source path information that is incrementally encoded within the data access request as the data access request traverses the hierarchical data storage system.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 5539895 (1996-07-01), Bishop et al.
patent: 5671371 (1997-09-01), Kondo et al.
U.S. patent application Ser. No. 09/903,728, Arimilli et al., filed Jun. 29, 2001.
U.S. patent application Ser. No. 09/903,727, Arimilli et al., filed Jun. 29, 2001.
Arimilli Ravi Kumar
Dodson John Steven
Lewis Jerry Don
Bracewell & Patterson L.L.P.
Bragdon Reginald G.
Namazi Mehdi
Salys Casimer K.
LandOfFree
Incremental tag build for hierarchical memory architecture does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Incremental tag build for hierarchical memory architecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Incremental tag build for hierarchical memory architecture will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3019093