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

This application claims priority under 35 U.S.C. § 119 to Korean Patent Application No. 10-2016-0032939, filed on Mar. 18, 2016, the disclosure of which is incorporated herein by reference in its entirety.

The present invention relates to a thread scheduling method and apparatus, and more particularly, to thread scheduling in which a plurality of threads are allocated to a plurality cores in a many-core system.

A many-core central processing unit (CPU) denotes a CPU where 100 or 1,000 or more cores are integrated into one chip. A multicore CPU is being widely used at present, and the many-core CPU is expected to be widely used in the near future.

As interest in many-core processors increases, interest in a microkernel-based operating system (OS) for the many-core processors is increasing.

A collaboration between processes (or threads which are a subordinate concept of the processes) executed in the microkernel-based OS uses a message transfer method based on inter-process communication (IPC). This denotes that a performance of the IPC is closely associated with a performance of the microkernel-based OS.

Among various factors affecting the performance of the IPC, a factor affecting the performance of the IPC in a structure of the many-core CPU is a hop between cores included in the many-core CPU.

If the number of cores is 100, a message is transferred via a maximum of 20 hops, and if the number of cores is 1,000, a message is transferred via about 64 hops. A time taken in transferring a message via one hop is a one CPU cycle.

Considering that a time taken in unidirectional IPC is 36 to 316 CPU cycles in a conventional microkernel, a hop between cores to which a thread for performing IPC in a many-core is allocated affects IPC performance greatly.

Therefore, thread allocation where threads are allocated to cores in consideration of a hop between the cores is a very important factor for enhancing IPC performance. However, a thread allocation method for greatly enhancing IPC performance is not proposed yet.

Accordingly, the present invention provides a thread scheduling method and apparatus for enhancing IPC performance.

In one general aspect, a method of scheduling threads in a many-cores system operating based on many-core processors including a plurality of 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 the 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.

In another general aspect, an apparatus for scheduling threads in a many-cores system operating based on many-core processors including a plurality of cores includes: a storage unit configured to store 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 threads, and a core map where a connection relationship between the plurality of cores is represented by a hop between cores; and a scheduler configured to respectively allocate the plurality of threads to the plurality of cores, based on the thread allocation policy stored in the storage unit.

Other features and aspects will be apparent from the following detailed description, the drawings, and the claims.

FIG. 1 is a block diagram illustrating a many-core system according to an embodiment of the present invention.

FIG. 2 is a diagram illustrating a thread map according to an embodiment of the present invention.

FIG. 3 is a diagram illustrating a core map according to an embodiment of the present invention.

FIG. 4 is a diagram illustrating an example where threads illustrated in FIG. 1 are arbitrarily allocated to cores illustrated in FIG. 2 .

FIG. 5 is a diagram illustrating an example where the threads illustrated in FIG. 1 are allocated to the cores illustrated in FIG. 2 in consideration of a frequency of IPC between the threads, according to an embodiment of the present invention.

FIGS. 6A and 6B are flowcharts illustrating a thread allocation method according to an embodiment of the present invention.

FIG. 7 is a diagram illustrating an example where a thread pair which is the highest in frequency of IPC is allocated to a core, according to an embodiment of the present invention.

FIG. 8 is a diagram illustrating an example where a thread pair which is second high in frequency of IPC is allocated to a core, according to an embodiment of the present invention.

FIG. 9 is a diagram illustrating an example where a thread pair which is third high in frequency of IPC is allocated to a core, according to an embodiment of the present invention.

Hereinafter, example embodiments of the present invention will be described in detail with reference to the accompanying drawings. Embodiments of the present invention are provided so that this disclosure will be thorough and complete, and will fully convey the concept of the present invention to one of ordinary skill in the art. Since the present invention may have diverse modified embodiments, preferred embodiments are illustrated in the drawings and are described in the detailed description of the present invention. However, this does not limit the present invention within specific embodiments and it should be understood that the present invention covers all the modifications, equivalents, and replacements within the idea and technical scope of the present invention. Like reference numerals refer to like elements throughout.

It will be further understood that the terms “comprises” and/or “comprising,” when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof. In various embodiments of the disclosure, the meaning of ‘comprise’, ‘include’, or ‘have’ specifies a property, a region, a fixed number, a step, a process, an element and/or a component but does not exclude other properties, regions, fixed numbers, steps, processes, elements and/or components.

As used herein, the term “or” includes any and all combinations of one or more of the associated listed items. For example, “A or B” may include A, include B, or include A and B.

It will be understood that, although the terms first, second, etc. used herein may qualify various elements according to various embodiments, these elements should not be limited by these terms. For example, the terms do not limit the order and/or importance of corresponding elements. These terms are only used to distinguish one element from another. For example, a first user equipment and a second user equipment are user equipment and denote different user equipment. For example, a first element may be referred to as a second element without departing from the spirit and scope of the present invention, and similarly, the second element may also be referred to as the first element.

In the case in which a component is referred to as being “connected” or “accessed” to other component, it should be understood that not only the component is directly connected or accessed to the other component, but also there may exist another component between the components. Meanwhile, in the case in which a component is referred to as being “directly connected” or “directly accessed” to other component, it should be understood that there is no component therebetween.

FIG. 1 is a block diagram illustrating a many-core system 100 according to an embodiment of the present invention.

Referring to FIG. 1 , the many-core system 100 according to an embodiment of the present invention may respectively allocate a plurality of threads to a plurality of cores, based on a frequency of inter-process communication (IPC) between threads. Due to such a thread allocation policy, a hop (a hop between two cores to which two threads are respectively allocated) between two threads for performing IPC is minimized in a microkernel-based many-core OS, and thus, IPC performance is enhanced.

In detail, the many-core system 100 may include a storage unit 110 , a scheduler 120 , a binder 130 , and a many-core processor (or a many-core CPU) 140 .

The storage unit 110 may store thread allocation policy information (hereinafter referred to as a thread allocation policy) based on thread map information (hereinafter referred to as a thread map) and core map information (hereinafter referred to as a core map).

The thread map may be an information map where a connection relationship between a plurality of threads T 1 to Tm generated by a process 10 is represented by a frequency of IPC, and the core map may be an information map where a connection relationship between a plurality of cores C 1 to Cn included in the many-core processor 140 is represented by a hop between cores. The thread map and the core map will be described below in detail.

The thread allocation policy may be a policy for respectively allocating the plurality of threads T 1 to Tm to the plurality of cores C 1 to Cn and may define a mapping rule between the thread map and the core map.

The scheduler 120 may generate a thread allocation command for respectively allocating the plurality of threads T 1 to Tm to the plurality of cores C 1 to Cn, based on the thread allocation policy stored in the storage unit 110 and may output the thread allocation command to the binder 130 .

The binder 130 may respectively connect the plurality of threads T 1 to Tm to the plurality of cores C 1 to Cn according to the thread allocation command. Therefore, each of the plurality of threads T 1 to Tm may be executed by a core connected thereto.

Hereinafter, a thread map and a core map will be described with reference to FIGS. 2 and 3 .

A thread map and a core map according to an embodiment of the present invention may be defined for respectively allocating a plurality of threads to a plurality of cores, based on a frequency of IPC.

First, as illustrated in FIG. 2 , the thread map may be expressed as an undirected graph. In order to help understanding, in FIG. 2 , a thread map consisting of nine threads is illustrated exemplarily.

The thread map according to an embodiment of the present invention may include nine vertexes t 1 to t 9 and a plurality of edges that connect the nine vertexes t 1 to t 9 . That is, in the thread map, nine threads T 1 to T 9 may be respectively configured with the nine vertexes t 1 to t 9 , and the nine vertexes t 1 to t 9 may be connected by the edges. In this case, each of the edges may denote occurrence of IPC, and in FIGS. 2, 1, 5, 10, 20, 30, 50, 70 , and 100 illustrated on the respective edges each represent a frequency of IPC performed between threads. Here, the frequency of IPC may be measured from the number of application program interface (API) calls associated with IPC.

Similarly, as illustrated in FIG. 3 , the core map may be expressed as an undirected graph. In order to help understanding, in FIG. 3 , a core map consisting of nine cores is illustrated exemplarily.

The core map according to an embodiment of the present invention may include nine vertexes c 1 to c 9 and a plurality of edges that connect the nine vertexes c 1 to c 9 . That is, in the core map, nine cores C 1 to C 9 may be respectively configured with the nine vertexes c 1 to c 9 , and the nine vertexes c 1 to c 9 may be connected by the edges. In this case, each of the edges represents a hop.

In allocating a thread to a core, in order to maximize a system throughput, the average IPC cost “E” of all threads should be minimized.

The average IPC cost “E” may be calculated as expressed in the following

Equation (1):

E =(1/ W )*sum( Wt ( e )* d ( m ( v ), m ( w ))), for each e =( v,w )  (1)

where e denotes an edge indicating whether IPC is performed between a thread “v” and a thread “w”, Wt(e) denotes a frequency of IPC occurring in the edge “e”, W denotes a total sum of frequencies of IPC “Wt(e)”, m( ) denotes a one-to-one mapping function defining a mapping rule between a thread and a core, m(v) denotes a core to which the thread “v” is allocated based on the mapping function, and m(w) denotes a core to which the thread “w” is allocated based on the mapping function. Also, d(m(v), m(w)) denotes a distance between the core “m(v)” and the core “m(w)”. Here, the distance may be represented by a hop and may be the minimum number of edges connecting the core “m(v)” and the core “m(w)”.

As seen through Equation (1), the average IPC cost “E” may be determined by the distance “d(m(v), m(w))”.

FIG. 4 is a diagram illustrating an example where threads are arbitrarily allocated to cores illustrated in FIG. 3 with no consideration of a frequency of IPC between the threads. FIG. 5 is a diagram illustrating an example where threads are allocated to cores in consideration of a frequency of IPC between the threads, according to an embodiment of the present invention.

By using Equation (1), the average IPC cost “E” calculated based on a thread allocation result of FIG. 4 is 3.17, and the average IPC cost “E” calculated based on a thread allocation result of FIG. 5 is 1.14.

Therefore, it can be seen that the average IPC cost “E” is lower in a case, where a plurality of threads are respectively allocated to a plurality of cores based on the thread allocation policy according to an embodiment of the present invention, than a case where a plurality of threads are respectively allocated to a plurality of cores arbitrarily.

Hereinafter, a method of respectively allocating a plurality of threads to a plurality of cores according to an embodiment of the present invention will be described in detail.

FIGS. 6A and 6B are flowcharts illustrating a thread allocation method according to an embodiment of the present invention.

Referring to FIG. 6A , in step S 610 , a center core Gc may be selected from a core map.

A core, arranged at a position where a sum of hops to all cores is the minimum, may be selected as the center core from the core map. When the core map illustrated in FIG. 3 is assumed, a core located at a vertex c 5 may be selected as the center core.

Subsequently, in step S 620 , a plurality of thread pairs may be configured by combining, by twos, a plurality of threads generated by a process.

Subsequently, in step S 630 , frequencies of IPC may be sorted in descending power, and the plurality of threads may be sorted in order in which the frequencies of IPC are sorted. When a thread map having an IPC frequency distribution illustrated in FIG. 2 is assumed, a plurality of thread pairs and a frequency of IPC corresponding to each of the thread pairs may be sorted as listed in the following Table 1.

In a sorting process, when there are thread pairs having the same frequency of IPC, the order of each of the thread pairs may be determined as an arbitrary order. Therefore, in Table 1, No. 3 rank thread pair (t 2 , t 4 ) may be arranged in No. 4 rank, and No. 4 rank thread pair (t 3 , t 6 ) may be arranged in No. 3 rank.

Subsequently, in step S 640 , a thread pair which is the highest in frequency of IPC may be selected from the sorted plurality of thread pairs. In Table 1, a thread pair which is the highest in frequency of IPC may be (t 1 , t 3 ). Hereinafter, a thread pair which is the highest in frequency of IPC may be referred to as a first thread pair.

Subsequently, in step S 650 , a thread allocated to the center core may be selected from among two threads included in the first thread pair.

A thread which is to be allocated to the center core may be selected based on a total sum of all frequencies of IPC occurring in the threads included in the first thread pair.

For example, when the thread map having the IPC frequency distribution illustrated in FIG. 2 is assumed, in the thread pair (t 1 , t 3 ) which is the highest in frequency of IPC, a total sum of all frequencies of IPC occurring in a thread t 3 may be 251(=100+70+50+30+1), and a total sum of all frequencies of IPC occurring in a thread t 1 may be 100.

Therefore, since the total sum of all the frequencies of IPC occurring in the thread t 3 is greater than the total sum of all the frequencies of IPC occurring in the thread t 1 , the thread t 3 may be selected as a thread which is to be allocated to the center core.

Subsequently, in step S 660 , when the thread which is to be allocated to the center core is selected, the selected thread may be allocated to the center core, and an unselected thread may be allocated to a core arbitrarily selected from among cores adjacent to the center core.

For example, when the thread pair (t 1 , t 3 ) which is the highest in frequency of IPC is allocated to a core included in the core map of FIG. 3 , as illustrated in FIG. 7 , the thread t 3 may be allocated to a center core c 5 selected from the core map, and the thread t 1 may be allocated to one core arbitrarily selected from among cores c 1 , c 2 , c 2 , c 3 , c 4 , c 6 , c 7 , and c 8 adjacent to the center core c 5 . FIG. 7 illustrates an example where the thread t 1 is allocated to a core c 4 .

Subsequently, in step S 670 , when core allocation for the first thread pair has been completed, a thread pair which is second high in frequency of IPC may be selected from among the thread pairs which have been sorted in step S 630 . For example, when the thread map having the IPC frequency distribution illustrated in FIG. 2 is assumed, a thread pair (t 3 , t 4 ) which is second high in frequency of IPC may be selected. Hereinafter, the thread pair which is second high in frequency of IPC may be referred to as a second thread pair.

Referring to FIG. 6B , subsequently, in step S 680 , whether at least one thread of two threads included in the second thread pair is in a state of being already allocated to a core may be determined.

When one of the two threads is in a state of being already allocated to the core, the thread allocation method may proceed to step S 682 , but when all of the two threads is not in a state of being already allocated to the core, the thread allocation method may proceed to step S 684 .

In step S 682 , when one of the two threads included in the second thread pair has been already allocated to the core, another unselected thread may be allocated to a core arbitrarily selected from among cores adjacent to the core to which the one thread has been already allocated.

For example, if the thread pair which has been selected in step S 670 is (t 3 , t 4 ), the thread t 3 may be in a state of being already allocated to the core in an operation of allocating the first thread pair (t 3 , t 1 ) to the core, and thus, only an operation of allocating a thread t 4 to a core may be performed. In this case, as illustrated in FIG. 8 , the thread t 4 may be allocated to a core arbitrarily selected from among cores c 2 , c 6 , and c 8 arranged at a hop closest to the core c 5 to which the thread t 3 is allocated. FIG. 8 illustrates an example where the thread t 4 is allocated to a core c 6 .

The core c 4 is a core arranged at the hop closest to the core c 5 to which the thread t 3 is allocated, but is a core to which the thread t 1 has been already allocated in an operation of allocating the first thread pair (t 1 , t 3 ), which is the highest in frequency of IPC, to the core. Therefore, the core c 4 is excluded from a candidate core to which the thread t 4 is to be allocated.

When all of two threads included in the second thread pair are not in a state of being allocated to a core, in step S 684 , one thread arbitrarily selected from among the two threads included in the second thread pair may be allocated to a core arbitrarily selected from among cores to which a thread is not allocated, and an unselected thread of the two threads included in the second thread pair may be allocated to a core arbitrarily selected from among cores adjacent to the core to which the arbitrarily selected one thread is allocated.

Subsequently, in step S 690 , a core allocation operation may be sequentially performed on the other thread pairs in descending power of frequencies of IPC.

That is, when the core allocation operation has been performed on a thread pair which is third high in frequency of IPC, the core allocation operation may be performed on a thread pair which is fourth high in frequency of IPC.

For example, a thread pair (t 2 , t 4 ) or a thread pair (t 3 , t 6 ) which is third high in frequency of IPC may be selected from the thread map of FIG. 2 . In this case, an operation of allocating a thread pair (t 2 , t 4 ) to a core may be performed based on the ranks of Table 1. Here, as illustrated in FIG. 8 , since the thread t 4 is a thread which has been already allocated to the core c 6 in an operation of allocating the second thread pair (t 3 , t 4 ) to the core, only the thread t 2 of the thread pair (t 2 , t 4 ) may be allocated to a core. That is, the thread t 2 may be allocated to a core, which is arranged at a hop closest to the core c 6 to which the thread t 4 is allocated, among cores to which a thread is not allocated yet. An example where the thread t 2 is allocated to the core is illustrated in FIG. 9 , and FIG. 9 illustrates an example where the thread t 2 is allocated to the core c 3 among the cores c 3 and c 9 arranged at a hop closest to the core c 6 to which the thread t 4 is allocated.

Subsequently, the other threads (t 3 , t 6 ), (t 3 , t 2 ), (t 2 , t 7 ), (t 2 , t 8 ), (t 8 , t 9 ), and (t 3 , t 5 ) may be sequentially allocated to cores. An operation of respectively allocating the threads (t 3 , t 6 ), (t 3 , t 2 ), (t 2 , t 7 ), (t 2 , t 8 ), (t 8 , t 9 ), and (t 3 , t 5 ) to the cores can be sufficiently understood through the descriptions on steps S 610 to S 690 , and thus, its detailed description is not provided. A result where all thread pairs are allocated to cores is illustrated in FIG. 5 .

As described above, in an embodiment of the present invention, since threads are allocated to a plurality of cores integrated into a many-core in consideration of a frequency of IPC between the threads, IPC performance associated with a system throughput and the IPC cost can be enhanced.

Furthermore, if the many-core system for scheduling threads according to an embodiment of the present invention is applied to electronic devices, a performance of the many-core system can be enhanced.

The many-core system according to an embodiment of the present invention may be applied to various electronic devices. For example, examples of the electronic devices may include at least one of a smartphone, a tablet personal computer (PC), a mobile phone, a video phone, an e-book reader, a desktop PC, a laptop PC, a netbook PC, a personal digital assistant (PDA), a portable multimedia player (PMP), an MP3 player, a mobile medical device, a camera, a wearable device (e.g., a head-mounted device (HMD), electronic clothes, electronic braces, an electronic necklace, an electronic appcessory, an electronic tattoo, or a smart watch), and/or the like.

Moreover, it is obvious to those skilled in the art that devices to which the many-core system according to an embodiment of the present invention is applied are not limited to the above-described devices, and the many-core system according to an embodiment of the present invention may be applied to all devices including a many-core processor including a plurality of cores integrated into a single chip without being limited to the kinds of devices.

According to the embodiments of the present invention, since threads are allocated to a plurality of cores integrated into a many-core in consideration of a frequency of IPC between the threads, IPC performance associated with a system throughput and the IPC cost can be enhanced.

A number of exemplary embodiments have been described above. Nevertheless, it will be understood that various modifications may be made. For example, suitable results may be achieved if the described techniques are performed in a different order and/or if components in a described system, architecture, device, or circuit are combined in a different manner and/or replaced or supplemented by other components or their equivalents. Accordingly, other implementations are within the scope of the following claims.