Thread execution scheduler for multi-processing system and method
A processing system includes a plurality of processors capable of executing a plurality of threads and supporting at least one of hardware context switching and software context switching. The processing system also includes at least one hardware scheduler capable of scheduling execution of the plurality of threads by the plurality of processors. The at least one hardware scheduler is capable of scheduling execution of the threads by performing instruction-by-instruction scheduling of the threads.
1. A processing system, comprising:
a plurality of processors configured to execute a plurality of threads and supporting at least one of hardware context switching and software context switching; and
at least one hardware scheduler configured to schedule execution of the plurality of threads by the plurality of processors by performing instruction-by-instruction scheduling of the threads, the execution schedule based on a dynamic priority for each thread, wherein the at least one hardware scheduler is configured to determine the dynamic priority for each thread by adding a static component of the dynamic priority for the thread to a quotient of an amount of work to be done by the thread divided by an amount of time from a deadline for each thread.
2. The processing system of claim 1 , wherein the at least one hardware scheduler is configured to schedule execution of the plurality of threads using at least one of: round robin scheduling, priority scheduling, and priority scheduling using round robin scheduling within a priority.
3. The processing system of claim 1 , wherein the at least one hardware scheduler is configured to dynamically change thread scheduling parameters using dynamically measured system parameters, the system parameters comprising at least one of: a power usage of at least one component of the processing system, a quality of service measurement, execution progress for each thread, resource usage for each thread, an estimated number of instructions to completion for each thread, a required completion time for each thread, and a current system time.
4. The processing system of claim 1 , wherein the at least one scheduler is configured to determine the dynamic priority for each thread using a formula of:
P
t
=
P
t0
+
K
·
W
td
D
,
where P t represents the dynamic priority for a particular thread, P t0 represents the static component of the dynamic priority, K represents a constant, W td represents the amount of work to be done by the thread, and D represents the amount of time from the deadline for the thread.
5. The processing system of claim 4 , wherein:
the amount of work to be done by the thread is determined as a difference between an estimated total number of instructions for the thread to do the work and a number of instructions actually executed by the thread; and
the amount of time from the deadline is determined as a difference between a value of a system clock when the thread must be completed and a current value of the system clock.
6. The processing system of claim 1 , further comprising a hardware concurrency engine configured to manage a plurality of concurrency primitives that coordinate execution of the threads by the processors.
7. The processing system of claim 6 , wherein the at least one scheduler is configured to determine the dynamic priority for each thread using a formula of:
P
t
=
P
t0
+
K
·
W
td
D
+
Y
t
,
where P t represents the dynamic priority for a particular thread, P t0 represents the static component of the dynamic priority, K represents a constant, W td represents the amount of work to be done by the thread, D represents the amount of time from the deadline for the thread, and Y t represents a value from the concurrency engine.
8. The processing system of claim 7 , wherein the value of Y t is based on at least one of: a concurrency semantic enforced by the concurrency engine, a power usage of at least one component of the processing system, a quality of service measurement, execution progress for at least one thread, resource usage for at least one thread, an estimated number of instructions to completion for at least one thread, a required completion time for at least one thread, and a current system time.
9. The processing system of claim 1 , wherein:
the at least one hardware scheduler comprises a hardware scheduler disposed in one of the processors;
the processing system further comprises at least one memory, at least one programmable hardware processing engine, at least one interface to an external device, and a network coupling the processors, the memory, the hardware processing engine, and the interface; and
the processors, the memory, the hardware processing engine, the interface, and the network comprise a system on a chip.
10. The processing system of claim 1 , wherein the at least one hardware scheduler is configured to schedule execution of the plurality of threads by at least one of:
initiating a context switch every clock cycle; and
initiating a context switch when an instruction from one of the threads is determined to have an associated latency.
11. The processing system of claim 1 , wherein at least one of the processors comprises a dedicated register set for each thread executed by the processor, the dedicated register set for a particular thread storing a priority associated with the particular thread.
12. The processing system of claim 1 , wherein the plurality of processors comprises homogenous processors in a symmetric multi-processing arrangement.
13. A method, comprising:
executing a plurality of threads using at least one processor; and
scheduling execution of the plurality of threads by the at least one processor using at least one hardware scheduler, the scheduling based on a dynamic priority for each thread, the dynamic priority for each thread determined by adding a static component of the dynamic priority for the thread to a quotient of an amount of work to be done by the thread divided by an amount of time from a deadline for each thread.
14. The method of claim 13 , wherein scheduling execution of the plurality of threads comprises scheduling execution of the plurality of threads using at least one of: round robin scheduling, priority scheduling, and priority scheduling using round robin scheduling within a priority.
15. The method of claim 13 , wherein scheduling execution of the plurality of threads comprises dynamically changing thread scheduling parameters using dynamically measured system parameters, the system parameters comprising at least one of: a power usage of the processors, a quality of service measurement, execution progress for each thread, resource usage for each thread, an estimated number of instructions to completion for each thread, a required completion time for each thread, and a current system time.
16. The method of claim 13 , wherein scheduling execution of the plurality of threads comprises determining the dynamic priority for each thread using a formula of:
P
t
=
P
t0
+
K
·
W
td
D
,
where P t represents the dynamic priority for a particular thread, P t0 represents the static component of the dynamic priority, K represents a constant, W td represents the amount of work to be done by the thread, and D represents the amount of time from the deadline for the thread.
17. The method of claim 13 , further comprising managing a plurality of concurrency primitives that coordinate execution of the threads by the processors using a hardware concurrency engine; and
wherein scheduling execution of the plurality of threads comprises determining the dynamic priority for each thread using a formula of:
P
t
=
P
t0
+
K
·
W
td
D
+
Y
t
,
where P t represents the dynamic priority for a particular thread, P t0 represents the static component of the dynamic priority, K represents a constant, W td represents the amount of work to be done by the thread, D represents the amount of time from the deadline for the thread, and Y t represents a value from the concurrency engine.
18. The method of claim 13 , further comprising storing a priority for a particular thread in a dedicated register set associated with the particular thread;
wherein scheduling execution of the plurality of threads comprises using the priority stored in the dedicated register set.
19. The method of claim 13 , wherein scheduling execution of the plurality of threads comprises at least one of:
initiating a context switch every clock cycle; and
initiating a context switch when an instruction from one of the threads is determined to have an associated latency.
20. A processor, comprising:
a plurality of pipeline stages collectively configured to execute a plurality of instructions from a plurality of threads;
a memory configured to store the instructions; and
a hardware scheduler configured to schedule execution of the instructions from the plurality of threads by the pipeline stages, the execution schedule based on a dynamic priority for each thread, wherein the hardware scheduler is configured to determine the dynamic priority for each thread by adding a static component of the dynamic priority for the thread to a quotient of an amount of work to be done by the thread divided by an amount of time from a deadline for each thread.
21. The processor of claim 20 , wherein the scheduler is configured to schedule execution of the plurality of threads by determining the dynamic priority for each thread using a formula of:
P
t
=
P
t0
+
K
·
W
td
D
,
where P t represents the dynamic priority for a particular thread, P t0 represents the static component of the dynamic priority, K represents a constant, W td represents the amount of work to be done by the thread, and D represents the amount of time from the deadline for the thread.
22. The processor of claim 20 , further comprising a hardware concurrency engine configured to manage a plurality of concurrency primitives that coordinate execution of a plurality of processors;
wherein the scheduler is configured to schedule execution of the plurality of threads by determining the dynamic priority for each thread using a formula of:
P
t
=
P
t0
+
K
·
W
td
D
+
Y
t
,
where P t represents the dynamic priority for a particular thread, P t0 represents the static component of the dynamic priority, K represents a constant, W td represents the amount of work to be done by the thread, D represents the amount of time from the deadline for the thread, and Y t represents a value from the concurrency engine.
23. The processor of claim 20 , further comprising a dedicated register set for each thread executed by the processor, the dedicated register set for a particular thread storing a priority associated with the particular thread, the scheduler configured to schedule execution of the instructions from the plurality of threads using the stored priority for each of the threads.
24. An apparatus, comprising:
at least one of: an input device and an interface to the input device, the input device configured to provide input data;
at least one of: an output device and an interface to the output device, the output device configured to receive output data; and
a processing system configured to receive the input data and generate the output data, the processing system comprising:
a plurality of processors configured to execute a plurality of threads; and
at least one hardware scheduler configured to schedule execution of the plurality of threads by the plurality of processors, the execution schedule based on a dynamic priority for each thread, wherein the at least one hardware scheduler is configured to determine the dynamic priority for each thread by adding a static component of the dynamic priority for the thread to a quotient of an amount of work to be done by the thread divided by an amount of time from a deadline for each thread.
25. The apparatus of claim 24 , wherein:
the apparatus comprises a mobile telephone;
the at least one of an input device and an interface to the input device comprises a keypad and a microphone; and
the at least one of an output device and an interface to the output device comprises a display and a speaker.
26. The apparatus of claim 24 , further comprising:
an antenna configured to at least one of: receive wireless signals and transmit wireless signals; and
a wireless interface configured to convert received signals into data suitable for processing and of converting data into signals suitable for transmission.
27. The apparatus of claim 24 , wherein:
the apparatus is coupled to a network; and
the processing system is configured to perform at least one of packet forwarding and traffic management.
28. The apparatus of claim 24 , wherein the at least one scheduler is configured to determine the dynamic priority for each thread using a formula of:
P
t
=
P
t0
+
K
·
W
td
D
,
where P t represents the dynamic priority for a particular thread, P t0 represents the static component of the dynamic priority, K represents a constant, W td represents the amount of work to be done by the thread, and D represents the amount of time from the deadline for the thread.
29. The apparatus of claim 24 , wherein the at least one scheduler is configured to determine the dynamic priority for each thread using a formula of:
P
t
=
P
t0
+
K
·
W
td
D
+
Y
t
,
where P t represents the dynamic priority for a particular thread, P t0 represents the static component of the dynamic priority, K represents a constant, W td represents the amount of work to be done by the thread, D represents the amount of time from the deadline for the thread, and Y t represents a value from a concurrency engine configured to manage a plurality of concurrency primitives that coordinate execution of the threads by the processors.