Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
1999-01-05
2002-07-23
Bragdon, Reginald G. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S144000, C711S151000
Reexamination Certificate
active
06425060
ABSTRACT:
FIELD OF THE INVENTION
The invention is generally related to computers and other data processing systems, and in particular to the scheduling of transactions between source and destination units in a data processing system.
BACKGROUND OF THE INVENTION
Computer technology continues to advance at a remarkable pace, with numerous improvements being made to the performance of both microprocessors—the “brains” of a computer—and the memory that stores the information processed by a computer.
In general, a microprocessor operates by executing a sequence of instructions that form a computer program. The instructions are typically stored in a memory system having a plurality of storage locations identified by unique memory addresses. The memory addresses collectively define a “memory address space,” representing the addressable range of memory addresses that can be accessed by a microprocessor.
Both the instructions forming a computer program and the data operated upon by those instructions are often stored in a memory system and retrieved as necessary by the microprocessor when executing the computer program. The speed of microprocessors, however, has increased relative to that of memory devices to the extent that retrieving instructions and data from a memory can often become a significant bottleneck on performance. To decrease this bottleneck, it is desirable to use the fastest available memory devices possible, e.g., static random access memory (SRAM) devices or the like. However, both memory speed and memory capacity are typically directly related to cost, and as a result, many computer designs must balance memory speed and capacity with cost.
A predominant manner of obtaining such a balance is to use multiple “levels” of memories in a memory system to attempt to decrease costs with minimal impact on system performance. Often, a computer relies on a relatively large, slow and inexpensive mass storage system such as a hard disk drive or other external storage device, an intermediate main memory that uses dynamic random access memory devices (DRAM's) or other volatile memory storage devices, and one or more high speed, limited capacity cache memories, or caches, implemented with SRAM's or the like. One or more memory controllers are then used to swap the information from segments of memory addresses, often known as “cache lines”, between the various memory levels to attempt to maximize the frequency that requested memory addresses are stored in the fastest cache memory accessible by the microprocessor. Whenever a memory access request attempts to access a memory address that is not cached in a cache memory, a “cache miss” occurs. As a result of a cache miss, the cache line for a memory address typically must be retrieved from a relatively slow, lower level memory, often with a significant performance hit.
Another manner of increasing computer performance is to use multiple microprocessors operating in parallel with one another to perform different tasks at the same time. Often, the multiple microprocessors share at least a portion of the same memory system to permit the microprocessors to work together to perform more complex tasks. The multiple microprocessors are typically coupled to one another and to the shared memory by a system bus or other like interconnection network. By sharing the same memory system, however, a concern arises as to maintaining “coherence” between the various memory levels in the shared memory system —that is, ensuring that there are not multiple modified copies of any particular data in the system.
For example, in a given multi-processor environment, each microprocessor may have one or more dedicated cache memories that are accessible only by that microprocessor, e.g., level one (L
1
) data and/or instruction cache, a level two (L
2
) cache, and/or one or more buffers such as a line fill buffer and/or a transition buffer. Moreover, more than one microprocessor may share certain caches as well. As a result, any given memory address may be stored from time to time in any number of components in the shared memory system.
Coherency is maintained in many systems by maintaining “state” information that indicates the status of the data stored in different components of a system. Often, this information is stored locally with each component. Furthermore, to reduce the amount of state information, multiple memory addresses are often grouped together into lines or blocks having a common state.
As an example, many systems utilize a MESI coherence protocol that tags data stored in a component as one of four states: Modified, Exclusive, Shared, or Invalid. The modified state indicates that valid data for a particular group of memory addresses is stored in the component, and the component has the most recent copy of the data—i.e., all other copies, if any, are no longer valid. The Exclusive state indicates that valid data for a particular group of memory addresses is stored solely in the component, but the data has not been modified relative to the copy in the shared memory. The Shared state indicates that the valid data for a particular group of memory addresses is stored in the component, but that other valid copies of the data also exist in other components, including the main memory. The Invalid state indicates that no valid data for a particular group of memory addresses is stored in the component, although valid data may be stored in the main memory.
In many conventional implementations, accesses to memory addresses in a shared memory system are handled via transactions, which are typically packets of information transmitted from a source unit to a destination unit to perform a predetermined operation. As one example, separate request and response transactions may be used to maintain cache coherency and initiate the transfer of data between the different components in a system. A request transaction may be initiated by a source unit such as a microprocessor to request an access to data stored at a particular memory address, e.g., a load or read request or a store or write request. One or more destination units, e.g., another microprocessor, a cache and/or a system bus interface unit, receive and process the request. Each destination unit then functions as a source unit by issuing a response transaction back to the original source unit, typically indicating, based upon the state information for the requested memory address, whether or not the requested data is allocated to that unit. Also, if the requested data is allocated to that unit, the data is typically returned to the requesting unit in the response transaction. Furthermore, often the state information for each component in the system is updated in response to the operation being performed.
One difficulty that arises with transaction-based shared memory systems is that with multiple source and destination units, multiple transactions may need to be transmitted and processed at any given time across the interface between the different units. As a result, some mechanism to schedule transactions is typically required.
Conventional scheduling mechanisms typically implement some form of fairness algorithm, e.g., where transactions are transmitted and processed on a first-come, first-served basis, and where transactions that arrive at the same time are scheduled in a round-robin or random fashion. No explicit prioritization, except temporal, is typically utilized in scheduling transactions.
While a purely fair algorithm ensures that all transactions are eventually handled in a shared memory system, in many instances such an algorithm offers only moderate performance. As a result, a need has arisen for an improved scheduling algorithm that offers improved performance over conventional implementations.
SUMMARY OF THE INVENTION
The invention addresses these and other problems associated with the prior art by providing a data processing system, circuit arrangement, and method that rely on state information to prioritize certain transactions relative to other transactions when scheduling transactions in a da
Freerksen Donald Lee
Mounes-Toussi Farnaz
Bragdon Reginald G.
Wood Herron & Evans
LandOfFree
Circuit arrangement and method with state-based transaction... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Circuit arrangement and method with state-based transaction..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuit arrangement and method with state-based transaction... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2851357