NETWORK ON CHIP WITH TASK QUEUES

• US 20170351555A1
• Filed: 06/03/2016
• Published: 12/07/2017
• Est. Priority Date: 06/03/2016
• Status: Abandoned Application

• Current Assignee: Friday Harbor LLC
• Original Assignee: Knuedge, Inc.
• Inventors: Coffin, Jerome Vincent
• Application Number:
  US15/173,017
• Publication Number:
  US 20170351555A1
• Time in Patent Office: Days
• CPC Class Codes: G06F 2209/548 Queue
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: G06F 9/54 Interprogram communication

Abstract

A network on a chip architecture uses hardware queues to distribute multiple-instruction tasks to processors dedicated to performing that task. By repeatedly using the same processors to perform the same task, the frequency at which the processors access memory to retrieve instructions is reduced. If a hardware queue runs dry and a processor is remains idle, the processor will determine which queues have tasks and rededicate to performing a new task that has higher demand, without requiring the intervention of centralized load balancing software or specialized programming.

Claims

1. A method comprising:

sending, by a first processing element to a first task distributor, a first task request to perform at least a first task, wherein;

the first task request comprises a first task identifier, a first return indicator, and first data,

the first task identifier identifies the first task,

the first return indicator indicates a location to return a first result, and

the first task is associated with a first plurality of executable instructions;

selecting, by the first task distributor, a first queue associated with the first task;

obtaining, by the first task distributor, a first address of the first queue;

enqueuing, by the first task distributor, the first return indicator and the first data into the first queue in accordance with the first address;

dequeuing, by a second processing element at a first time, the first return indicator and the first data from the first queue;

executing, by the second processing element at a second time, the first plurality of executable instructions using at least a portion of the first data to obtain the first result; and

returning, by the second processing element, the first result in accordance with the first return indicator.

2. The method of claim 1, further comprising:

loading, by the second processing element prior to the dequeuing, the first plurality of executable instructions.

3. The method of claim 1, wherein the location indicated by the first return indicator is a second address of a memory location, and returning the first result comprises writing the first result to the memory location.

4. The method of claim 1, wherein the location indicated by the first return indicator is a second address of a second queue, and returning the first result comprises enqueuing the first result in the second queue, the method further comprising:

dequeuing the first result from the second queue by the first processing element.

5. The method of claim 1, further comprising, prior to the first processing element sending the first task request:

sending, by a third processing element to a second task distributor, a second task request to perform a second task, wherein;

the second task request comprises a second task identifier, the first task identifier, the first return indicator, and second data, and

the second task is associated with a second plurality of executable instructions;

selecting, by the second task distributor, a second queue associated with the second task;

obtaining, by the second task distributor, a second address of the second queue;

enqueuing, by the second task distributor, the first task identifier, the first return indicator and the second data into the second queue in accordance with the second address;

dequeuing, by the first processing element, the first task identifier, the first return indicator, and the second data from the second queue; and

executing, by the first processing element, the second plurality of executable instruction using at least a portion of the second data to obtain a second result,

wherein the first data includes the second result.

6. The method of claim 1, wherein:

selecting the first queue comprises providing the first task identifier as input to a content-addressable memory (CAM), the content-addressable memory associating a plurality of task identifiers, including the first task identifier, with addresses of a plurality of queues, including the first address of the first queue; and

obtaining the first address comprises receiving the first address from the CAM.

7. The method of claim 1, wherein:

selecting the first queue comprises searching a stored table for the first task identifier, the stored table associating a plurality of task identifiers, including the first task identifier, with addresses of a plurality of queues, including the first address of the first queue; and

obtaining the first address comprises determining the first address associated with the first task identifier from the stored table.

8. The method of claim 1, wherein a combination of selecting the first queue and obtaining the first address comprises hashing the first task identifier using a distributed hash function to determine the first address.

9. The method of claim 1, wherein:

the first task identifier, the first return indicator, and the first data are sent by the first processing element to the first task distributor as a first payload of a first data packet,

the first return indicator and the first data are enqueued to the first queue by the first task distributor as a second payload of a second data packet, and

the first result is returned as a third payload of a third data packet.

10. The method of claim 1, further comprising:

waiting, by the second processing element, after the second time, for a second return indicator with second data to be available from the first queue;

determining, by the second processing element at a third time, that the waiting has exceeded a specified duration;

selecting, by the second processing element, a second queue associated with a second task, the second task associated with a second plurality of executable instructions;

loading, by the second processing element after selecting the second queue, the second plurality of instructions;

dequeuing, by the second processing element after loading the second plurality of instructions, a third return indicator and third data from the second queue;

executing, by the second processing element, the second plurality of instructions using at least a portion of the third data to obtain a second result; and

returning, by the second processing element, the second result in accordance with the third return indicator.

11. The method of claim 10, wherein:

the first queue and the second queue are of a plurality of queues, and

selecting the second queue comprises;

determining that at least one of the plurality of queues has a depth exceeding a threshold value; and

selecting the second queue based on the depth of the second queue being a largest or tied for the largest among the plurality of queues.

12. The method of claim 10, further comprising:

determining, by the second processing element, that at least one other processing element is subscribed to the first queue at the third time;

decrementing, after the second queue is selected, a first register associated with the first queue that indicate a first number of processing elements subscribed to the first queue; and

incrementing, after the second queue is selected, a second register associated with the second queue that indicates a second number of processing element subscribed to the second queue.

13. The method of claim 1, wherein the first processing element and the first task distributor are on a first semiconductor chip, the first queue and the second processing element are on a second semiconductor chip, and enqueuing the first return indicator and the first data into the first queue comprises inter-chip communications.

14. A system, comprising:

a first processor;

a first memory storing first executable instructions to be executed by the first processor, wherein;

the first executable instructions configure the first processor to send a first task request to a first task distributor,

the first task request comprises a first task identifier, a first return indicator, and first data,

the first return indicator indicates where to return a first result, and

a first task identified by the first task identifier is associated with execution of second executable instructions;

the first task distributor configured to identify a first queue associated with the first task identifier and enqueue the first return indicator and the first data in the first queue;

the first queue comprising a plurality of storage locations, the first queue configured to provide a data-available indication that indicates there is data enqueued in at least one of the plurality of storage location;

a second processor;

a second memory configured to store the second executable instructions to be executed by the second processor, wherein the second executable instructions configure the second processor to;

dequeue the first return indicator and the first data from the first queue in response to the data-available indication;

process at least a portion of the first data to obtain the first result; and

send the first result in accordance with a the first return indicator.

15. The system of claim 14, wherein:

the first processor and the first task distributor are on a first semiconductor chip, and

the first queue and the second processor are on a second semiconductor chip.

16. The system of claim 14, wherein the first task distributor comprises:

a parser configured to read a predetermined range of bits from the first task request to determine the first task identifier;

a content-addressable memory (CAM) configured to output the first address in response to receiving the first task identifier as input, the CAM containing an associative array that associates a plurality of task identifiers including the first task identifier with addresses of a plurality of queues including a first address of the first queue; and

an assembler configured to assemble and send a packet to the first queue in accordance with the first address, the packet comprising the first return indicator and the first data.

17. The system of claim 14, wherein the first task distributor comprises:

a parser configured to read a predetermined range of bits from the first task request to determine the first task identifier;

an address resolver configured to hash the first task identifier using a distributed hash function to determine the first address; and

an assembler configured to assemble and send a packet to the first queue in accordance with the first address, the packet comprising the first return indicator and the first data.

18. The system of claim 14, the second processor comprising a first timer, the second processor further configured to:

run the first timer and wait for another data-available indication from the first queue after the first result is sent;

determine, based on the first timer, that a duration that the second processor has waited has exceeded a specified duration;

select a second queue associated with a second task, wherein the second task is associated with execution of third executable instructions;

load the third executable instructions into the second memory, after the second queue is selected; and

execute the third executable instructions, to configure the second processor to;

dequeue a second return indicator and second data from the second queue;

processes at least a portion of the second data to obtain a second result; and

send the second result in accordance with the second return indicator.

19. The system of claim 18, wherein the first queue and the second queue are of a plurality of queues, and to select the second queue, the second processor is configured to:

determine that at least one of the plurality of queues has a depth exceeding a threshold value; and

select the second queue based on the depth of the second queue being a largest or tied for the largest among the plurality of queues.

20. The system of claim 18, wherein the second processor is configured to:

obtain a first value from a first register of the first queue indicating a first number of processors subscribed to the first queue;

determine from the first value that at least one other processor is subscribed to the first queue;

decrement first register after the second queue is selected; and

increment a second value in a second register of the second queue after the second queue is selected, the second value indicating a second number of processors subscribed to the second queue.

21. A method comprising:

sending, by a first processing element to a first task distributor, (i) a first task identifier and a first address where a first return indicator and first data are stored in memory, or (ii) a first address where the first task identifier, the first return indicator, and first data are stored in memory, wherein;

the first task identifier identifies a first task associated with execution of a first plurality of executable instructions, and

the first return indicator indicates a location to return a first result;

selecting, by the first task distributor, a first queue associated with the first task;

obtaining, by the first task distributor, a second address of the first queue;

enqueuing, by the first task distributor, the first address or an offset version of the first address into the first queue in accordance with the second address;

dequeuing, by a second processing element, the first address or the offset version of the first address from the first queue;

retrieving, by the second processing element, the first return indicator and the first data from memory based on the first address or the offset version of the first address;

executing, by the second processing element, the first plurality of executable instructions using at least a portion of the first data to obtain the first result; and

returning, by the second processing element, the first result in accordance with the first return indicator.

22. The method of claim 21, further comprising:

loading, by the second processing element prior to the dequeuing, the first plurality of executable instructions.