Task Backpressure and Deletion in a Multi-Flow Network Processor Architecture

• US 20130125127A1
• Filed: 11/28/2012
• Published: 05/16/2013
• Est. Priority Date: 04/27/2009
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: LSI Corporation (Broadcom, Inc.)
• Inventors: Mital, Deepak, Burroughs, William, Betker, Michael R.
• Granted Patent: US 8,910,168 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 2209/509 Offload
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: G06F 9/4856 resumption being on a different machine, e.g. task migration, virtual machine migration G06F9/5088 takes precedence
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 49/101 using crossbar or matrix
• CPC Class Codes: H04L 49/109 Integrated on microchip, e.g. switch-on-chip
• CPC Class Codes: H04L 49/506 Backpressure
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Described embodiments generate tasks corresponding to packets received by a network processor. A source processing module sends task messages including a task identifier and a task size to a destination processing module. The destination module receives the task message and determines a queue in which to store the task. Based on a used cache counter of the queue and a number of cache lines for the received task, the destination module determines whether the queue has reached a usage threshold. If the queue has reached the threshold, the destination module sends a backpressure message to the source module. Otherwise, if the queue has not reached the threshold, the destination module accepts the received task, stores data of the received task in the queue, increments the used cache counter for the queue corresponding to the number of cache lines for the received task, and processes the received task.

Claims

1. A method of processing a received packet of a network processor, wherein the network processor comprises a plurality of processing modules and at least one shared memory, the method comprising:

generating one or more tasks corresponding to each received packet;

sending, by a source processing module, a task message corresponding to a task to a destination processing module, the task message comprising a task identifier and a task size;

receiving, by the destination processing module, the task message;

determining, by the destination processing module, (i) an associated one of a plurality of task queues of the destination processing module in which to store the task, and (ii) based on (1) a used cache counter of the destination processing module associated with the associated task queue and (2) a number of cache lines required for the received task, whether the associated task queue has reached a usage threshold;

if the associated task queue has reached the usage threshold;

sending a backpressure message to the source processing module;

otherwise, if the associated task queue has not reached the usage threshold;

accepting the received task and storing data associated with the received task in the associated task queue;

incrementing the used cache counter for the associated task queue corresponding to the number of cache lines required for the received task; and

processing, by the destination processing module, the received task.

2. The method of claim 1, further comprising:

when the step of processing the received task completes, decrementing the used cache counter for the associated task queue corresponding to the number of cache lines for the completed task.

3. The method of claim 1, wherein each queue comprises one or more memory blocks in the at least one shared memory, the method further comprising:

determining, by the destination processing module whether the received task is larger than space available within a current memory block of the associated queue;

if the task is larger than space available within a current memory block of the associated queue;

determining an address of a next memory block in the at least one shared memory for the associated queue, and providing the address of the next memory block to the source processing module;

providing an offset address within the current memory block of the associated queue to the source processing module;

writing, by the source processing module, the task to the at least one shared memory based on at least one of the provided offset address and the address of the next memory block, if provided;

if a task is written to more than one memory block of the associated queue;

preloading, by the destination processing module, the address of the next memory block to a local memory of the destination processing module; and

processing, by the destination processing module, queued tasks without stalling to retrieve the address of the next memory block from the at least one shared memory.

4. The method of claim 3, further comprising:

writing, by the source processing module, the address of the next memory block as a link address in a previous memory block of the associated queue.

5. The method of claim 4, further comprising:

writing, by the source processing module, the link address at the end of the previous memory block.

6. The method of claim 4, wherein, for the method, each memory block is 2KB, each task is 256B and each link address is 16B.

7. The method of claim 6, further comprising:

writing the link address after byte 240 in the 2KB memory block.

8. The method of claim 3, further comprising:

allocating, by a memory manager of the network processor, one or more additional memory blocks to a queue to store additional new tasks.

9. The method of claim 1, further comprising:

sending tasks and task requests between processing modules over one or more unidirectional ring buses, each ring bus coupled between two adjacent processing modules.

10. The method of claim 9, further comprising:

determining, by each processing module, if the processing module is an associated destination processing module for a received task message and, if so;

the processing module processes the task message;

otherwise, the processing module passes the task message unchanged to an adjacent one of the ring-coupled processing cores.

11. The method of claim 10, wherein each task comprises at least one of:

(i) pointers to data stored in the at least one memory, (ii) inline data corresponding to the task message, (iii) control data corresponding to the task message, and (iv) a flow identifier corresponding to the task.

12. The method of claim 11, further comprising:

determining, based on the flow identifier, a processing order for each task through one or more of the plurality of processing modules of the network processor.

13. The method of claim 12, wherein the processing modules comprise at least one of a programmable processor and a dedicated hardware accelerator.

14. A non-transitory machine-readable medium, having encoded thereon program code, wherein, when the program code is executed by a machine, the machine implements a method of processing a received packet of a network processor, wherein the network processor comprises a plurality of processing modules and at least one shared memory, the method comprising:

generating one or more tasks corresponding to each received packet;

sending, by a source processing module, a task message corresponding to a task to a destination processing module, the task message comprising a task identifier and a task size;

receiving, by the destination processing module, the task message;

determining, by the destination processing module, (i) an associated one of a plurality of task queues of the destination processing module in which to store the task, and (ii) based on (1) a used cache counter of the destination processing module associated with the associated task queue and (2) a number of cache lines required for the received task, whether the associated task queue has reached a usage threshold;

if the associated task queue has reached the usage threshold;

sending a backpressure message to the source processing module;

otherwise, if the associated task queue has not reached the usage threshold;

accepting the received task and storing data associated with the received task in the associated task queue;

incrementing the used cache counter for the associated task queue corresponding to the number of cache lines required for the received task; and

processing, by the destination processing module, the received task.

15. The non-transitory machine-readable medium of claim 14, wherein each queue comprises one or more memory blocks in the at least one shared memory, the method further comprising:

determining, by the destination processing module whether the received task is larger than space available within a current memory block of the associated queue;

if the task is larger than space available within a current memory block of the associated queue;

determining an address of a next memory block in the at least one shared memory for the associated queue, and providing the address of the next memory block to the source processing module;

providing an offset address within the current memory block of the associated queue to the source processing module;

writing, by the source processing module, the task to the at least one shared memory based on at least one of the provided offset address and the address of the next memory block, if provided;

if a task is written to more than one memory block of the associated queue;

preloading, by the destination processing module, the address of the next memory block to a local memory of the destination processing module; and

processing, by the destination processing module, queued tasks without stalling to retrieve the address of the next memory block from the at least one shared memory.

16. A network processor comprising:

a plurality of processing modules and at least one shared memory, one or more of the processing modules configured to generate one or more tasks corresponding to each of a plurality of packets received by the network processor;

a source processing module configured to send a task message corresponding to a task to a destination processing module, the task message comprising a task identifier and a task size;

the destination processing module configured to (i) receive the task message and (ii) determine. (a) an associated one of a plurality of task queues of the destination processing module in which to store the task, and (b) based on (1) a used cache counter of the destination processing module associated with the associated task queue and (2) a number of cache lines required for the received task, whether the associated task queue has reached a usage threshold;

if the associated task queue has reached the usage threshold;

the destination processing module is configured to send a backpressure message to the source processing module;

otherwise, if the associated task queue has not reached the usage threshold;

the destination processing module is configured to;

(i) accept the received task, (ii) store data associated with the received task in the associated task queue, (iii) increment the used cache counter for the associated task queue corresponding to the number of cache lines required for the received task, and (iv) process the received task.

17. The network processor of claim 16, wherein:

each queue comprises one or more memory blocks in the at least one shared memory;

the destination processing module is further configured to;

determine whether the received task is larger than space available within a current memory block of the associated queue;

if the task is larger than space available within a current memory block of the associated queue;

determine an address of a next memory block in the at least one shared memory for the associated queue, and provide the address of the next memory block to the source processing module;

provide an offset address within the current memory block of the associated queue to the source processing module, wherein the source processing module is configured to write the task to the at least one shared memory based on at least one of the provided offset address and the address of the next memory block, if provided;

if a task is written to more than one memory block of the associated queue, the destination processing module is configured to;

preload the address of the next memory block to a local memory of the destination processing module; and

process queued tasks without stalling to retrieve the address of the next memory block from the at least one shared memory.

18. The network processor of claim 16, wherein each processing module is configured to:

send tasks and task requests between processing modules over one or more unidirectional ring buses, each ring bus coupled between two adjacent processing modules, wherein each task comprises at least one of;

(i) pointers to data stored in the at least one memory, (ii) inline data corresponding to the task message, (iii) control data corresponding to the task message, and (iv) a flow identifier corresponding to the task;

determine, based on the flow identifier, a processing order for each task through one or more of the plurality of processing modules of the network processor;

determine if the processing module is an associated destination processing module for a received task message and, if so, process the task message;

otherwise, pass the task message unchanged to an adjacent one of the ring-coupled processing cores.

19. The network processor of claim 16, wherein the processing modules comprise at least one of a programmable processor and a dedicated hardware accelerator.

20. The network processor of claim 16, wherein the network processor is implemented in an integrated circuit chip.