Concurrent non-blocking FIFO array
First Claim
Patent Images
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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
24 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
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. - View Dependent Claims (20, 21, 22, 23, 24)
-
Specification