Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-05-20
2001-11-13
Bragdon, Reginald G. (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S109000, C711S156000, C711S158000, C711S146000, C711S167000
Reexamination Certificate
active
06317806
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The invention relates to data processing systems and, more particularly, to an apparatus and method for controlling a static queue used in a data processing system.
BACKGROUND OF THE INVENTION
Data processing systems, including microprocessors, may use queues for temporarily storing information prior to being transferred to some other resource in the system. Each queue comprises a series of registers of suitable width for the information which they are to store temporarily. Each register represents a location in the queue. The information which may be stored in a queue location may comprise memory address information, data, or control information. Regardless of the number of locations in a particular queue and the width of each location, some mechanism must be associated with the queue for selecting a particular location so that the information stored in that location may be transferred to another resource in the system.
A queue may be operated to shift the stored information from one queue location to the next. This shifting operation may be used to control how the stored information is transferred from the queue to the next resource in the system. For example, queue entries may shift down through the locations in a queue, with each entry moving to the next location in the queue on the occurrence of an event such as a clock cycle. Upon the occurrence of each event, the entry in the last queue location exits the queue and the first queue location receives a new queue entry. Alternatively, a queue may be operated to hold information in a single location until the information is selected to be transferred to another resource in the system. These static queues must include some mechanism by which a particular queue location may be selected.
A queue may be used in a data processing system to hold address, data, and control information associated with a number of outstanding or pending store transactions. Store transactions which may be held in the queue include write-through stores, pushes, interventions, castouts, cache control operations, and barrier instructions.
Referring still to the store example, it is desirable to prioritize transactions in the queue to ensure that certain transactions are transferred on for processing earlier than other transactions which may have been stored in the queue. A castout transaction from one processor, for example, is preferably transferred from the queue more quickly when another processor requests the information stored at the address specified by the castout transaction. It is also desirable to eliminate certain transactions from the queue to prevent the transactions from being passed on to the next processing step. For example, where a castout transaction is to be stored in the queue specifies an address which is the same address as that specified in an older castout transaction already resident in the queue, in this case the older transaction represents a transaction with stale data. It is, therefore, desirable to remove such a castout transaction from the queue in order to prevent the transaction from being finished unnecessarily only to be overwritten by the newer castout transaction.
Prior data processing systems have used a priority bit in each queue location to differentiate between the priorities of different transactions in the queue. Arbitration logic associated with these systems used the priority bits to schedule the transactions for transfer from the queue. However, the larger the queue, the more complex the arbitration logic required to implement a priority bit scheme.
A store transaction queue may be implemented as a dynamic queue in which transactions shift from one location to the next in each clock cycle or other event. However, shifting large amounts of data in the queue causes power dissipation and does not facilitate prioritization of transactions in the queue.
SUMMARY OF THE INVENTION
It is an object of the invention to provide an apparatus and method for efficiently queuing information in a processor. Another object of the invention is to provide for more efficient use of system resources by prioritizing queue entries and facilitating reprioritization as desired, and by removing certain types of transactions to prevent them from consuming system resources.
The queuing apparatus according to the invention includes at least one static queue and at least one index queue. The index queue or queues are used to retrieve entries from the static queue or queues. By using index queues to control the static queues, information may be transferred from the static queues without the power dissipation inherently associated with shifting large amounts of data within the queues. Also, multiple index queues may be used to ensure that higher priority static queue entries are transferred from the static queues earlier than lower priority entries. The queuing arrangement according to the invention may also be implemented to facilitate the reprioritization of a static queue entry based upon events which may occur after the entry is stored in a static queue.
The queuing apparatus includes a static queue having a plurality of static queue locations. Each static queue location is adapted to store a static queue entry. Also, each static queue location includes an availability indicator, preferably an availability bit, which is used to indicate an availability status of the respective static queue location. An index generator is associated with the static queue and provides a unique index value or pointer for each static queue entry. The index value for a particular static queue entry identifies the static queue location containing the particular static queue entry. For example, a static queue according to the invention may have eight queue locations, identified as locations zero through seven. The index for the particular static queue entry currently stored in static queue location five, for example, may comprise the binary representation for the number five, that is, 101.
Each index queue includes a plurality of index queue locations. Each index queue location is adapted for storing one of the index values provided by the index generator. Also, each index queue location preferably includes a position for an index value validity indicator. Since each index queue location stores only an index value and perhaps a validity indicator, each index queue location may be relatively small compared with a location in the static queue. For an eight-location static queue, each index queue location may include only four bits, three bits for storing the respective index value and one bit for the validity indicator.
The queuing system according to the invention also includes a static queue accessing arrangement. The static queue accessing arrangement retrieves a selected index value from a particular index queue location and uses the selected index value to retrieve the static queue entry with which the index value is associated. Once the static queue entry is retrieved from the static queue, the static queue accessing arrangement also preferably marks the static queue location from which the entry was retrieved as being available for storing a new static queue entry. The static queue location may be marked by changing the availability indicator to an “available” status.
In a preferred form of the invention a plurality of index queues are used to control the static queue. Each index queue is reserved for index values associated with a certain priority level. For example, the queuing arrangement may include two separate index queues, a first index queue for storing index values associated with low priority static queue entries, and a second index queue for storing index values associated with high priority static queue entries. In this preferred form of the invention, the apparatus also includes queue selection logic for selecting the index queue from which the next index value is to the retrieved. Location selection logic is also included for selecting a particular location within the selected index queue.
For example, each
Audityan Srinath
Petersen Thomas Albert
Podnar Robert Charles
Bragdon Reginald G.
England Anthony V. S.
Gulbertson Russell D.
International Business Machines - Corporation
Shaffer & Culbertson
LandOfFree
Static queue and index queue for storing values identifying... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Static queue and index queue for storing values identifying..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Static queue and index queue for storing values identifying... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2576971