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
38 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)
-
-
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)
-
-
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. - View Dependent Claims (26, 27, 28, 29, 30, 31, 32)
-
-
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. - View Dependent Claims (34, 35, 36, 37)
-
-
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.
-
Specification