Method for scheduling threads in a many-core system based on a mapping rule between the thread map and core map

• US 10,296,379 B2
• Filed: 03/17/2017
• Issued: 05/21/2019
• Est. Priority Date: 03/18/2016
• Status: Active Grant

• Current Assignee: Electronics and Telecommunications Research Institute
• Original Assignee: Electronics and Telecommunications Research Institute
• Inventors: Kim, Kang Ho, Koh, Kwang Won, Kim, Jin Mee, Lee, Jeong Hwan, Jeon, Seung Hyub, Jung, Sung In, Jeong, Yeon Jeong, Cha, Seung Jun
• Primary Examiner(s): Ghaffari, Abu
• Application Number:
  US15/462,683
• Publication Number:
  US 20170269966A1
• Time in Patent Office: 795 Days
• Field of Search: None
• CPC Class Codes: G06F 1/329 by task scheduling
• CPC Class Codes: G06F 2209/502 Proximity
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/54 Interprogram communication

Abstract

Scheduling threads in a system with many cores includes generating a thread map where a connection relationship between a plurality of threads is represented by a frequency of inter-process communication (IPC) between threads, generating a core map where a connection relationship between a plurality of cores is represented by a hop between cores, and respectively allocating the plurality of threads to the plurality of cores defined by the core map, based on a thread allocation policy defining a mapping rule between the thread map and the core map.

Claims

1. A method of scheduling threads in a many-cores system operating based on many-core processors including a plurality of cores, the method comprising:

generating a thread map where a connection relationship between a plurality of threads is represented by a frequency of inter-process communication (IPC) between all pairs of threads in the plurality of threads;

generating a core map where a connection relationship between the plurality of cores is represented by hops between each of the plurality of cores; and

respectively allocating the plurality of threads to the plurality of cores defined by the core map, based on a thread allocation policy defining a mapping rule between the thread map and the core map

wherein the respectively allocating of the plurality of threads to the plurality of cores comprises;

combining the plurality of threads by twos to configure a plurality of thread pairs;

selecting a first thread pair, which is the highest in frequency of IPC between the threads, from among the plurality of thread pairs;

allocating a thread, selected front among two threads included in the first thread pair, to a center core; and

allocating another unselected thread of the two threads to a core arbitrarily selected from among cores adjacent to the center core.

2. The method of claim 1, wherein the generating of the thread map comprises:

configuring the plurality of threads with a plurality of vertexes, respectively; and

connecting the plurality of vertexes by using an edge representing the frequency of IPC.

3. The method of claim 1, wherein the generating of the core map comprises:

configuring the plurality of cores with a plurality of vertexes, respectively; and

connecting the plurality of vertexes by using an edge representing the hop.

4. The method of claim 1, wherein the center core is a core arranged at a position where a sum of hops to all cores is the minimum.

5. The method of claim 1, wherein in the allocating of the thread to the center core, a total sum of all frequencies of IPC occurring in the selected thread is greater than a total sum of all frequencies of IPC occurring in the other unselected thread.

6. The method of claim 1, further comprising:

after the allocating of the thread to the selected core,

selecting a second thread pair, which is second high in frequency of IPC between the threads, from among the plurality of thread pairs; and

when one thread of two threads included in the second thread pair has been already allocated to one core of the center core and the arbitrarily selected core, allocating another one thread included in the second thread pair to a core arranged at a hop closest to the one core to which the one thread has been already allocated.

7. The method of claim 1, further comprising:

after the allocating of the thread to the selected core,

selecting a second thread pair, which is second high in frequency of IPC between the threads, from among the plurality of thread pairs;

when all of two threads included in the second thread pair are not in a state of being allocated to the center core or the arbitrarily selected core, allocating a thread, selected from among the two threads included in the second thread pair, to a core arbitrarily selected from among other cores except the center core and the arbitrarily selected core; and

allocating an unselected thread of the two threads, included in the second thread pair, to a core arbitrarily selected from among cores adjacent to a core to which the selected thread of the two threads included in the second thread pair is allocated.

8. An electronic that includes a many-core system for scheduling threads by using the method of claim 1, the many core system including a many-core processor.

9. A many-core system comprising:

a memory that stores a thread allocation policy defining a mapping rule between a thread map, where a connection relationship between a plurality of threads is represented by a frequency of inter-process communication (IPC) between all pairs of threads in the plurality of threads, and a core map where a connection relationship between the plurality of cores is represented by hops between each of the plurality of cores; and

a scheduler that is configured to perform the following operations;

respectively allocating the plurality of threads to the plurality of cores, based on the thread allocation policy stored in the storage unit;

selecting two threads, which are the highest in frequency of IPC, from among the plurality of threads according to the thread allocation policy;

allocating a thread selected from among the selected two threads to a center core of the plurality of cores; and

allocating another unselected thread of the two threads to a core arbitrarily selected from among cores adjacent to the center core.

10. The apparatus of claim 9, wherein the thread map is a map where a plurality of vertexes respectively corresponding to the plurality of threads are connected to each other by using an edge representing the frequency of IPC.

11. The apparatus of claim 9, wherein the core map is a map where a plurality of vertexes respectively corresponding to the plurality of cores are connected to each other by using an edge representing the hop.

12. The apparatus of claim 9, wherein the center core is a core arranged at a position where a sum of hops to all cores is the minimum.

13. The apparatus of claim 9, wherein a total sum of all frequencies of IPC occurring in the selected thread is greater than a total sum of all frequencies of IPC occurring in the other unselected thread.

14. The apparatus of claim 9, wherein the scheduler is further configured to:

select two threads, which are second high in frequency of IPC, from among the plurality of threads according to the thread allocation policy, and

when one thread of the two threads which are second high in frequency of IPC is in a state of being allocated to the center core or the arbitrarily selected core, allocates another one thread to a core arbitrarily selected from among cores adjacent to the center core or the arbitrarily selected core.