Static queue and index queue for storing values identifying static queue locations

• US 6,317,806 B1
• Filed: 05/20/1999
• Issued: 11/13/2001
• Est. Priority Date: 05/20/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation, Freescale Semiconductor, Inc. (NXP Semiconductors NV)
• Original Assignee: International Business Machines Corporation
• Inventors: Podnar, Robert Charles, Petersen, Thomas Albert, Audityan, Srinath
• Primary Examiner(s): BRAGDON, REGINALD GLENWOOD
• Application Number:
  US09/315,612
• Time in Patent Office: 908 Days
• Field of Search: 711/109, 711/156, 711/158, 711/146, 711/167, 711/101, 710/57
• US Class Current: 711/101
• CPC Class Codes: G06F 12/0855 Overlapped cache accessing, e.g. pipeline G06F12/0846 takes precedence
• CPC Class Codes: G06F 5/06 for changing the speed of data flow, i.e. speed regularising or timing, e.g. delay lines, FIFO buffers; over- or underrun control therefor G06F7/78 takes precedence
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A queuing apparatus associated with a processor includes at least one static queue (11), an index generator (34), at least one index queue (37), and a static queue accessing arrangement. Each static queue (11) has a number of static queue locations (12), each for storing a static queue entry and an availability indicator (14) for indicating an availability status of the respective static queue location. The index generator (34) uses information from the static queue (11) to provide a unique index value for each static queue entry, the index value for a particular static queue entry identifying the static queue location (12) containing the particular static queue entry. Each index queue (37, 42) has a number of index queue locations (40), each for storing one of the index values provided by the index generator (34). The static queue accessing arrangement retrieves a selected index value from a particular index queue location (40), and uses the selected index value to retrieve the static queue entry with which the selected index value is associated. Multiple index queues (37, 42) facilitate prioritization of static queue entries, and reprioritization by transferring index queue values from one index queue to another. The index queues (37, 42) also facilitate compaction of unnecessary static queue entries.

Claims

1. A queuing apparatus associated with a processor, the queuing apparatus comprising:

(a) a static queue having a plurality of static queue locations, each static queue location for storing a static queue entry and having an availability indicator for indicating an availability status of the respective static queue location;

(b) an index generator associated with the static queue, the index generator for providing a unique index value for each static queue entry, the index value for a particular static queue entry identifying the static queue location containing the particular static queue entry;

(c) at least one index queue, each index queue having a plurality of index queue locations and each index queue location for storing one of the index values provided by the index generator; and

(d) a static queue accessing arrangement for (i) retrieving a selected index value from a particular index queue location, (ii) using the selected index value to retrieve the static queue entry with which the selected index value is associated, and (iii) changing the availability status of the static queue location which stored the retrieved static queue entry, the availability status being changed to an available status.

2. The queuing apparatus of claim 1 wherein each index value is associated with one of a plurality of priority levels, and further comprising:

(a) one index queue for each priority level, each index queue for storing index values associated with a particular one of the priority levels.

3. The queuing apparatus of claim 2 further comprising:

(a) index queue selection logic for selecting one of the index queues to access the index value stored in the selected index queue location in that particular index queue.

4. The queuing apparatus of claim 1 further comprising:

(a) index queue location selection logic for selecting the particular index queue location.

5. The queuing apparatus of claim 1 further comprising:

(a) an index queue transfer arrangement for transferring an identified index value from one index queue to a different index queue.

6. The queuing apparatus of claim 5 wherein the index queue transfer arrangement comprises:

(a) a static queue comparator arrangement for receiving a snoop transaction and identifying a snoop matching static queue entry, the snoop matching static queue entry comprising a static queue entry which matches the received snoop transaction;

(b) an index queue comparator arrangement for locating the identified index value in a first index queue, the identified index value comprising the particular index value associated with the snoop matching static queue entry;

(c) an index queue invalidating arrangement associated with the first index queue, the index queue invalidating arrangement for invalidating the identified index value in the first index queue; and

(d) a transfer control arrangement for receiving the identified index value from the index queue comparator arrangement and for storing the identified index value in a second, higher priority index queue.

7. The queuing apparatus of claim 6 further comprising:

(a) a synchronizing arrangement associated with the transfer control arrangement, the synchronizing arrangement for ensuring that the identified index value is stored in the second index queue during a clock cycle in which no new entry is stored in the static queue.

8. The queuing apparatus of claim 1 wherein the static queue comprises a first static queue and further comprising:

(a) a plurality of additional static queues each additional static queue having a queue location which (i) corresponds to a static queue location in the first static queue and (ii) is identified by the respective index value associated with the corresponding static queue location in the first static queue.

9. The queuing apparatus of claim 1 further comprising:

(a) a queue compacting arrangement for invalidating a duplicate transaction index value from a first index queue, the duplicate transaction index value indicating a static queue entry for a duplicate transaction.

10. The queuing apparatus of claim 9 wherein the index queue compacting arrangement comprises:

(a) a static queue comparator arrangement for receiving a transaction specifier and for identifying a duplicate static queue entry, the duplicate static queue entry comprising a static queue entry which matches the received transaction specifier;

(b) an index queue comparator arrangement associated with the first index queue for identifying a matching index value in the first index queue, the matching index value comprising the particular index value associated with the duplicate static queue entry;

(c) an index queue location invalidating arrangement associated with the first index queue, the index queue location invalidating arrangement for invalidating the identified index value in the first index queue;

(d) a static queue canceling arrangement for invalidating the duplicate static queue entry.

11. A static queue control method comprising the steps of:

(a) storing a plurality of static queue entries in a static queue, each static queue entry being stored in a different static queue location in the static queue, and each static queue entry including an availability indicator indicating an availability status for the respective static queue location;

(b) generating a unique index value for each static queue entry, the index value for a particular static queue entry identifying the static queue location containing the particular static queue entry;

(c) storing each index value in a different index queue location in an index queue;

(d) retrieving a selected index value from one of the index queue locations; and

(e) using the selected index value to retrieve the static queue entry with which the selected index value is associated.

12. The method of claim 11 further comprising the step of:

(a) changing the availability status of the retrieved static queue entry to an available status.

13. The method of claim 11 wherein:

(a) each index value is associated with one of a plurality of relative priorities;

(b) separate index queues are provided for storing index values of like relative priority; and

(c) the step of storing a particular index value includes the step of selecting one of the index queues according to the relative priority with which the particular index value is associated.

14. The method of claim 13 wherein the step of retrieving the selected index value includes:

(a) choosing one of the index queues based upon the relative priority of the index values for which the respective index queue is reserved.

15. The method of claim 11 further comprising the step of:

(a) transferring an identified index value from one index queue to a different index queue, the different index queue being reserved for index values associated with a different relative priority.

16. The method of claim 15 wherein the step of transferring the identified index value includes the steps of:

(a) receiving a snoop transaction;

(b) identifying a snoop matching static queue entry, the snoop matching static queue entry comprising a static queue entry which matches the received snoop transaction;

(c) locating the identified index value in a first index queue, the identified index value comprising the particular index value associated with the snoop matching static queue entry; and

(d) invalidating the identified index value in the first index queue.

17. The method of claim 16 wherein the step of transferring the identified index value further includes the steps of:

(a) passing the identified index value through a synchronizing arrangement to ensure that the identified index value is stored in the different index queue during a clock cycle in which no new entry is stored in the static queue.

18. The method of claim 11 further comprising the steps of:

(a) invalidating a duplicate transaction index value from a first index queue, the duplicate transaction index value identifying the static queue entry for a duplicate transaction; and

(b) invalidating the static queue entry for the duplicate transaction.

19. The method of claim 18 wherein the step of invalidating the duplicate transaction index value includes the steps of:

(a) receiving a transaction specifier;

(b) identifying a duplicate static queue entry, the duplicate static queue entry comprising a static queue entry which matches the received transaction specifier; and

(c) identifying the duplicate transaction index value in the first index queue, the duplicate transaction index value comprising a particular index value associated with the duplicate static queue entry.

20. A queuing apparatus associated with a processor, the queuing apparatus comprising:

(a) a static queue having a plurality of static queue locations, each static queue location for storing a static queue entry and having an availability indicator for indicating an availability status of the respective static queue location;

(b) an index generator associated with the static queue, the index generator for providing a unique index value for each static queue entry, each index value being associated with one of a plurality of priority levels, the index value for a particular static queue entry identifying the static queue location containing the particular static queue entry;

(c) a plurality of index queues, one index queue for each of the plurality of priority levels, each index queue having a plurality of index queue locations and each index queue location for storing one of the index values provided by the index generator, each respective index queue being reserved for index values associated with a single one of the priority levels; and

(d) a static queue accessing arrangement for (i) retrieving a selected index value from a particular index queue location, and (ii) using the selected index value to retrieve the static queue entry with which the selected index value is associated.

21. The queuing apparatus of claim 20 further comprising:

(a) an index queue transfer arrangement for transferring an identified index value from one index queue to a different index queue.

22. The queuing apparatus of claim 21 wherein the index queue transfer arrangement comprises:

(a) a static queue comparator arrangement for receiving a snoop transaction and identifying a snoop matching static queue entry, the snoop matching static queue entry comprising a static queue entry which matches the received snoop transaction;

(b) an index queue comparator arrangement for locating the identified index value in a first index queue, the identified index value comprising the particular index value associated with the snoop matching static queue entry;

(c) an index queue invalidating arrangement associated with the first index queue, the index queue invalidating arrangement for invalidating the identified index value in the first index queue; and

(d) a transfer control arrangement for receiving the identified index value from the index queue comparator arrangement and for storing the identified index value in a second, higher priority index queue.

23. The queuing apparatus of claim 22 further comprising:

(a) a synchronizing arrangement associated with the transfer control arrangement, the synchronizing arrangement for ensuring that the identified index value is stored in the second index queue during a clock cycle in which no new entry is stored in the static queue.

24. The queuing apparatus of claim 20 further comprising:

(a) an index queue compacting arrangement for invalidating a duplicate transaction index value from one of the index queues, the duplicate transaction index value indicating a static queue entry for a duplicate transaction.

25. The queuing apparatus of claim 24 wherein the index queue compacting arrangement comprises:

(a) a static queue comparator arrangement for receiving a transaction specifier and for identifying a duplicate static queue entry, the duplicate static queue entry comprising a static queue entry which matches the received transaction specifier;

(b) an index queue comparator arrangement for identifying a matching index value in a first index queue, the matching index value comprising the particular index value associated with the duplicate static queue entry;

(c) an index queue location invalidating arrangement associated with the first index queue, the index queue location invalidating arrangement for invalidating the identified index value in the first index queue; and

(d) a static queue location invalidating arrangement for invalidating the duplicate static queue entry.