TASK QUEUING IN A NETWORK COMMUNICATIONS PROCESSOR ARCHITECTURE

• US 20100293353A1
• Filed: 05/18/2010
• Published: 11/18/2010
• Est. Priority Date: 05/18/2009
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: LSI Corporation (Broadcom, Inc.)
• Inventors: Sundararaman, Balakrishnan, Aulakh, Shailendra, Sonnier, David P., Mital, Deepak
• Granted Patent: US 8,407,707 B2
• Time in Patent Office: Days
• US Class Current: 711/170
• 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, comprising the steps of:

sending, by a source processing core, a new task having an identifier;

receiving, by a destination processing core, the new task;

determining, by the destination processing core, if another task having the same identifier exists in any of the plurality of queues;

assigning, if the another task with the same identifier as the new task exists, the new task to the queue containing a task with the same identifier as the new task;

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

writing, by the source processing core, the new task to the assigned queue; and

executing the new task by the destination processing core.

2. The method of claim 1, wherein the task 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 task 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 associated with a processing core, comprising the steps of:

sending, by a source processing core, a new task having an identifier;

receiving, by a destination processing core, the new task;

determining, by the processing core, if another task having the same identifier exists in any of a plurality of queues;

assigning, if the another task with the same identifier as the new task exists, the new task to the queue containing a task with the same identifier as the new task;

assigning, if the another task with the same identifier as the new task does not exist, the new task to the queue having the smallest size;

writing, by the source processing core, the new task to the assigned queue; and

executing the tasks in a queue 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 task 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 task 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;

a common memory adapted for direct communication with each of the processing cores;

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

i) a source processing core adapted to send a new task message having an identifier to a receiving processing core adjacent thereto on the common communication bus, and ii) a destination processing core if the task message is intended for the receiving processing core,

wherein the destination processing core is adapted to i) determine if another task having the same identifier as the new task message exists in any of a plurality of queues, ii) assign, if the another task with the same identifier as the new task message exists, the new task message to the queue containing a task message with the same identifier, otherwise, assign the new task message to a least loaded one of the plurality of queues, and iii) execute the task messages in the queue; and

wherein the source processing core is adapted to write the new task to the assigned queue.

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.