Granted Patent B2

US 9,031,077 · App. 13/804,693 · Granted May 12, 2015

Abstract

Claims (41)

1. A parallel data unit processing system for passing data, the system comprising:

multiple ingress data producers receiving processed data, wherein the processed data include discrete data units that are each consecutively numbered, each of the data producers calculating insertion indices for ones of the data units passing therethrough based on each consecutive number; and

a circular buffer receiving the data units from the ingress data producers, the data units placed in slots that correspond to the respective insertion indices;

wherein the multiple ingress data producers follow a protocol so that the multiple ingress data producers operate independently of each other and without coordination or hand-shaking with each other.

2. The system of claim 1 in which the data units comprise packets.

3. The system of claim 1 in which a first one of the ingress data producers, upon failing to place a first data unit in the circular buffer, does not lock other ingress data producers from placing other data units in the circular buffer.

4. The system of claim 1 in which the ingress data producers comprise processor cores, each of the processor cores assigning the data units to an egress queue.

5. The system of claim 4 , further comprising a consumer of the data units that receives the data units from the circular buffer in an order that preserves sequential numbering of the data units, in which the consumer comprises the owner of the egress queue.

6. The system of claim 1 in which each of the slots of the circular buffer comprises a flag indicating whether the slot is in use.

7. The system of claim 1 in which each of the slots of the circular buffer comprises a reference to a particular data unit.

8. The system of claim 1 further comprising a consumer of the data units that receives the data units from the circular buffer, in which the consumer receives the first data unit from a first slot and changes a flag within the first slot to indicate that the first slot is unoccupied.

9. The system of claim 1 in which each of the ingress data producers checks a flag in a particular slot of the circular buffer and stalls upon determining that the flag indicates that the particular slot is occupied.

10. A method for passing a plurality of ordered data units in a system that includes multiple ingress data producers, a data consumer, and a memory buffer between the ingress data producers and the data consumer, the memory buffer having a plurality of slots, the method comprising:

at a first one of the ingress data producers, receiving a first data unit with a sequential number;

calculating an insertion index for the first data unit based on the sequential number of the first data unit, the insertion index corresponding to a first slot in the buffer;

discerning that the first slot is unavailable to receive the first data unit; and

stalling the first one of the ingress data producers from placing the first data unit in the first slot while not locking others of the ingress data producers from placing other data units in other slots.

11. The method of claim 10 further comprising:

placing the first data unit in the first slot after discerning that the data consumer has marked the first slot as unoccupied.

12. The method of claim 10 in which first slot is unavailable due to being marked as occupied by the data consumer.

13. The method of claim 10 further comprising:

at the data consumer, removing one of the data units from ones of the slots in the buffer according to a tail index that sequentially moves from slot to slot;

the consumer stalling upon discerning that a second slot is marked as unoccupied; and

un-stalling the consumer to remove a second data unit from the second slot after subsequently discerning that the second slot is marked as occupied.

14. The method of claim 10 in which the buffer is sized so that each ingress data producer has a slot for a plurality of data units passing therethrough.

15. A computer program product having a non-transitory computer readable medium tangibly recording computer program logic for maintaining data unit order by an ingress data producing unit, the computer program product comprising:

code to receive a data unit having a sequential number, the sequential number indicating an order of the data unit with respect to a plurality of data units;

code to calculate an insertion index for the data unit within a circular buffer, the insertion index being calculated from the sequential number;

code to check availability of a slot in the circular buffer, the slot corresponding to the insertion index;

code to stall the ingress data producing unit in response to determining that the slot is unavailable, wherein stalling the ingress data producing unit does not include locking other ingress data producing units from the circular buffer; and

code to place the data unit in the slot subsequently to at least one other data unit with a sequential number higher than that of the data unit.

16. The compute program product of claim 1 in which the code to place the data unit in the slot comprises:

code to place a pointer to the data unit in the slot; and

code to save the data unit itself in another memory.

17. The computer program product of claim 15 in which the data unit is placed in the circular buffer after determining that the slot has become available.

18. The computer program product of claim 15 further comprising:

code to mark the slot as in use after placing the data unit in the slot.

19. The computer program product of claim 15 in which the code to stall comprises:

code to discern that the slot includes unconsumed data.

20. The system of claim 1 , further comprising:

a consumer of the data units that receives at least a subset of the data units from the circular buffer as a batch in an order that preserves sequential numbering of the data units, wherein the consumer comprises the owner of the egress queue.

Assignments (9)