Multi-core device and multi-thread scheduling method thereof

Patent metadata

Field	Value
Publication number	US-9632822-B2
Application number	US-201313961604-A
Country	US
Kind code	B2
Filing date	Aug 7, 2013
Priority date	Sep 21, 2012
Publication date	Apr 25, 2017
Grant date	Apr 25, 2017

Abstract

A multi-core device and a multi-thread scheduling method thereof are disclosed. The multi-thread scheduling method includes the following steps: recording thread performance-associated parameters for a thread; and performing a thread load balancing between multiple central processing units of a multi-core processor of the multi-core device. The thread load balancing is performed according to a thread critical performance condition of the thread and the thread critical performance condition is determined based on the thread performance-associated parameters.

First claim

What is claimed is:

1. A multi-core device, comprising:
a multi-core processor, comprising multiple central processing units;
a random access memory, coupled to the multi-core processor,
wherein:
the multi-core processor uses the random access memory to store thread performance-associated parameters for a plurality of threads; and
a code storage, stored with operating system codes to be executed by the multi-core processor to provide an operating system scheduler to perform a thread load balancing between the multiple central processing units, performing the steps of:
thread load balancing according to a thread critical performance condition of the thread and the thread critical performance condition is determined based on the threads current and historical performance-associated parameters,
generating an array of entries for the performance-associated parameters, wherein each entry of the array corresponds to a historically observed values of the performance-associated parameter of the multi-core processor;
initializing an unfinished count of a thread to a value of zero;
determining a number of right shifts needed for making the value of the unfinished count to equal zero;
determining the historical observed value associated with the performance-associated parameter indexed at a position value equivalent to the number of right shifts;
determining if the current value of the performance-associated parameter associated with the thread is greater than the determined historic observed value, and if so setting the thread critical performance condition to critical;
if the current value of the performance-associated parameter associated with the thread is less than the determined historic observed value, performing the steps of:
preempting the thread;
increasing the unfinished count by one; and
repeating the determining steps; and

processing said thread on one of the multiple central processing units when the thread critical performance condition is critical.

2. The multi-core device as claimed in claim 1 , wherein:
the thread performance-associated parameters comprises a waiting latency which indicates a waiting time of the thread in a runnable queue before switching to a running state, and the thread critical performance condition is evaluated based on the waiting latency of the thread.

3. The multi-core device as claimed in claim 2 , wherein:
the thread performance-associated parameters further comprises historic waiting latency information, and to determine whether the thread critical performance condition is critical, a currently evaluated waiting latency of the thread is compared to a latency criterion, wherein the latency criterion is set based on the historic waiting latency information as well as the currently evaluated waiting latency, and
the criterion for the thread with the higher unfinished count comprises historic waiting latency information with a higher weight than that with a lower unfinished count.

4. The multi-core device as claimed in claim 1 , wherein:
the thread performance-associated parameters comprises a MIPS/clock cycle value which indicates the execution speed of the thread in a running state, and the thread critical performance condition of the thread is evaluated based on the MIPS/clock cycle value of the thread.

5. The multi-core device as claimed in claim 4 , wherein:
the thread performance-associated parameters further comprises historic MIPS/clock cycle value information, and to determine whether a thread critical performance condition is critical, a currently evaluated MIPS/clock cycle value of the thread is compared to a MIPS/clock cycle criterion, wherein the MIPS/clock cycle criterion is set based on the historic MIPS/clock cycle value information as well as the currently evaluated MIPS/clock cycle value, and
the criterion for the thread with the higher unfinished count comprises historic MIPS/clock cycle value information with a higher weight than that with a lower unfinished count.

6. The multi-core device as claimed in claim 1 , wherein:
when the thread critical performance condition is critical, a central processing unit of the multiple central processing units wakes up from a power saving mode to execute the thread.

7. The multi-core device as claimed in claim 1 , wherein:
when the thread critical performance condition is critical, a processor frequency of the central processing unit executing the thread is scaled up by Dynamic Voltage and Frequency Scaling.

8. The multi-core device as claimed in claim 1 , wherein:
when the thread is released to a runnable state from a blocked state, the unfinished count is reset.

9. A multi-thread scheduling method for a multi-core device, comprising:
recording thread performance-associated parameters for a plurality of threads; and
performing a thread load balancing between multiple central processing units of a multi-core processor of the multi-core device,
wherein the thread load balancing is performed according to a thread critical performance condition of the thread and the thread critical performance condition is determined based on the thread performance-associated parameters,
generating an array of entries for the performance-associated parameters, wherein each entry of the array corresponds to a historically observed values of the performance-associated parameter of the multi-core processor;
initializing an unfinished count of a thread to a value of zero;
determining a number of right shifts needed for making the value of the unfinished count to equal zero;
determining the historical observed value associated with the performance-associated parameter indexed at a position value equivalent to the number of right shifts;
determining if the current value of the performance-associated parameter associated with the thread is greater than the determined historic observed value, and if so setting the thread critical performance condition to critical;
if the current value of the performance-associated parameter associated with the thread is less than the determined historic observed value, performing the steps of:
preempting the thread;
increasing the unfinished count by one; and
repeating the determining steps; and

processing said thread on one of the multiple central processing units when the thread critical performance condition is critical.

10. The multi-thread scheduling method as claimed in claim 9 , wherein:
the thread performance-associated parameters comprises a waiting latency which indicates a waiting time of the thread in a runnable queue before switching to a running state, and the thread critical performance condition is evaluated based on the waiting latency of the thread.

11. The multi-thread scheduling method as claimed in claim 10 , wherein:
the thread performance-associated parameters further comprises historic waiting latency information, and to determine whether the thread critical performance condition is critical, a currently evaluated waiting latency of the thread is compared to a latency criterion, wherein the latency criterion is set based on the historic waiting latency information as well as the currently evaluated waiting latency, and
the criterion for the thread with the higher unfinished count comprises historic waiting latency information with a higher weight than that with a lower unfinished count.

12. The multi-thread scheduling method as claimed in claim 9 , wherein: the thread performance-associated parameters comprises a MIPS/clock cycle value which indicates the execution speed of the thread in a running state, and the thread critical performance condition of the thread is evaluated based on the MIPS/clock

Assignees

• Htc Corp

Inventors

• Chang Wen-Yen
• Wu Chih-Tsung
• Lai Ching-Tsung

Classifications

• G06F9/50

  Allocation of resources, e.g. of the central processing unit [CPU] · CPC title

• G06F2209/483

  Multiproc · CPC title

• G06F2209/501

  Performance criteria · CPC title

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F9/505

  considering the load · CPC title