Context-switched multi-stream pipelined reorder engine
First Claim
1. A reorder engine for reordering a plurality of out-of-order data items, received from a plurality of sources, to correspond to a transmitted order from each of the plurality of sources, the reorder engine comprising:
- a plurality of sets of context memories operatively coupled to a plurality of pipelined stages, where one of the plurality of sets of context memories stores state information associated with a state of reordering of data items transmitted by one of the plurality of sources; and
a pipeline that includes the plurality of pipelined stages, the pipeline to;
receive a data item,determine a particular source, of the plurality of sources, from which the data item was transmitted, based on source identification information obtained from the data item or based on source identification information read from one or more context memories of the plurality of sets of context memories,identify a particular set of context memories, of the plurality of context memories, based on the determination of the particular source, of the plurality of sources, anddetermine a position for the data item, relative to other data items transmitted by the particular source, of the plurality of sources, based on particular state information obtained from at least one context memory of the particular set of context memories, andorder the data item, based on the determined position for the data item, with respect to the other data items transmitted by the particular source of the plurality of sources.
0 Assignments
0 Petitions
Accused Products
Abstract
A pipelined reorder engine reorders data items received over a network on a per-source basis. Context memories correspond to each of the possible sources. The pipeline includes a plurality of pipeline stages that together simultaneously operate on the data items. The context memories are operatively coupled to the pipeline stages and store information relating to a state of reordering for each of the sources. The pipeline stages read from and update the context memories based on the source of the data item being processed.
-
Citations
22 Claims
-
1. A reorder engine for reordering a plurality of out-of-order data items, received from a plurality of sources, to correspond to a transmitted order from each of the plurality of sources, the reorder engine comprising:
-
a plurality of sets of context memories operatively coupled to a plurality of pipelined stages, where one of the plurality of sets of context memories stores state information associated with a state of reordering of data items transmitted by one of the plurality of sources; and a pipeline that includes the plurality of pipelined stages, the pipeline to; receive a data item, determine a particular source, of the plurality of sources, from which the data item was transmitted, based on source identification information obtained from the data item or based on source identification information read from one or more context memories of the plurality of sets of context memories, identify a particular set of context memories, of the plurality of context memories, based on the determination of the particular source, of the plurality of sources, and determine a position for the data item, relative to other data items transmitted by the particular source, of the plurality of sources, based on particular state information obtained from at least one context memory of the particular set of context memories, and order the data item, based on the determined position for the data item, with respect to the other data items transmitted by the particular source of the plurality of sources. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method performed by a reorder engine, the reorder engine including a plurality of pipelined stages to reorder data items transmitted by a plurality of sources, to correspond to a transmitted order, the method comprising:
-
receiving, by the reorder engine, sequence information associated with the data items transmitted by the plurality of sources, the sequence information, for each data item, including a different one of a plurality of sequence numbers associated with one of the plurality of sources; performing, by the reorder engine and using a stage of the plurality of pipelined stages, an arbitration operation on particular sequence information, associated with a particular data item, to determine a particular source, of the plurality of sources, from which the particular data item was transmitted; computing, by the reordering engine and using another stage of the plurality of pipelined stages, an order for the particular data item relative to other data items transmitted by the particular source, based on a particular sequence number obtained from the particular sequence information; and storing, by the reorder engine and using a further stage of the plurality of pipelined stages, the particular sequence information in a context memory associated with the particular source based on the order computed for the particular data item. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15)
-
-
16. A system for reordering a plurality of out-of-order data items, received from a plurality of sources, to correspond to a transmitted order, the system comprising:
-
a plurality of sets of context memories associated with the plurality of sources, each of the plurality of sets of context memories storing information associated with a state of reordering of data items transmitted by one of the plurality of sources; and a reordering pipeline engine, that includes a plurality of sequential stages configured to interact with the plurality of sets of context memories, to; receive data items from the plurality of sources, each of the received data items including source identification information, identify a set of context memories, of the plurality of sets of context memories, for a particular data item, of the received data items, based on the source identification information obtained from the particular data item, reorder one or more of the received data items, using information obtained from the identified set of context memories associated with the one or more of the received data items, and update address information, in one or more of the plurality of sets of context memories, with other address information associated with the reordered one or more received data items, corresponding to a transmitted order of the one or more received data items. - View Dependent Claims (17, 18, 19, 20, 21, 22)
-
Specification