Concurrent non-blocking FIFO array

• US 20030065892A1
• Filed: 09/28/2001
• Published: 04/03/2003
• Est. Priority Date: 09/28/2001
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Bonola, Thomas J.
• Granted Patent: US 6,697,927 B2
• Time in Patent Office: Days
• US Class Current: 711/147
• CPC Class Codes: G06F 13/4059 where the synchronisation uses buffers, e.g. for speed matching between buses
• CPC Class Codes: G06F 5/10 having a sequence of storage locations each being individually accessible for both enqueue and dequeue operations, e.g. using random access memory G06F5/065 takes precedence

Abstract

A technique for providing concurrent non-blocking access to a circular queue is provided. The concurrent non-blocking circular queue also may be configured such that cache-coherent requesters and a non-cache-coherent requester (e.g., software and hardware) both may concurrently access the queue. Further, the queue may be configured such that the probability of occurrence of the ABA race condition may be minimized.

Claims

1. A concurrent non-blocking queue, comprising:

a plurality of entries arranged in a circular queue and configured such that a plurality of requesters have access to enqueue data to and dequeue data from the queue;

enqueue logic to direct an enqueue access to a current enqueue entry of the plurality of entries; and

dequeue logic to direct a dequeue access to a current dequeue entry of the plurality of entries,

wherein the enqueue logic and dequeue logic cooperate such that the plurality of requesters can perform concurrent accesses on the circular queue, and

wherein the queue is configurable in one of a cache-coherent only mode in which only cache-coherent requesters of the plurality of requesters have access to the circular queue and a non-cache-coherent mode in which a non-cache-coherent requester of the plurality of requesters may access the circular queue.

2. The queue as recited in claim 1, wherein the dequeue logic is configured such that data cannot be dequeued from an entry until the entry is marked as available for dequeuing.

3. The queue as recited in claim 2, wherein, in the cache-coherent only mode, the entry is marked as available for dequeuing when the data is enqueued in the entry.

4. The queue as recited in claim 2, wherein, in the non-cache-coherent mode, the entry is marked as available for dequeuing after an access to the entry has been completed by the non-cache-coherent requester.

5. The queue as recited in claim 2, wherein each entry comprises:

a data field to store data; and

a consumed field, wherein contents of the consumed field are representative of whether the entry is available for dequeuing.

6. The queue as recited in claim 5, wherein the contents of the consumed field comprise a consumed bit, and wherein, in the cache-coherent only mode, the state of the consumed bit is set to indicate the entry is available for dequeuing when an enqueue access is performed on the entry.

7. The queue as recited in claim 5, wherein the contents of the consumed field comprise a consumed bit, and wherein, in the non-cache-coherent mode, the state of the consumed bit is set to indicate the entry is available for dequeuing when an access on the entry by the non-cache-coherent requester is completed.

8. The queue as recited in claim 5, wherein each entry comprises a count field to store a count that is incremented each time the data is dequeued from the entry.

9. The queue as recited in claim 1, wherein the enqueue logic is configured to detect and repair an anomalous condition on the circular queue that hinders successful completion of an access on the circular queue.

10. The queue as recited in claim 9, wherein the anomalous condition is detected if the enqueue pointer is not indicating a valid current enqueue entry.

11. The queue as recited in claim 10, wherein the enqueue logic repairs the anomalous condition by incrementing the enqueue pointer.

12. The queue as recited in claim 1, wherein the dequeue logic is configured to detect and repair an anomalous condition on the circular queue that hinders successful completion of an access on the queue.

13. The queue as recited in claim 12, wherein the anomalous condition is detected if the dequeue pointer is not indicating a valid current dequeue entry.

14. The queue as recited in claim 13, wherein the dequeue logic repairs the anomalous condition by retrying the current dequeue request.

15. The queue as recited in claim 13, wherein the anomalous condition is detected if a previous dequeue entry is occupied, and the dequeue logic repairs the anomalous condition by clearing the previous dequeue entry.

16. The queue as recited in claim 1, wherein in the non-cache-coherent mode, the plurality of requesters comprises a software requester and a hardware requester.

17. The queue as recited in claim 1, wherein the plurality of requesters comprises a plurality of software threads.

18. The queue as recited in claim 1, wherein the plurality of requesters comprises a plurality of processors.

19. A concurrent non-blocking queue, comprising:

a plurality of entries arranged in a circular queue concurrently accessible by a plurality of requesters;

enqueue logic to enqueue data into the queue, wherein the enqueue logic provides an enqueue pointer to a current enqueue entry of the plurality of entries; and

dequeue logic to dequeue data from the queue, wherein the dequeue logic provides a dequeue pointer to a current dequeue entry of the plurality of entries,

wherein the enqueue logic and the dequeue logic are configured to detect and repair an anomalous condition hindering completion of a request on the circular queue.

20. The queue as recited in claim 19, wherein the anomalous condition comprises an invalid current entry, and wherein the repair comprises incrementing the enqueue pointer.

21. The queue as recited in claim 20, wherein the invalid current entry comprises a current enqueue entry that is occupied.

22. The queue as recited in claim 19, wherein the repair comprises retrying the current request.

23. The queue as recited in claim 19, wherein the anomalous condition comprises an occupied previous dequeue entry, and wherein the repair comprises clearing the previous dequeue entry.

24. The queue as recited in claim 19, wherein the circular queue is configurable in one of a cache-coherent only mode in which the plurality of requesters comprises only cache-coherent requesters, and a non-cache-coherent mode in which the plurality of requesters comprises a cache-coherent requester and a non-cache-coherent requester.

25. A method of providing concurrent non-blocking access to a circular queue having a plurality of entries, the circular queue being concurrently accessible by a plurality of requesters which generate a plurality of requests to enqueue data to and dequeue data from current entries of the circular queue, each current entry being indicated by an enqueue pointer or a dequeue pointer, the method comprising the acts of:

detecting, while executing a current request of the plurality of requests from a current requester of the plurality of requesters, an anomalous condition that hinders successful completion of a request of the plurality of requests to the circular queue; and

repairing, while executing the current request, the anomalous condition.

26. The method as recited in claim 25, wherein the anomalous condition hinders successful completion of the current request.

27. The method as recited in claim 25, wherein the act of repairing the anomalous condition comprises the act of executing an atomic operation.

28. The method as recited in claim 25, wherein detecting the anomalous condition comprises the act of determining whether the current enqueue entry is occupied, and wherein repairing the anomalous condition comprises the acts of determining whether the value of the enqueue pointer match a value stored during execution of the current requests and incrementing the value of the enqueue pointer if the values matches the stored value.

29. The method as recited in claim 28, wherein the acts of determining whether the value of the enqueue pointer matches and incrementing the value of the enqueue pointer comprises the act of atomically executing a compare and exchange operation.

30. The method as recited in claim 25, wherein the act of repairing the anomalous condition comprises the act of retrying the current request.

31. The method as recited in claim 25, wherein detecting the anomalous condition comprises the act of determining whether a previous dequeue entry is occupied, and wherein repairing the anomalous condition comprises the acts of determining whether the contents of the previous dequeue entry match a value stored during execution of the current request and clearing the previous dequeue entry if the contents match.

32. The method as recited in claim 31, wherein the acts of determining whether the contents of the previous dequeue entry match and clearing the previous dequeue entry are performed as an atomic operation.

33. A method of providing concurrent non-blocking access to a circular queue by a plurality of concurrent requesters, the circular queue comprising a plurality of entries, the plurality of concurrent requesters comprising a cache-coherent requester and a non-cache-coherent requester, the method comprising the acts of:

enqueuing data to a first entry of the plurality of entries; and

preventing dequeuing of the data from the first entry by a cache-coherent requester until an access to the first entry by a non-cache-coherent requester is complete.

34. The method as recited in claim 33, comprising the acts of:

detecting, while executing a current request from the plurality of requesters to the circular queue, an anomalous condition; and

repairing the anomalous condition.

35. The method as recited in claim 34, wherein the anomalous condition hinders successful completion of an access to the circular queue.

36. The method as recited in claim 34, wherein the act of detecting an anomalous condition comprises the acts of:

determining whether a current enqueue entry of the plurality of entries is occupied;

determining whether the value of a current enqueue pointer to the current enqueue entry matches a stored value stored during execution of the current request if the current enqueue entry is occupied; and

incrementing the value of the current enqueue pointer if the value matches the stored valued.

37. The method as recited in claim 36, wherein the act of determining whether the value of the current enqueue pointer matches the stored value and the act of incrementing the value of the current enqueue pointer are performed as an atomic operation.

38. A tangible storage medium, comprising:

a setup routine to establish a concurrent non-blocking circular queue, the setup routine configured to establish a number of entries for the circular queue, a number of bits for each entry, and an operational mode for the circular queue, wherein the operational mode is one of a cache-coherent only mode in which only cache-coherent requesters may concurrently access the circular queue and a non-cache-coherent mode in which a non-cache-coherent requester also may concurrently access the circular queue;

an enqueue routine to enqueue data to entries for the circular queue; and

a dequeue routine to dequeue data from the entries for the circular queue,

wherein the enqueue and dequeue routines are configured to cooperate to detect and repair an anomalous condition that hinders successful completion of an access on the circular queue, and to provide for concurrent accesses on the circular queue performed by a non-cache-coherent requester.