System and method for preserving order of data processed by processing engines

• US 9,817,773 B2
• Filed: 09/30/2015
• Issued: 11/14/2017
• Est. Priority Date: 10/02/2001
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.), Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Lim, Raymond Marcelino Manese, Dyckerhoff, Stefan, Libby, Jeffrey Glenn, Tesfaye, Teshager
• Primary Examiner(s): Lee, James J
• Application Number:
  US14/870,683
• Publication Number:
  US 20160019170A1
• Time in Patent Office: 776 Days
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 13/1626 by reordering requests
• CPC Class Codes: G06F 13/1663 Access to shared memory
• CPC Class Codes: G06F 13/4022 using switching circuits, e.g. switching matrix, connection or expansion network G06F13/4009 takes precedence
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: H04L 45/62 Wavelength based optical switching H04Q11/0062
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9094 Arrangements for simultaneous transmit and receive, e.g. simultaneous reading/writing from/to the storage element

Abstract

A device includes an input processing unit and an output processing unit. The input processing unit dispatches first data to one of a group of processing engines, records an identity of the one processing engine in a location in a first memory, reserves one or more corresponding locations in a second memory, causes the first data to be processed by the one processing engine, and stores the processed first data in one of the locations in the second memory. The output processing unit receives second data, assigns an entry address corresponding to a location in an output memory to the second data, transfers the second data and the entry address to one of a group of second processing engines, causes the second data to be processed by the second processing engine, and stores the processed second data to the location in the output memory.

Claims

1. A system for preserving an order of data, the system comprising:

a processor, comprising;

an arbiter to;

detect a dispatch of packet fields of a packet, the packet fields being dispatched to a processing engine, and

store an identifier of the processing engine in a first-in-first-out (FIFO) buffer within the arbiter; and

a reorder buffer to;

receive, from the processing engine, control information including information based on the packet fields,

receive a request, from the processing engine, to assign a reorder buffer location within the reorder buffer,

grant the request when the reorder buffer location is available,

send a memory pointer to the processing engine based on granting the request, the memory pointer corresponding to a FIFO buffer location of the identifier of the processing engine in the FIFO buffer within the arbiter,

store the control information at the reorder buffer location, and

transmit the control information out of the reorder buffer in a same order in which the packet fields were dispatched.

2. The system of claim 1, wherein, when storing the identifier of the processing engine in the FIFO buffer, the arbiter to:

store the identifier in a first-in-first-out manner.

3. The system of claim 1, wherein, when storing the identifier of the processing engine in the FIFO buffer, the arbiter to:

store the identifier in an order in which the packet fields are dispatched to the processing engine.

4. The system of claim 1, wherein, when granting the request to assign the reorder buffer location within the reorder buffer, the reorder buffer to:

assign the reorder buffer location in a first-in-first-out manner.

5. The system of claim 1, wherein, when granting the request to assign the reorder buffer location within the reorder buffer, the reorder buffer to:

grant the request based on an order in which the identifier is stored in the FIFO buffer.

6. The system of claim 1, wherein, when granting the request to assign the reorder buffer location within the reorder buffer, the reorder buffer to:

assign the reorder buffer location within the reorder buffer, the reorder buffer location corresponding to the FIFO buffer location within the FIFO buffer in which the identifier was stored.

7. A method for preserving an order of data, comprising:

detecting, by a processor, a dispatch of packet fields of a packet, the packet fields being dispatched to a processing engine;

storing, by the processor, an identifier of the processing engine in a first-in-first-out (FIFO) buffer within an arbiter;

receiving, by the processor and from the processing engine, control information including information based on the packet fields;

receiving, by the processor and from the processing engine, a request to assign a reorder buffer location within a reorder buffer;

granting, by the processor, the request when the reorder buffer location is available;

sending, by the processor, a memory pointer to the processing engine based on granting the request, the memory pointer corresponding to a FIFO buffer location of the identifier in the FIFO buffer within the arbiter;

storing, by the processor, the control information at the reorder buffer location; and

transmitting, by the processor, the control information out of the reorder buffer in a same order in which the packet fields were dispatched.

8. The method of claim 7, wherein storing the identifier in the FIFO buffer within the arbiter comprises:

storing the identifier in an order in which the packet fields are dispatched to the processing engine.

9. The method of claim 8, wherein granting the request comprises:

granting the request based on the order in which the identifier is stored in the FIFO buffer.

10. The method of claim 7, wherein granting the request comprises:

assigning the reorder buffer location within the reorder buffer corresponding to the FIFO buffer location in which the identifier was stored.

11. The method of claim 7, wherein granting the request comprises:

granting the request based on an order in which the packet fields are dispatched to the processing engine.

12. The method of claim 7, wherein storing the control information at the reorder buffer location within the reorder buffer comprises:

storing the control information at the reorder buffer location based on granting the request to assign the reorder buffer location.

13. A non-transitory computer-readable medium storing instructions for preserving an order of data, the instructions comprising:

one or more instructions that, when executed by one or more processors, cause the one or more processors to;

detect a dispatch of first packet fields of a packet, the first packet fields being dispatched to a first processing engine;

store a first identifier in a first-in-first-out (FIFO) buffer within an arbiter, the first identifier identifying the first processing engine;

receive, from the first processing engine, first control information including information based on the first packet fields;

receive, from the first processing engine, a first request to assign a reorder buffer location within a reorder buffer;

grant the first request when the reorder buffer location is available;

send a memory pointer to the first processing engine based on granting the first request, the memory pointer corresponding to a FIFO buffer location of the first identifier in the FIFO buffer within the arbiter;

store the first control information at the reorder buffer location; and

transmit the first control information out of the reorder buffer in a same order in which the first packet fields were dispatched.

14. The non-transitory computer-readable medium of claim 13, wherein the one or more instructions, to store the first identifier in the FIFO buffer, cause the one or more processors to:

store the first identifier in an order in which the first packet fields are dispatched to the first processing engine.

15. The non-transitory computer-readable medium of claim 13, wherein the one or more instructions, to grant the first request, cause the one or more processors to:

grant the first request based on an order in which the first packet fields are dispatched to the first processing engine.

16. The non-transitory computer-readable medium of claim 13, wherein the one or more instructions further cause the one or more processors to:

detect a dispatch of second packet fields of the packet, the second packet fields being dispatched to a second processing engine;

determine whether the second packet fields were dispatched before the first packet fields were dispatched;

receive, from the second processing engine, a second request to assign the reorder buffer location; and

grant the second request when the second packet fields were dispatched before the first packet fields were dispatched.

17. The non-transitory computer-readable medium of claim 16, wherein the one or more instructions further cause the one or more processors to:

selectively store a second identifier in the FIFO buffer, the second identifier identifying the second processing engine, and selectively storing comprising;

storing the second identifier before storing the first identifier when the second packet fields were dispatched before the first packet fields were dispatched, and

storing the first identifier before storing the second identifier when the second packet fields were not dispatched before the first packet fields were dispatched.

18. The non-transitory computer-readable medium of claim 16, wherein the one or more instructions further cause the one or more processors to:

receive, from the second processing engine, second control information; and

store the second control information at the reorder buffer location,

storing the second control information at the reorder buffer location when the second packet fields were dispatched before the first packet fields were dispatched.