KR101553650B1 - Load Balancing Device and Method in Multicore Systems - Google Patents

Abstract

A load balancing apparatus and method in a multicore system for achieving load distribution with little overhead through the modification of the core allocation of a thread rather than changing the data distribution is disclosed. According to one embodiment, it may be determined whether the load of a multicore allocated to a plurality of threads per core is unbalanced, and if it is determined to be unbalanced, the core allocation for at least one thread of the plurality of threads may be changed Thereby performing load balancing. A plurality of threads are loaded on the multicore based on the allocation of the plurality of threads to the multicore and the core utilization rate.

Load balancing, multicore, thread, core utilization

Description

[0001] Apparatus and method for load balancing in multi-core systems [

One or more aspects of the present invention pertain to multicore based systems, and more particularly, to an apparatus and method for effectively distributing computational loads in multicore.

3D graphics or multi-modal user interface (UI) require computational power because they simulate physical phenomena and calculate the results. Multicore systems such as Multiprocessor System-on-Chip (MPSoC) are being offered to meet these needs. Such a multi-core system has a different computation power required for each core according to input data, so that the performance of the entire system becomes equal to the performance of the cores requiring the most computation power among all cores. To overcome this situation, a method is being studied to improve overall performance by dynamically balancing load between cores.

The problem of distributing computing loads among cores in multicore is as old as distributed computing. Most of the researches on this problem of load distribution are studying a way to distribute input data to each core with techniques for distributed environment or grid computing.

A load balancing apparatus and method is proposed in a multicore system for achieving load distribution with little overhead by changing the core allocation of a thread rather than changing the data distribution.

A load balancing apparatus of a multicore system according to an aspect of the present invention determines whether a load of a multicore core allocated to a plurality of threads per core is unbalanced and determines whether a load of at least one thread among a plurality of threads A load management unit for performing load balancing by changing the allocation to the core; And a thread load table including load information corresponding to each thread allocated to the multicore.

And a scheduler for loading or unloading the multicore based on the allocation of the plurality of threads to the multicore determined by the load management unit and the core utilization rate. If the scheduler determines that the core allocation for at least one thread should be changed by the load management unit for load balancing of each of the multi-cores, the scheduler stops only the operation of at least one thread whose allocation is to be changed, , The operation of at least one thread in the core whose allocation has been changed can be resumed.

The thread load information includes thread identification information for each thread, load information for the thread, core information allocated to the thread, and utilization information of the core for processing the thread in the core.

The load management unit measures the load for each thread of each core, updates the thread load information for each measured thread to the thread load table, determines whether the load between the cores is unbalanced, and if the load between the cores is determined to be unbalanced, A transmitting performance measuring unit; A load balancing execution unit for receiving a load balancing request, determining a quota and a core utilization rate for a plurality of threads of a plurality of threads based on updated load information, and updating the determined allocation and core utilization ratios in a thread load table; And a core allocation unit for setting a core allocation and a core utilization ratio of the plurality of threads based on the updated allocation and the core utilization ratio.

According to another aspect of the present invention, there is provided a load balancing method for a multi-core system, the multi-core load balancing method comprising: determining whether a load of a multi-core allocated to a plurality of threads per core is unbalanced; And performing load balancing by changing allocation of at least one thread of the plurality of threads to a multicore if it is determined to be unbalanced; .

According to one embodiment, by providing an appropriate dynamic load balancing scheme in a MPSoC environment where the cost of core allocation is much less than in a distributed environment, reducing the waiting time of unnecessary threads and reducing the data redistribution overhead between threads The performance of the MPSoC embedded system can be improved.

Because it provides dynamic load balancing with less overhead, it can provide a fine grained load-balancing technique that enables load balancing even on a per-loop basis.

Hereinafter, an embodiment of the present invention will be described in detail with reference to the accompanying drawings. In the following description of the present invention, a detailed description of known functions and configurations incorporated herein will be omitted when it may make the subject matter of the present invention rather unclear. In addition, the terms described below are defined in consideration of the functions of the present invention, which may vary depending on the intention of the user, the operator, or the custom. Therefore, the definition should be based on the contents throughout this specification.

FIGS. 1A and 1B illustrate a load balancing technique for a multicore system according to an embodiment.

1A and 1B illustrate a multicore system in which two cores, a first core 110 and a second core 120, are coupled to the bus 130 to process threads. In FIGS. 1A and 1B, the ellipses 11, 21, 31, and 41 represent threads executed in the corresponding core. 1B, two threads are allocated to the first core 110 and the second core 120, respectively.

The rectangle 12 below the thread 11 represents the core usage occupied by the thread 11 in the first core 110 and the rectangle 22 below the thread 21 represents the core usage occupied by the first core 110. [ Represents the core usage occupied by the thread 21 in the thread. The quadrangles 32 and 42 under the threads 31 and 41 also indicate the core utilization rate of the corresponding thread in the second core 120, respectively. The core utilization rate is a ratio of the CPU usage time (CPU time) used to process each thread when a plurality of threads are allocated to one core (or core processor). In addition, A (10), B (20), C (30) and D (40) represent the data allocated to each thread, and the numbers under A, B, C and D indicate the load .

FIG. 1A shows a multi-core system before load balancing according to one embodiment.

It is assumed that the first core 110 and the second core 120 occupy the same 50% of the core utilization allocated for processing each thread. The data processing load of the first core 110 is 8 and the data processing load of the second core 120 is 12, so that the load imbalance of the multicore can be detected.

In a typical load balancing scheme, one thread is allocated to each core. After the load of each core is measured, the operation of the entire system is suspended by the global synchronization technique, and the data is dynamically redistributed. Called " stop-and-repartition " based load balancing techniques. These dynamic load balancing techniques based on the stop-and-re partition are not suitable for applications with a large load change according to input data such as 3D graphics. The reason is that the overhead of stopping all threads at all, and the overhead of data redistribution, are more than the performance gains of balancing the load, reducing the effect of load balancing.

On the other hand, according to one embodiment, load balancing is performed by changing the core allocation of the threads while allocating a plurality of threads to each core, thereby eliminating the load imbalance. In this case, instead of pausing all the threads, after temporarily stopping each of the individual threads at a predetermined time, after adjusting the core allocation and the core utilization ratio, the suspended thread is executed again.

1B illustrates a multicore system after performing load balancing according to one embodiment.

1B is compared with FIG. 1A, the core allocation of the thread 21 is changed from the first core 110 to the second core 120 according to the modification of the core allocation of the thread according to the embodiment, The core allocation of the first core 110 is changed from the second core 120 to the first core 110. [ In accordance with the change in the core throughput of the thread whose core usage rate of the thread 11 and the thread 21 set to 50% in the first core 110 is changed according to the change of the core allocation, And adjusted to 20% and 80% for the thread 41, respectively. The core utilization rate of the thread 31 and the thread 41 that have been set to 50% in the second core 120 is also 40 (n) for the thread 31 and the thread 21 in accordance with the data throughput change according to the core allocation of the changed thread. % ≪ / RTI > and 60%, respectively.

Therefore, according to the load balancing method according to the embodiment, unnecessary waiting time of other threads can be reduced because there is no global synchronization unlike the conventional method, and the core allocation of some threads among all threads is adjusted The overhead can be reduced.

2 is a block diagram illustrating a configuration of a multicore system for performing load balancing according to an embodiment.

Referring to FIG. 2, the multicore system 200 includes a load management unit 210, a thread load table 220, a scheduler 230, and a multicore processor 240.

The load management unit 210 determines whether or not the loads of the multi-core to which a plurality of threads are allocated per core are unbalanced, and changes the assignment of at least one thread among the plurality of threads to the multi-core when it is determined to be unbalanced Perform load balancing. At this time, the thread allocation for all cores does not need to be changed, and the allocation of some threads of some cores may be changed for load balancing.

The thread load table 220 includes load information corresponding to each thread allocated to the multicore, and the load management unit 210 stores information necessary for load distribution according to load balancing. An example of the information structure included in the thread load table is shown in FIG.

3 is a diagram illustrating an information structure included in a thread load table according to an exemplary embodiment of the present invention.

As shown in FIG. 3, the thread load information includes thread identification information (thread ID) for each thread, load information for the thread, core information allocated to the thread, and utilization information of the core for processing the thread in the core .

Referring again to FIG. 2, a plurality of threads are allocated to each process of the multicore 240 by the scheduler 230. The scheduler 230 loads or unloads the threads to each processor of the multicore 240 based on the allocation and core utilization of the multicore of the plurality of threads determined by the load management unit 210.

If it is determined by the load management unit 210 that the core allocation for at least one thread should be changed for load balancing of each of the multi-cores under the control of the load management unit 210, the scheduler 230 must change the allocation Stopping only the operation of at least one thread, and resuming operation of at least one thread in the core whose allocation has changed after the core allocation is changed. The scheduler 230 can adjust the core allocation and loading of threads in real time using a fair queuing based scheduling method or a lottery scheduling method instead of the priority method.

Although the multicore 230 is shown as including processor 1 241, processor 2 242, processor 3 243 and processor 4 244, the number of processors configured in multicore 230 is limited There is no.

2, the load management unit 210 may include a performance measurement unit 212, a load balancing unit 214, and a core allocation unit 216.

The performance measuring unit 212 measures (or predicts) the load of each thread. In addition, the performance measuring unit 212 updates the thread load table 220 with the measured thread load information. The performance measuring unit 212 determines whether the load between the cores is unbalanced, and transmits a load balancing request to the load balancing performing unit 214 that a new load balancing is required if the inter-core load is determined to be unbalanced. The performance measuring unit 212 can perform load measurement or prediction using various conventional methods. For example, if the value indicating the load imbalance for each core exceeds the set threshold, it can be determined that the load is unbalanced.

The load balancing performing unit 214 eliminates the load imbalance and determines a new policy. In more detail, the load balancing execution unit 214 determines allocation and core utilization ratios of the plurality of threads to the multi-core based on the updated load information, and updates the determined allocation and core utilization ratios to the thread load table 220 . The load balancing performing unit 214 may use a load balancing method according to various existing methods to change a core allocation of a thread for load balancing.

The core allocator 216 applies the last determined policy to each thread.

That is, the core allocator 216 transfers and sets the core allocation and the core utilization rate of the plurality of threads to the scheduler 220 based on the updated allocations and the core utilization rates. The core allocation unit 216 may change the core allocation and core utilization rate information of the determined plurality of threads to a format suitable for the scheduler 220 to process and deliver.

According to one embodiment, a dynamic load balancing scheme is provided that is suitable for MPSoC environments where the cost of core allocation is much less than in a distributed environment, thereby eliminating the idle time of unnecessary threads and reducing the data redistribution overhead between threads. The performance of the embedded system can be improved.

In addition, it provides a load balancing technique with less overhead, so it can provide fine grained load balancing techniques that can be used for load balancing even on a per-loop basis.

4 is a flowchart illustrating a load balancing method of a multicore system according to an embodiment.

If a plurality of threads are allocated to one core in a multi-core (S410), and if it is not a load unbalance in a multi-core (S420), a plurality of threads are scheduled and processed according to a core allocation of determined threads (S450). More specifically, a plurality of threads are loaded on the multicore based on the allocation of the plurality of threads to the multicore and the allocation of the threads, that is, based on the core usage rate determined according to the data processing load of the core allocated thread, do.

If it is determined that the load of the multicore is unbalanced (S 420), load balancing is performed by changing allocation of at least one thread among the plurality of threads to the multicore (S 430). The threads are processed based on the changed core allocation for load balancing (S440). If it is determined that the allocation for at least one thread of the plurality of threads should be changed for load balancing of each of the multi-cores, only the operation of the at least one thread is stopped, and after the core allocation is changed, The operation of the thread of FIG.

In order to change the allocation of at least one thread among the plurality of threads to the multicore, load information corresponding to each thread can be managed. Here, the load information corresponding to the thread may include thread identification information for each thread, load information for the thread, core information allocated to the thread, and utilization information of the core for processing the thread in the core .

One aspect of the present invention may be embodied as computer readable code on a computer readable recording medium. The code and code segments implementing the above program can be easily deduced by a computer programmer in the field. A computer-readable recording medium includes all kinds of recording apparatuses in which data that can be read by a computer system is stored. Examples of the computer-readable recording medium include ROM, RAM, CD-ROM, magnetic tape, floppy disk, optical disk, and the like. The computer-readable recording medium may also be distributed over a networked computer system and stored and executed in computer readable code in a distributed manner.

It will be apparent to those skilled in the art that various modifications and variations can be made in the present invention without departing from the spirit or scope of the invention. Therefore, the scope of the present invention is not limited to the above-described embodiments, but should be construed to include various embodiments within the scope of the claims.

1A and 1B are diagrams illustrating a load balancing technique of a multicore system according to an embodiment,

2 is a block diagram showing a configuration of a multicore system for performing load balancing according to an embodiment,

3 is a diagram illustrating an information structure included in a thread load table according to an embodiment,

4 is a flowchart illustrating a load balancing method of a multicore system according to an embodiment.

Claims (11)

A load balancing apparatus for a multicore system, Determining whether a load of a plurality of threads allocated to a plurality of threads per core is unbalanced, and performing load balancing by changing allocation of at least one thread among the plurality of threads to the multicore when it is determined to be unbalanced ; A thread load table including load information corresponding to each thread allocated to the multicore; And If it is determined by the load management unit that the core allocation for the at least one thread should be changed for load balancing of the multicore, stopping only the operation of at least one thread whose allocation is to be changed, A scheduler for resuming operation of the at least one thread in a core whose allocation has been changed; / RTI > The method according to claim 1, Wherein the scheduler loads or unloads the plurality of threads to the multicore based on an allocation and a core utilization rate of the plurality of threads to the multicore determined by the load management unit. delete The method according to claim 1, Wherein the load information corresponding to the thread includes thread identification information for each thread, load information for the thread, core information allocated to the thread, and utilization information of the core for processing the thread in the core. The method according to claim 1, The load management unit Load on each thread of each core is measured, the measured load-by-thread load information is updated in the thread load table, the load between the cores is determined to be unbalanced, and the load balancing request is transmitted when the inter-core load is determined to be unbalanced Performance Measurement Department; Performing load balancing to receive the load balancing request, determine allocation and core utilization rates for the multi-cores of the plurality of threads based on the updated load information, and update the determined allocation and core utilization rates in the thread load table part; And And a core allocator configured to set a core allocation and a core utilization rate of the plurality of threads based on the updated allocations and core utilization rates. A load balancing method of a load balancing apparatus of a multicore system, Determining whether a load of the multi-core to which a plurality of threads per core is allocated is unbalanced; Stopping only the operation of at least one thread among the plurality of threads when it is determined to be unbalanced; Performing load balancing by changing the allocation of the at least one thread to the multicore; And Resuming the operation of the at least one thread in a core whose allocation has changed after the core allocation is changed; ≪ / RTI > The method according to claim 6, After performing the load balancing, Further comprising loading or unloading the plurality of threads to the multicore based on the allocation of the plurality of threads to the multicore and the core utilization rate. delete The method according to claim 6, After performing the load balancing, Further comprising managing load information corresponding to the thread, Wherein the load information corresponding to the thread includes thread identification information for each thread, load information for the thread, core information allocated to the thread, and utilization information of the core for processing the thread in the core. 10. The method of claim 9, Determining whether the load of each of the multi-cores allocated to a plurality of threads per core is unbalanced, Measuring the load for each thread of each core, updating the measured load information to a thread load table storing load information corresponding to the thread, and Determining whether the load of the multicore is unbalanced based on the measured thread-specific load information, Performing load balancing by changing an allocation of at least one thread among the plurality of threads to the multicore, Determining allocation and core utilization for the plurality of threads based on the updated load information; And And setting core allocation and core utilization of the plurality of threads based on the modified core allocation and core utilization. A computer-readable recording medium having recorded thereon a program for implementing a load balancing method of a multicore system, Determining whether a load of the multi-core to which a plurality of threads per core is allocated is unbalanced; Stopping only the operation of at least one thread among the plurality of threads when it is determined to be unbalanced; Performing load balancing by changing the allocation of the at least one thread to the multicore; And Resuming the operation of the at least one thread in a core whose allocation has changed after the core allocation is changed; ≪ / RTI >

Images