MULTI-PROCESSING SYSTEM AND A METHOD OF EXECUTING A PLURALITY OF DATA PROCESSING TASKS

• US 20100115168A1
• Filed: 05/14/2007
• Published: 05/06/2010
• Est. Priority Date: 05/17/2006
• Status: Active Grant

• Current Assignee: NXP B.V. (NXP Semiconductors NV)
• Original Assignee: NXP B.V. (NXP Semiconductors NV)
• Inventors: Bekooij, Marco J.G.
• Granted Patent: US 8,065,459 B2
• Time in Patent Office: Days
• US Class Current: 710/244
• CPC Class Codes: G06F 9/48 Program initiating; Program switching, e.g. by interrupt

Abstract

A plurality of data processing tasks with processing elements (10) that contend for a resource (18). Execution of each task comprising executing a series of instructions. During execution indications are measured of the speed of progress of executing the instructions for respective ones of the tasks. Requests to access the resource (18) for different ones of the tasks are arbitrated, a priority for judging arbitration being assigned to each task based on the measured indication of the speed of progress of the task. At least over a part of a range of possible speed of progress values increasingly higher priority is assigned in case of increasingly lower indication of the speed of progress.

Claims

1. A multi-processor circuit, comprising

a plurality of processing elements each configured to execute at least a respective task comprising execution of a series of instructions;

a shared resource coupled to the plurality of processing elements;

an arbitration circuit coupled to the processing elements and configured to arbitrate conflicting access requests to the shared resource from the plurality of processing elements dependent on priorities assigned to the processing elements;

priority setting circuitry configured to measure an indication of a speed of progress of execution of respective ones of the tasks and to set the priority for each processing element that executes a particular one of the tasks dependent on the measured indication of the speed of progress of execution of the series of instructions of the particular one of the tasks.

2. A multi-processor circuit according to claim 1, wherein the priority setting circuitry is configured to determine the indication of the speed of progress of the particular one of the tasks at a particular one of the instructions in the particular one of the tasks dependent on a count of instruction execution cycles that have occurred before reaching said particular one of the instructions from a reference instruction execution cycle that has a predetermined relation to a start of execution of the particular one of the tasks.

3. A multi-processor circuit according to claim 2, wherein the priority setting circuitry is configured to determine the indication of the speed of progress achieved at the particular one of the instructions relative to a nominally expected indication of the speed of progress up to the particular one of the instructions and setting priority of the particular one of the tasks at the particular one of the instructions increasingly higher when said indication of the speed of progress is increasingly lower relative to the nominally expected indication of the speed of progress, at least over a part of a range of possible indication values.

4. A multi-processor circuit according to claim 2, wherein the priority setting circuitry is configured to count a number of instruction stalls or execution cycles lost between the reference instruction cycle and execution of the particular one of the instructions and using the counted number of instruction stalls to determine the indication of the speed of progress to set the priority.

5. A multi-processor circuit according to claim 2, wherein the priority setting circuitry is configured to selectively count a number of instruction stalls due to loss of arbitration or execution cycles lost to such stalls between the reference instruction cycle and execution of the particular one of the instructions and using the counted number of instruction stalls to determine the indication of the speed of progress to set the priority.

6. A multi-processor circuit according to claim 5, wherein the priority setting circuitry is configured to increase the priority at the particular one of the instructions of the task with increasing difference between the counted number of instruction stalls or lost execution cycles and a predetermined fraction of the number of instruction cycles used to reach said particular one of the instructions, at least over a part of a range of possible difference values.

7. A multi-processor circuit according to claim 2, wherein the processing elements are configured to maintain a first in first out input buffer for input tokens and a first in first out output buffer for output tokens, the processing elements being configured to execute the particular one of the tasks repeatedly, each execution consuming a successive input token from the input buffer and producing a successive output token in the output buffer, the processing elements being configured to trigger the start of execution of the particular one of the tasks when the input token for the particular one of the tasks is stored in its input buffer and there is space for storing the output token in the output buffer.

8. A multi-processor circuit according to claim 1, comprising a shared main memory, the shared resource comprising the shared main memory, each processing element comprising a respective cache memory coupled to the shared main memory for caching data from the shared main memory, priority setting circuitry being configured to compute the indication of the speed of progress by counting stalls due to access conflicts arising upon cache misses.

9. A method of executing a plurality of data processing tasks with processing elements that contend for a resource, execution of each task comprising executing a series of instructions, the method comprising

measuring indications of the speed of progress of executing the instructions for respective ones of the tasks;

arbitrating requests to access the resource for different ones of the tasks, a priority for judging arbitration being assigned to each task based on the measured indication of the speed of progress of the task, increasingly higher priority being assigned in case of increasingly lower indication of the speed of progress, at least over a part of a range of possible speed of progress values.

10. A method according to claim 9, wherein execution of each task comprises executing successive instructions of that task, the indication of the speed of progress of the task at a particular one of the instructions being determined dependent on a number of instruction cycles that have occurred before reaching said particular instruction from a reference instruction cycle that has a predetermined relation to a start of execution of the task.

11. A method according to claim 10, the method comprising determining the indication of the progress achieved at the particular one of the instructions relative to a nominally speed of expected indication of the speed of progress up to the particular one of the instructions and setting the priority of the task at the particular one of the instructions of the task higher when said indication of the speed of progress is lower relative to the nominally expected indication of the speed of progress.

12. A method according to claim 10, the method comprising counting a number of instruction stalls or lost instruction cycles between the reference instruction cycle and execution of the particular one of the instructions and using the counted number of instruction stalls or lost instruction cycles to set the priority of the task at the particular one of the instructions.

13. A method according to claim 10, the method comprising selectively counting a number of instruction stalls or instruction cycles lost due to loss of said arbitration between the reference instruction cycle and execution of the particular one of the instructions and using the counted number of instruction stalls or lost instruction cycles to set the priority of the task at the particular one of the instructions.

14. A method according to claim 12, the method comprising increasing the priority of the task at the particular one of the instructions based on increasing difference between the counted number of instruction stalls and a predetermined fraction of the number of instruction cycles used to reach said particular instruction, at least over a part of a range of possible difference values.

15. A method according to claim 10, comprising

maintaining a first in first out input buffer for input tokens and a first in first out output buffer for output tokens for each of the tasks, the output buffers for at least a first part of the tasks being input buffers for at least a second part of the tasks;

executing the particular one of the tasks repeatedly, each execution consuming a successive input token from the input buffer and producing a successive output token in the output buffer;

triggering the start of execution of the particular one of the tasks when the input token for the particular one of the tasks is stored in its input buffer and there is space for storing the output token in the output buffer.