Task queuing in a network communications processor architecture

• US 8,407,707 B2
• Filed: 05/18/2010
• Issued: 03/26/2013
• Est. Priority Date: 05/18/2009
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: LSI Corporation (Broadcom, Inc.)
• Inventors: Sonnier, David P., Sundararaman, Balakrishnan, Aulakh, Shailendra, Mital, Deepak
• Primary Examiner(s): MANSFIELD, THOMAS L
• Application Number:
  US12/782,411
• Publication Number:
  US 20100293353A1
• Time in Patent Office: 1,043 Days
• Field of Search: 718100-108
• US Class Current: 718/101
• CPC Class Codes: G06F 15/167 using a common memory, e.g. mailbox
• 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

Abstract

Described embodiments provide a method of assigning tasks to queues of a processing core. Tasks are assigned to a queue by sending, by a source processing core, a new task having a task identifier. A destination processing core receives the new task and determines whether another task having the same identifier exists in any of the queues corresponding to the destination processing core. If another task with the same identifier as the new task exists, the destination processing core assigns the new task to the queue containing a task with the same identifier as the new task. If no task with the same identifier as the new task exists in the queues, the destination processing core assigns the new task to the queue having the fewest tasks. The source processing core writes the new task to the assigned queue. The destination processing core executes the tasks in its queues.

Claims

1. A method of assigning tasks to a plurality of queues of a processing core of a network processor having a plurality of processing cores and a shared memory comprising a plurality of addressable memory arrays, the processing cores coupled to at least one unidirectional ring bus, the method comprising:

sending, by a source one of the plurality of processing cores, a task over the at least one unidirectional ring bus to an adjacent processing core coupled to the ring bus, the task having a corresponding one or more destination processing cores and a corresponding flow identifier;

iteratively;

checking, by the adjacent processing core, whether the processing core is a destination processing core for the task and, if not, passing the task unchanged to a next adjacent processing core coupled to the ring bus, thereby passing the task from the source processing core to each corresponding destination processing core on the ring bus;

receiving, by the corresponding one or more destination processing cores, the task;

determining, by the destination processing core, (i) if another task having the same flow identifier as the received task exists in any of the plurality of queues, and (ii) a logical address in the shared memory of data corresponding to the task;

computing, by the destination processing core, a hash value based on at least a part of the logical address;

assigning, if the another task with the same flow identifier exists, the received task to the queue containing a task with the same flow identifier;

assigning, if the another task with the same flow identifier does not exist in the plurality of queues, the received task to the queue with the fewest number of tasks therein;

selecting, by the destination processing core, one of the plurality of addressable memory arrays in which to store the assigned queue based on the hash value;

writing, by the source processing core, the received task to the assigned queue in the selected addressable memory array; and

executing the received task by the destination processing core.

2. The method of claim 1, wherein the flow identifier is related to at least one of a source of the task, a session number associated with the task, a data source address, and a data destination address.

3. The method of claim 1, wherein the flow identifier is a hashed value of at least one of a source of the task, a session number associated with the task, a data source address, and a data destination address.

4. The method of claim 1, wherein each of the queues in the plurality of queues is stored in a memory comprised of one or more memory blocks, the size of a queue is the number of memory blocks in a queue.

5. The method of claim 4, further comprising the step of:

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

6. The method of claim 4, wherein the one or more memory blocks comprises a plurality of memory blocks that are linked, one memory block of the plurality of memory blocks having a address of a subsequent one of the plurality of memory blocks.

7. The method of claim 6, further comprising:

writing, by the source processing core, a memory address of a subsequent one of the plurality of memory blocks at the end of a prior one of the plurality of memory blocks.

8. The method of claim 1, wherein each of the plurality of queues are first-in-first-out queues.

9. The method of claim 1, wherein the method is implemented by a machine executing program code encoded on a non-transitory machine-readable storage medium.

10. A method of assigning tasks to a plurality of queues of a processing core of a network processor having a plurality of processing cores and a shared memory comprising a plurality of addressable memory arrays, the processing cores coupled to at least one unidirectional ring bus, the method comprising:

sending, by a source one of the plurality of processing cores, a task over the at least one unidirectional ring bus to an adjacent processing core coupled to the ring bus, the task having a corresponding one or more destination processing cores and a corresponding flow identifier;

iteratively;

checking, by the adjacent processing core, whether the processing core is a destination processing core for the task and, if not, passing the task unchanged to a next adjacent processing core coupled to the ring bus, thereby passing the task from the source processing core to each corresponding destination processing core on the ring bus;

receiving, by the corresponding one or more destination processing cores, the task;

determining, by the destination processing core, (i) another task having the same flow identifier as the received task exists in any of the plurality of queues, and (ii) a logical address in the shared memory of data corresponding to the task;

computing, by the destination processing core, a hash value based on at least a part of the logical address;

assigning, if the another task with the same flow identifier exists, the received task to the queue containing a task with the same flow identifier;

assigning, if the another task with the same flow identifier does not exist in the plurality of queues, the received task to the queue with the fewest number of tasks therein;

selecting, by the destination processing core, one of the plurality of addressable memory arrays in which to store the assigned queue based on the hash value;

writing, by the source processing core, the received task to the assigned queue in the selected addressable memory array; and

executing the received task by the destination processing core.

11. The method of claim 10, wherein each of the queues in the plurality of queues is stored in a memory comprised of one or more memory blocks, the size of a queue is the number of memory blocks in a queue.

12. The method of claim 11, further comprising the step of:

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

13. The method of claim 11, wherein the one or more memory blocks comprise a plurality of memory blocks that are linked, one memory block of the plurality of memory blocks having a address of a subsequent one of the plurality of memory blocks.

14. The method of claim 13, further comprising:

writing, by the source processing core, a memory address of a subsequent one of the plurality of memory blocks at the end of a prior one of the plurality of memory blocks.

15. The method of claim 10, wherein each of the queues in the plurality of queues is stored in a memory, each queue having a read pointer and a write pointer associated therewith and each pointer having a value, and wherein the size of a queue is a difference between the read pointer value and the write pointer value.

16. The method of claim 15, wherein the step of executing the tasks in the queue comprises:

reading the task pointed to by the read pointer;

and wherein the step of writing the new task comprises;

writing the new task in the queue at the location specified by the write pointer; and

updating the write pointer to a next location in the queue for a task.

17. The method of claim 15, wherein at least one of the queues have associated therewith a written pointer, the written pointer indicating a location in the queue between the read pointer and the write pointer, inclusive, that, when the written pointer does not equal the write pointer, at least one gap exists in the queue.

18. The method of claim 17, wherein the step of reading the task in a queue continues until the read pointer equals the written pointer, the written pointer being set to equal the write pointer when the gap is eliminated.

19. The method of claim 10, wherein the flow identifier is related to at least one of a source of the task, a session number associated with the task, a data source address, and a data destination address.

20. The method of claim 10, wherein the flow identifier is a hashed value of at least one of a source of the task, a session number associated with the task, a data source address, and a data destination address.

21. The method of claim 10, wherein the method is implemented by a machine executing program code encoded on a non-transitory machine-readable storage medium.

22. A network processor comprising:

a plurality of processing cores coupled to a common communication bus, wherein the common communication bus comprises one or more unidirectional ring buses, each ring bus coupled between two adjacent processing cores, and wherein the plurality of processing cores comprise at least one of dedicated hardware accelerator engines and a microprocessor core;

a common memory adapted for direct communication with each of the processing cores and comprising a plurality of addressable memory arrays;

each of the processing cores adapted to function as one of;

(i) a source processing core adapted to send a new task over the at least one unidirectional ring bus to an adjacent processing core coupled to the ring bus, the task having a flow identifier and a corresponding one or more destination processing cores, (ii) a task passing processing core, wherein the processing core is configured to check whether the processing core is a destination processing core for the task and, if not, pass the task unchanged to a next adjacent processing core coupled to the ring bus, thereby passing the task from the source processing core to each corresponding destination processing core on the ring bus, and (iii) a destination processing core if the task is intended for the processing core,

wherein the destination processing core is adapted to (i) determine if another task having the same flow identifier as the new task exists in any of a plurality of queues, (ii) determine a logical address in the common memory of data corresponding to the task, (iii) compute a hash value based on at least a part of the logical address;

(iv) assign, if the another task with the same flow identifier as the new task exists, the new task to the queue containing a task message with the same flow identifier, otherwise, assign the new task to a least loaded one of the plurality of queues, (v) select one of the plurality of addressable memory arrays in which to store the assigned queue based on the hash value, and (vi) execute the tasks in the queue; and

wherein the source processing core is adapted to write the new task to the assigned queue in the selected addressable memory array.

23. The network processor of claim 22, wherein the destination processing core is further adapted to determine the least loaded one of the plurality of queues based on a number of task message entries in each queue.

24. The network processor of claim 22, wherein the destination processing core is further adapted to determine the least loaded one of the plurality of queues based on a number of memory blocks allocated to each queue.

25. The network processor of claim 22, wherein the network processor is implemented in a monolithic integrated circuit chip.