CN109918195B - Processor resource scheduling method for many-core systems based on thermal-aware dynamic task migration - Google Patents

Abstract

The invention discloses a resource scheduling method for many-core system processors based on thermal perception dynamic task migration, which includes the following steps: step 1, detecting whether the waiting sequence is empty; if it is not empty, map the application, and then perform step 2; Whether the arrival queue is empty; if it is not empty, go to step 3; step 3, check whether there is no application running in the system, if not, use the model to estimate the running and waiting time of the bubbles, and search for the best bubble distribution through the branch and bound algorithm Result; Step 4, searching for the best bubble allocation result through the branch-and-bound algorithm; Step 5, applying the mapping stage, and Step 6, applying the running stage. This method utilizes the black silicon phenomenon, adapts to application arrival queues of different lengths according to the application arrival rate and the calculation-sensitive or communication-sensitive characteristics of the application, maintains the task running frequency, can respond to the variable application arrival rate, and effectively improves the system throughput rate , which improves system performance.

Description

Processor resource scheduling method for many-core systems based on thermal-aware dynamic task migration

technical field

The invention relates to the field of communication technology, in particular to a resource scheduling method for many-core system processors based on dynamic task migration based on thermal perception.

Background technique

Many-core chips are one of the processor components in cloud computing, mobile computing and other fields. Many-core processors are widely used in servers, data centers and other fields. Many-core chips are becoming an increasingly important platform in the development of computer systems. With the increase of computing demands of applications, the integration and performance of many-core chips are also continuously improved, followed by the rapid increase of chip power density and temperature, and temperature has become an important factor limiting chip performance. Excessively high temperature for a long time will affect the reliability and service life of many-core chips. Due to the limitation of heat dissipation conditions and to ensure the safety of system operation, power constraints are generally set for chip systems. To meet power constraints while maintaining high-speed computing performance, part of the processor on the chip has to be turned off, which is known as the black silicon phenomenon.

The inactive idle processors in the system-on-a-chip are generally referred to as bubbles. Because the air bubbles dissipate heat better, some practices place the air bubbles around the active processor, causing the processor to run at a higher frequency to increase computing performance. This type of approach is still in the category of static task-processor core mapping. Since the task mapping position is fixed, hot spots may still occur when the operating frequency remains unchanged. Some approaches apply dynamic task migration to reduce hotspots by migrating threads or tasks from overheated cores to other cores when the temperature of the original processor gradually rises above a set temperature threshold. One class of methods tends to choose the processor with the lowest global temperature or randomly select an idle processor as the migration target of the task, which will greatly increase the communication distance. If there are many communications between application tasks, this obviously leads to high communication costs. Another type of method selects a processor adjacent to the overheated processor to migrate tasks each time. After multiple such migrations, a discontinuous free area may be left when the application leaves the system, and the newly arrived or waiting in the queue applications cannot be mapped consecutively to idle processors. Both of the above two types of methods may face the situation that the inter-task communication may pass through multiple processor cores running other applications, resulting in conflicts in the application inter-task communication and reducing the communication efficiency.

Due to the diversity and complexity of user requests, the server system is expected to be able to respond to changing workloads in the shortest possible time. A method of task migration overclocks each processor that is running a task, and migrates all tasks to another contiguous free processor area when the temperature threshold is reached. Although the communication distance between tasks remains unchanged, this type of method is only suitable for systems with low loads. When applications arrive more and require more processor resources, this method of processor resource scheduling with low system utilization It will bring too long application waiting time, offset the performance gain under overclocking, and increase the response time.

The invention patent with the authorized announcement number CN201310059705 discloses a "nuclear resource allocation method, device, and many-core system". The invention patent mainly proposes a nuclear resource allocation method. The number of idle cores) merge the scattered core partitions to assign the formed continuous core partitions to user processes, optimizing the communication cost. According to the core partition migration cost, the method selects a reference core partition and a slave core partition from at least two scattered core partitions, so as to minimize the total core partition migration cost. Secondly, the idle cores of the slave core partition are migrated so that the idle cores of the slave core partition and the idle cores of the reference core partition are merged to form a continuous core partition. The above-mentioned patent mainly integrates on-chip processor resources from the perspective of de-fragmentation, so that the arriving applications can realize continuous mapping. Its disadvantage is that it does not consider the power constraints and temperature constraints of the system, and does not consider the possible temperature peaks and abnormalities. Uniform temperature distribution, risk of system overheating.

None of the above methods for task transfer take the use of bubbles into account. When the black silicon phenomenon exists, how to design the dynamic processor resource scheduling of the many-core system is the key to maintaining its high performance while considering the chip temperature constraints and load.

Contents of the invention

The present invention is a processor resource scheduling method under the black silicon phenomenon, which is implemented in a two-dimensional on-chip network many-core system task scheduling simulation system, which can avoid thermal risks and consider communication costs while maintaining a high processor operating frequency. It is used to improve the throughput of the system.

For this reason, the present invention proposes a resource scheduling method for many-core system processors based on thermal perception dynamic task migration, including the following steps:

Step 1. Check whether the waiting sequence is empty; if it is not empty, map each application in the waiting sequence, and then proceed to step 2; if it is empty, end this resource scheduling, and wait for the start of the next clock cycle to proceed to step 1;

Step 2: Detect whether the arrival queue is empty; if the arrival queue is not empty, proceed to step 3; if the arrival queue is empty, then no new application arrives in this clock cycle, processor resource scheduling is not required, and this resource scheduling ends. When waiting for the start of the next clock cycle, proceed to step 1;

Step 3. Check whether there is no application running in the system. If there is no application running, that is, the N*N processor resources of the system are all available, use the bubble-performance model and the waiting time model to estimate the execution under different bubbles for each application Time and waiting time, as the calculation input of the cost function in the branch and bound, search for the bubble distribution result with the shortest total response time of the application through the branch and bound algorithm, so as to make the total response time the shortest; if there is an application running, go to step 4;

Step 4: If there are applications running, the available processors of the system are divided into a group of discontinuous free available areas by the occupied application areas. The bubble-performance model and the waiting time model are used to estimate the execution time and waiting time under the optional number of bubbles for each application respectively, as the calculation input of the cost function in the branch and bound, and search for the best bubble allocation result through the branch and bound algorithm, so that The overall response time is the shortest.

Step 5, the application mapping stage: using the First-Fit Heuristic algorithm (First-Fit Heuristic) to select the free area, and then selecting the application mapping mode for mapping; the application mapping mode includes a square mapping mode and a communication priority mapping mode;

Step 6: Application running phase: According to the mapping mode of the application and its own calculation-communication rate (CCR) as the basis for selection, the migration mode is selected for different types of applications.

Further, the bubble-performance model is used to calculate the corresponding execution time of each application under different numbers of bubbles, the model is a polynomial regression model, let the execution time of the application be ∏ _i , the number of bubbles b _i contained in the application area, and the application The hop count of the critical path is the hop count h _i of the longest weighted path, the average computing time _ci of the task in the application, and the average communication time t _i of the task in the application. The bubble-performance model is as follows:

为应用i的气泡数的k次方，/>

为应用i关键路径跳数的k次方，/>

为应用i中平均任务计算时间的k次方，/>

为应用i的平均每两个任务间通信时间。Among them, n ₁ to n ₄ are polynomial orders, α _k , β _k , γ _k , and θ _k are the fitting coefficients of the model, and the values are obtained by the maximum likelihood method.

is the kth power of the number of bubbles applied to i, />

is the k-th power of the hop count of the critical path of application i, />

is the kth power of the average task computing time in application i, />

is the average communication time between every two tasks of application i.

Further, the waiting time model is given the area size of the current application, that is, the sum of the number of bubbles and the number of tasks, and is used to calculate the corresponding waiting time of each application under different numbers of bubbles and the current arrival rate. The model is polynomial regression Model, the area of the current application is denoted as R, the total number of processors in the system is denoted as |T|, the average number of tasks of the mapped application is denoted as |A _i |, let the waiting time of the current application be η _i , η _i is given by the following Variable modeling: the average number of bubbles of the mapped application - the ratio of the number of tasks r _i , the average execution time e _i of the mapped application, the application arrival rate λ, and the waiting time model are as follows:

where a ₀ is a constant term, z is the polynomial order, r ^j is the jth power of the average bubble number-task number ratio of the mapped application, e ^j is the jth power of the average execution time of the mapped application, and ^λj is The jth power of the current application arrival rate. δ _j , ε _j , μ _j are the fitting coefficients corresponding to each parameter item obtained by maximum likelihood regression.

Further, the number of application tasks is the number of processors occupied by the application mapping. An application is a collection of multiple small tasks, and each task executes a different part of the application's instructions when running, thereby executing the application in parallel. Each task map occupies one processor core, and the number of application tasks is equal to the number of processors occupied by the application to run.

Further, the optional number of bubbles is the difference between the total number of processors in each free area and the number of application tasks; the number of application tasks is equal to the number of processors occupied by the application to run.

Further, step 3 is implemented by the global manager. When subsequent applications arrive, the global manager counts all available processor areas in the current system, and estimates the execution time corresponding to these available processor areas for each subsequent application. and waiting time, use the branch-and-bound algorithm to find the application-available area correspondence with the least cost.

Further, the specific implementation process of the first adaptation algorithm is: search for idle processors in the system from left to right and from top to bottom, and judge whether it can be used as the starting point of the application area. The condition that can be used as the starting point is that the starting point The product of the number of free processors on the right side of the same row and the number of free processors below the same column is greater than or equal to the area of the application area; when the first processor that can be used as the starting point of the application area is found, this processor is used as the upper left corner The free area of the application is allocated to the application. If no processor can be found that can be used as the starting point of the application area, the application will be put into the waiting queue; after the area is selected, the application will be mapped in the area in the selected mode. The method of selecting the mapping mode of the application is: when the number of bubbles and tasks of the application meet the ratio of 1:1, the application selects the square mapping mode; when the number of bubbles and tasks of the application does not meet the ratio of 1:1, the application selects the mapping of communication priority model.

Further, the migration mode includes three migration modes, namely: square migration mode, the coldest core migration mode in the region, and the coldest neighbor core migration mode in the region; the fifth step is based on the applied mapping mode and its own The calculation volume-communication volume ratio is used as the basis for selection. The maximum number of application bubbles should not exceed the number of tasks. The process of selecting the migration mode is as follows:

If the number of bubbles is equal to the number of tasks, select the square migration mode for the application to keep its communication distance constant during the migration process, and the processor will run overclocked;

If the number of bubbles is not equal to the number of tasks, the communication priority mapping is selected for the application. The threshold value is 2h/(h-1), h is the hop count of the application critical path, that is, the longest path hop count of the weighted path, the coldest core migration area is selected for applications with CCR greater than the threshold value, and the selection area is selected for applications with CCR less than the threshold value Coldest neighbor nuclear migration.

Further, the specific implementation process of the three migration modes is as follows:

(1) Square migration mode, the application needs to meet the square mapping and the size of the application area is at least twice the number of tasks. When calling, unbind all tasks from their current mapped processors, and map tasks to In another free area of the application area;

(2) The coldest core migration mode in the area. When calling, the task ID obtained by hotspot detection is located on the processor that exceeds the temperature threshold, that is, the overheated processor. Then, the processor core with the lowest temperature is searched in the application area. When one is found The migration condition of the processor core with the lowest temperature and the coldest core migration mode in the region, that is, the processor is a bubble, that is, an idle processor without mapping tasks, and there is no mapping task on the processor. The processor is unbound and mapped to the processor. If the migration conditions of the task cannot be met, that is, the coldest core is not a bubble, the overheated processor will be downclocked;

(3) The coldest neighbor core migration mode in the area. When calling, the task ID obtained by hotspot detection is located on the overheated processor, and the processor core with the lowest temperature is searched among the 8 adjacent cores adjacent to the processor. If the searched processor core meets the migration conditions of the coldest neighbor core migration mode in the area, that is, tasks have been mapped on it but the temperature is not higher than two-thirds of the threshold temperature, or the processor is a bubble, that is, idle processing If there is a task in the processor, the tasks on the processor and the overheated processor are exchanged, that is, double unbinding-remapping; if the processor core is in an idle state, a single unbinding Binding-remapping, if the migration condition of the task cannot be met, that is, its temperature is higher than two-thirds of the threshold temperature, the overheated processor will be down-clocked.

Further, the branch-and-bound algorithm is as follows: assign different numbers of bubbles to each application, and calculate the current total response time at each node as a cost function; The maximum sum of waiting time and execution time:

σ=max{η _i +∏ _i }, i∈{0,1,...,n}

Where η _i is the waiting time of application i, and ∏ _i is the execution time of application i. Each time, the branch with the slowest growth in the lower bound is first expanded, and the upper-level nodes that are more costly than the lower-level nodes, that is, the response time is longer, are cut off. Finally, the bubble allocation result with the shortest total response time is obtained, that is, the application area division result.

Further, after the application arrives, the execution time of the application under different numbers of bubbles is estimated and calculated according to the bubble-performance model. The maximum number of bubbles for each application cannot exceed the number of tasks. Estimate the execution time in full migration mode when the number of bubbles is equal to the number of tasks. When the number of bubbles is less than the number of tasks, estimate the execution time in the neighbor’s coldest core task migration mode that is conducive to communication for applications whose CCR is higher than the threshold; estimate the coldest core task migration in the area that is conducive to computing for applications whose CCR is lower than the threshold model.

Further, if the number of processors included in the area is greater than the number of application tasks, the frequency of the active processors in the area is calculated according to the ratio of the number of bubbles in the mapped area to the number of tasks, and the processors are overclocked.

Furthermore, in the application running phase, the system detects hot spots in every control interval. When a hotspot occurs, perform task migration in the corresponding application area according to the selected migration mode.

Further, in the communication priority mapping mode, the node with the largest communication weight is used as the preferred task to map on the processor core near the geometric center of the application area, and the nodes connected to it are sequentially mapped to the available nodes with the shortest Manhattan distance. on the processor core. Secondly, select the mapped parent node of the unmapped task, and map the nodes connected to it to the available processor core with the shortest distance from Manhattan. And so on, until all tasks of the application are mapped to the processor.

Further, in the square mapping mode, the square root of the number of applied tasks is rounded down to the side length, and all tasks are continuously mapped in a rectangular area.

A control interval that is the same as the sampling interval is selected, and whether a processor temperature is higher than a given temperature threshold is detected every time a control interval passes. If not, no task migration is done. If there is a processor core exceeding the temperature threshold, the task mapped on the hotspot is located to the corresponding application, and the task migration is performed according to the selected mode in the event class instance bound to the application. Hotspot detection gives the overheating application ID and its overheating task ID.

By establishing the application bubble-performance model, waiting time model, designing three migration modes and expanding the two-dimensional network-on-chip many-core system. In terms of resource allocation, the black silicon phenomenon is used to obtain better computing performance. In task migration, the migration mode is selected for different types of applications according to the application mapping mode and its own calculation-communication rate (CCR) as the basis for selection. A higher CCR generally means that the computing performance contributes more to the overall performance of the application, and vice versa means that the communication performance is more important in the overall performance.

Compared with the prior art, the present invention has the following beneficial effects:

1. In this scheduling method, bubbles can not only be used for heat dissipation, but also serve as migration objects for tasks on overheated processors.

2. The system can dynamically respond to the current application arrival rate, make full use of the black silicon phenomenon to improve the operating performance of the application when there are few applications, and improve the system utilization rate when there are many applications to avoid excessive waiting time for applications. In general, compared with other traditional task migration methods, the system throughput rate is improved, and the average response time of the application is reduced.

Description of drawings

Fig. 1 is a structural block diagram of the expanded simulation system of the present invention.

Fig. 2 is an example diagram of an algorithm for allocating bubbles in branch boundaries in the present invention.

FIG. 3 is a flow chart of a processor resource scheduling method in the present invention.

Detailed ways

The present invention will be further described in detail below in conjunction with the embodiments and the accompanying drawings, but the embodiments of the present invention are not limited thereto.

In the method for resource scheduling of many-core system processors based on thermal-aware dynamic task migration in this embodiment, application 1 corresponds to a CCR threshold of 2.6, application 2 corresponds to a CCR threshold of 2.6, and application 3 corresponds to a CCR threshold of 2.4. The system scale is 5*5 and contains a total of 25 processor cores. The clock frequency of the processor core is 1GHZ, and the clock cycle is 1 nanosecond.

As shown in Figure 3, the following steps are included:

Step 1. Check whether the waiting sequence is empty; if it is not empty, map each application in the waiting sequence, and then proceed to step 2; if it is empty, end this resource scheduling and wait for the next clock cycle;

Step 2: Detect whether the arrival queue is empty; if the arrival queue is not empty, proceed to step 3; if the arrival queue is empty, then no new application arrives in this clock cycle, processor resource scheduling is not required, and this resource scheduling ends. When waiting for the start of the next clock cycle, proceed to step 1.

Step 3. Check whether there is no application running in the system. If there is no application running, that is, 5*5 processor resources of the system are available, then use the bubble-performance model and the waiting time model to estimate the execution under different bubbles for each application The time and waiting time are used as the calculation input of the cost function in the branch and bound, and the optimal bubble allocation result is searched through the branch and bound algorithm; if there is an application running, go to step 4.

Step 4: If there are applications running, the available processors of the system are divided into a group of discontinuous free available areas by the occupied application areas. Use the bubble-performance model and the waiting time model to estimate the execution time and waiting time under the number of optional bubbles (the number of optional bubbles is the difference between the total number of processors in each free area and the number of application tasks) for each application, as a branch The calculation input of the cost function in the bounds, searches for the best bubble distribution result through the branch and bound algorithm, so that the total response time is the shortest.

Step 5, the application mapping stage: using the First-Fit Heuristic algorithm (First-Fit Heuristic) to select the free area, and then selecting the application mapping mode for mapping; the application mapping mode includes a square mapping mode and a communication priority mapping mode;

Step 6: Application running phase: According to the mapping mode of the application and its own calculation-communication rate (CCR) as the basis for selection, the migration mode is selected for different types of applications.

Further, the bubble-performance model is used to calculate the corresponding execution time of each application under different numbers of bubbles, the model is a polynomial regression model, let the execution time of the application be ∏ _i , the number of bubbles b _i contained in the application area, and the application The hop count of the critical path is the hop count h _i of the longest weighted path, the average computing time _ci of the task in the application, and the average communication time t _i of the task in the application. The bubble-performance model is as follows:

为应用i的气泡数的k次方，/>

为应用i关键路径跳数的k次方，/>

为应用i中平均任务计算时间的k次方，/>

为应用i的平均每两个任务间通信时间。Among them, n ₁ to n ₄ are polynomial orders, α _k , β _k , γ _k , and θ _k are model coefficients, and the values are obtained by the maximum likelihood method.

is the kth power of the number of bubbles applied to i, />

is the k-th power of the hop count of the critical path of application i, />

is the kth power of the average task computing time in application i, />

is the average communication time between every two tasks of application i.

Further, the waiting time model is given the area size of the current application, that is, the sum of the number of bubbles and the number of tasks, and is used to calculate the corresponding waiting time of each application under different numbers of bubbles and the current arrival rate. The model is a polynomial regression Model, the area of the current application is denoted as R, the total number of processors in the system is denoted as |T|, the average number of tasks of the mapped application is denoted as |A _i |, let the waiting time of the current application be η _i , η _i is given by the following Variable modeling: the average number of bubbles of the mapped application - the ratio of the number of tasks r _i , the average execution time e _i of the mapped application, the application arrival rate λ, and the waiting time model are as follows:

where a ₀ is a constant term, z is the polynomial order, r ^j is the jth power of the average bubble number-task number ratio of the mapped application, e ^j is the jth power of the average execution time of the mapped application, and ^λj is The jth power of the current application arrival rate. δ _j , ε _j , μ _j are the fitting coefficients corresponding to each parameter item obtained by maximum likelihood regression.

Further, step 3 is implemented by the global manager, that is, when subsequent applications arrive, the global manager counts all available processor areas in the current system, and estimates the execution corresponding to these available processor areas for each subsequent arriving application Time and waiting time, use the branch and bound algorithm to find the application-available area correspondence with the least cost.

Further, the specific implementation process of the first adaptation algorithm is: search for idle processors in the system from left to right and from top to bottom, and judge whether it can be used as the starting point of the application area. The condition that can be used as the starting point is that the starting point The product of the number of free processors on the right side of the same row and the number of free processors below the same column is greater than or equal to the area of the application area; when the first processor that can be used as the starting point of the application area is found, this processor is used as the upper left corner The free area of the application is allocated to the application. If no processor can be found that can be used as the starting point of the application area, the application will be put into the waiting queue; after the area is selected, the application will be mapped in the area in the selected mode.

The method of selecting the mapping mode of the application is: when the number of bubbles and tasks of the application meet the ratio of 1:1, the application selects the square mapping mode; when the number of bubbles and tasks of the application does not meet the ratio of 1:1, the application selects the mapping of communication priority model.

Further, the migration mode includes three migration modes, namely: square migration mode, the coldest core migration mode in the region, and the coldest neighbor core migration mode in the region; the fifth step is based on the applied mapping mode and its own The calculation volume-communication volume ratio is used as the basis for selection. The maximum number of application bubbles should not exceed the number of tasks. The process of selecting the migration mode is as follows:

If the number of bubbles is equal to the number of tasks, select the square migration mode for the application to keep its communication distance constant during the migration process, and the processor will run overclocked;

If the number of bubbles is not equal to the number of tasks, the communication priority mapping is selected for the application. For applications with a CCR greater than the threshold, select the region's coldest kernel migration, and for applications with a CCR less than the threshold, select the region's coldest neighbor kernel migration.

Further, the specific implementation process of the three migration modes is as follows:

(1) Square migration mode, the application needs to meet the square mapping and the size of the application area is at least twice the number of tasks. When calling, unbind all tasks from their current mapped processors, and map them to another idle area in the application area in sequence. within the area;

(2) The coldest core migration mode in the area. When calling, the task ID obtained by hotspot detection is located on the overheated processor, and then the processor core with the lowest temperature is searched in the application area. When a processor core with the lowest temperature is found and Satisfy the migration conditions, that is, the processor is a bubble, and there is no mapping task on the processor. Unbind the task from the overheated processor and remap it to the processor. If the migration conditions of the task cannot be met, that is, the coldest core is not a bubble, Reduce the frequency of the overheated processor;

(3) The coldest neighbor core migration mode in the area. When calling, the task ID obtained by hotspot detection is located on the overheated processor, and the processor core with the lowest temperature is searched among the 8 adjacent cores adjacent to the processor. If the searched processor core meets the migration conditions, that is, the task has been mapped on it but the temperature is not higher than two-thirds of the threshold temperature, or the processor is a bubble, then the processor is selected as the target processing of the task migration device. If there is already a task in the processor, exchange the tasks on the processor and the overheated processor, that is, perform two unbinding-remapping, unbind the overheated processor from its mapped task X, and unbind the target processor from its mapped task X. Unbind task Y, then remap task X to the target processor, and remap task Y to the overheated processor; if the processor core is an idle processor, perform a single unbind-remap, if not satisfied The migration condition of the task is that its temperature is higher than two-thirds of the threshold temperature, and the overheated processor is frequency-down processed.

Further, after the application arrives, the execution time of the application under different numbers of bubbles is estimated and calculated according to the bubble-performance model. The maximum number of bubbles for each application cannot exceed the number of tasks. Estimate the execution time in full migration mode when the number of bubbles is equal to the number of tasks. When the number of bubbles is less than the number of tasks, estimate the execution time in the neighbor’s coldest core task migration mode that is conducive to communication for applications whose CCR is higher than the threshold; estimate the coldest core task migration in the area that is conducive to computing for applications whose CCR is lower than the threshold model.

Further, if the number of processors included in the area is greater than the number of application tasks, the frequency of the active processors in the area is calculated according to the ratio of the number of bubbles in the mapped area to the number of tasks, and the processors are overclocked.

Furthermore, the system detects hotspots at every control interval during the application run phase. When a hotspot occurs, perform task migration in the corresponding application area according to the selected migration mode.

Further, in the communication priority mapping mode, the node with the largest communication weight is used as the preferred task to map on the processor core near the geometric center of the application area, and the nodes connected to it are sequentially mapped to the available nodes with the shortest Manhattan distance. on the processor core. Secondly, select the mapped parent node of the unmapped task, and map the nodes connected to it to the available processor core with the shortest distance from Manhattan. And so on, until all tasks of the application are mapped to the processor.

Further, in the square mapping mode, the square root of the number of applied tasks is rounded down to the side length, and all tasks are continuously mapped in a rectangular area.

A control interval that is the same as the sampling interval is selected, and whether a processor temperature is higher than a given temperature threshold is detected every time a control interval passes. If not, no task migration is done. If there is a processor core whose temperature exceeds the threshold of 80 degrees Celsius, the task mapped on the hot spot is located to the corresponding application, and the task migration is performed according to the selected mode in the event class instance bound to the application. Hotspot detection gives the overheating application ID and its overheating task ID.

The present invention is implemented in a simulation system, referring to Fig. 1, this two-dimensional many-core system task scheduling simulation system includes an application generator, an event-driven simulated multi-core system, and a HotSpot (Chinese name hot spot) temperature simulator is an American Virginia The temperature simulation model developed by the university using the resistance-capacitance equivalent model is accurate and fast, and the latest version of the HotSpot6.0 temperature simulator is used. The task graph is randomly generated by the application generator, that is, the number of tasks and task calculations (range 100-800) of the simulated application, the communication topology between tasks and the communication amount of each communication edge (range 50-500), the task graph is Expressed as a directed acyclic graph with weights, it contains the calculation amount of each task and the communication dependencies between tasks.

The event-driven simulated multi-core system simulates the binding relationship between a single task instance and a simulated processor, as well as the task execution calculation and inter-task communication. Processor resource scheduling algorithms include allocation bubbles to applications, task mapping, and task run migration simulation. Task mapping is implemented by single-task-single-processor bindings. When the application finishes running, the processors occupied by its tasks are released. When the simulation task is running, the calculation speed of the task is equal to the operating frequency of the corresponding processor (the operating frequency of each analog processor in the system can be adjusted), and the communication speed between each pair of tasks is equal to the routing frequency of the processor/corresponding Manhattan distance between two processors.

In the task mapping phase, two optional mapping methods are provided, square mapping and communication-first mapping:

Square mapping simply maps all the tasks of the application sequentially in an approximate square area in order of serial number, which accounts for half of the overall application area (allocated free continuous processor area).

Communication priority mapping first creates three dynamic arrays MAP, MET, and UNM to represent mapped tasks, tasks connected to mapped tasks (that is, with communication), and other tasks not in the first two queues. Nodes represent analog processors. During initialization, select the approximate geometric center of the application area (allocated free continuous processor area) as the first node, select the task with the highest cumulative traffic as the preferred task and map it to the first node, and put it into the MAP array. Put all the tasks connected with the preferred task into the MUP array in turn, and put the remaining tasks into the UNM array. For the first task in the MET, find its parent task and the corresponding node in the MAP, and start searching from the nodes whose Manhattan distance is 1, 2, 3, ... until the first available node is found , map the tasks in the MET array on the nodes, move them from the MET to the MAP array, and move the tasks connected to it and in the UNM from the UNM to the MET. Perform the above steps for each node in the MET until the size of the MAP array is equal to the number of tasks applied, and the mapping is completed.

According to the power model of a single processor, the power of each processor in the many-core system is calculated in every microsecond as the power trace at the current moment. With a fixed time period as the sampling interval, the HotSpot temperature emulator is called to simulate the system temperature every time a sampling interval passes, and the power trajectory at each moment of the system running time is used as input, and Hotspot returns each processor in the system at that moment The instantaneous simulated temperature of the nucleus. When the temperature of a certain processor exceeds the set temperature threshold, the application corresponding to the hotspot will perform task migration.

In the task migration phase, three optional migration modes are provided, the square migration mode, the coldest core migration mode in the area, and the coldest neighbor core migration mode in the area.

The square migration mode is based on the square mapping, and migrates the task mapped as a rectangle to another rectangular area in the application area as a whole.

The coldest core migration mode in the area searches for the processor core with the lowest temperature in the application area. When a processor core with the lowest temperature is found and the migration conditions are met, the overheated task is migrated to the coldest core.

The coldest neighbor core migration mode in the area searches for the processor core with the lowest temperature among the 8 cores adjacent to the overheated processor. If a certain temperature condition is met, the tasks on this processor and the overheated processor are exchanged, and the The frequency of the overheated processor.

Figure 2 shows an example where after the system first arrives at three applications, different numbers of bubbles are assigned to the three applications according to the branch-and-bound algorithm to obtain the shortest overall response time.

Application 1 contains seven tasks, and the execution times corresponding to bubbles 0, 1, 3, 5, and 7 obtained from the bubble-performance model are 80, 76, 62, 51, and 40 respectively (for simplified representation, only those that can form regular regions are considered number of bubbles, the longest side of the application area is less than the side length of the system).

Application 2 contains five tasks. According to the bubble-performance model, the execution times corresponding to bubbles 0, 1, 3, 4, and 5 are 300, 275, 250, 217, and 150, respectively.

Application 3 contains eight tasks. According to the bubble-performance model, the execution times corresponding to bubbles 0, 1, 2, 4, 6, and 8 are 195, 184, 166, 147, 125, and 99, respectively.

In the embodiment, b1, b2, and b3 represent the bubbles allocated to application 1, the bubbles allocated to application 2, and the bubbles allocated to application 3, respectively. According to the characteristics of the branch-and-bound method, the branch with the slowest growth in response time is preferentially expanded each time (the total response time is the lower bound), and the upper-level branch whose lower bound is greater than the lower bound of the lower-level branch is pruned (such as the lower bound of the first branch of the third layer is 195, Prune all branches with a lower bound greater than 195 on the second level). Find the branch with the shortest total response time in the bottom layer, which is the optimal solution. In the embodiment, the optimal solution of the total response time is 165, and all branches whose lower bound is greater than the optimal solution are pruned. The bubbles corresponding to the optimal solution are assigned to three applications, and the bubbles corresponding to the optimal solution in the embodiment are {b1=7, b2=5, b3=6}. As shown in Figure 2, the ancestor node corresponding to the optimal solution node is b1=7, that is, 7 bubbles are allocated to application 1, and the corresponding parent node is b2=5, that is, 5 bubbles are allocated to application 2, and the node itself corresponds to b3=6, that is Dispense 6 bubbles to Application 3.

Application area division and resource scheduling are as follows: the application area of application 1 needs to map 7 tasks and contain 7 bubbles, and allocate a processor area with a size of 14 for it. The first adaptation algorithm searches for 3*5 continuous free areas for it ( One of the processors is not occupied); the application area of application 2 needs to map 5 tasks and contain 5 bubbles, and allocate a processor area with a size of 10 for it, and the first adaptation algorithm searches for 2*5 continuous free areas for it ; The application area of application 3 needs to map 8 tasks and contain 6 bubbles. There is not enough free area in the system, and application 3 is waiting in the queue.

For application 1, the number of tasks is equal to the number of bubbles, and it is mapped to the area according to the square mapping mode, and the square migration mode is selected, and application 1 starts running; for application 2, the number of tasks is equal to the number of bubbles, and it is mapped according to the square mapping mode Map to the region, and select the square migration mode, and application 2 starts running.

Application 1 finishes running first, and the processor cores occupied by its application area are released. The application area of application 3 needs to map 8 tasks and contain 6 bubbles, and allocate 14 continuous free processor areas for it, and the first adaptation algorithm searches for 3*5 free areas for it.

For application 3, the number of bubbles is less than the number of tasks, and they are mapped to the area according to the communication priority mapping mode. Its CCR is calculated to be 3.2 greater than the threshold, and the coldest core migration mode in the region is selected for it, and application 3 starts running.

The above content is a detailed description of the present invention in conjunction with specific implementation modes, but it cannot be assumed that the specific implementation of the present invention is limited to this content. For those skilled in the art to which the present invention belongs, several adjustments, modifications, substitutions and/or variations can be made to these implementations without departing from the principle and spirit of the present invention. The protection scope of the present invention is defined by the appended claims and their equivalents.

Claims (4)

1. The method for scheduling the processor resources of the many-core system based on the thermal perception dynamic task migration is characterized by comprising the following steps:

step one, detecting whether a waiting sequence is empty; if not, mapping each application in the waiting sequence, and then carrying out the second step; if the clock is empty, ending the resource scheduling, and waiting for the starting of the next clock cycle, and performing the step one;

step two, detecting whether an arrival queue is empty; if the queue is not empty, performing a third step; if the arrival queue is empty, no new application arrives in the clock cycle, the resource scheduling of the processor is not needed, the resource scheduling is ended, and the step one is carried out when the next clock cycle is waited to start;

detecting whether no application is running in the many-core system, if no application is running, using a bubble-performance model and a waiting time model to estimate the execution time and the waiting time under different bubbles for each application respectively, and searching a bubble distribution result with the shortest total response time of the application through a branch limit algorithm, wherein the execution time and the waiting time are used as calculation input of a cost function in a branch limit; if the application runs, performing a fourth step;

the bubble-performance model is used for calculating the corresponding execution time of each application under different numbers of bubbles, and is a polynomial regression model, so that the execution time of the application is pi _i Number of bubbles contained in application area b _i The critical path hop count of the application, i.e. the path hop count h with the longest weighted path _i Average computation time c of tasks in application _i Task average communication time t in application _i The bubble-performance model is as follows:

wherein n is ₁ ～n ₄ Is polynomial order, alpha _k ,β _k ,γ _k ,θ _k The fitting coefficient of the model is obtained by a maximum likelihood method;

to the k-th power of the number of bubbles applying i, < >>

To the k-th power of the number of hops applying the i critical path,/-th>

Computing the k-th power of the time for the average task in application i,/-th>

Average inter-task communication time per two tasks for application i;

the waiting time model is given to the sum of the area size of the current application, namely the bubble number and the task number, and is used for calculating the waiting time of each application corresponding to different bubble numbers and the current arrival rate, the model is a polynomial regression model, the area of the current application is recorded as R, the total number of processors of the system is recorded as |T|, and the average task number of the mapped application is recorded as |A _i Let the waiting time of the current application be eta _i ，η _i Modeling was performed by the following variables: r is the average bubble number-task number ratio of the mapped application, e is the average execution time of the mapped application, λ is the application arrival rate, and the waiting time model is as follows:

wherein a is ₀ Is a constant term, z is a polynomial order, r ^j To the power j, e of the average bubble number-task number ratio of the mapped application ^j To the power j, λ of the average execution time of the mapped application ^j J is a value from 1 to z to the power j of the arrival rate of the current application, delta _j ，ε _j ，μ _j Fitting coefficients of parameter items obtained by maximum likelihood regression;

step four: if the application runs, the available processor of the system is divided into a group of discontinuous idle available areas by the occupied application area, the execution time and the waiting time under the selectable bubble number are estimated for each application by using a bubble-performance model and a waiting time model respectively, the execution time and the waiting time are used as the calculation input of a cost function in a branch limit, and the optimal bubble distribution result is searched by a branch limit algorithm;

fifth, the mapping stage is applied: selecting an idle area by adopting a first-time adaptive heuristic algorithm, and then selecting an applied mapping mode for mapping; the first adaptation heuristic algorithm is as follows: searching idle processors from left to right and from top to bottom in the system, judging whether the idle processors can be used as a starting point of an application area, wherein the condition that the starting point can be used as the starting point is that the product of the number of idle processors on the right side of the same row and the number of idle processors under the same row is larger than or equal to the area of the application area; when a first processor which can be used as the starting point of the application area is found, the processor is used as the idle area at the leftmost upper corner to be distributed to the application, and if the processor which can be used as the starting point of the application area is not found, the application is put into a waiting queue; after the region is selected, mapping the application in the selected mode in the region; the mode of selecting the mapping mode of the application is as follows: when the number of bubbles and tasks applied satisfies 1:1, selecting a square mapping mode by application; when the number of bubbles and tasks applied does not satisfy 1:1, applying a mapping mode for selecting communication priority;

step six, application operation phase: selecting a migration mode for different types of applications according to the mapping mode of the application and the calculation amount-traffic ratio (Computation communication rate, CCR) of the application as selection basis; the migration modes comprise three migration modes, namely: square migration mode, coldest core migration mode in area and coldest neighbor core migration mode in area;

the specific implementation process of the three migration modes is as follows:

(1) The square migration mode is applied, the square mapping is required to be met, the size of an application area is at least twice the number of tasks, all tasks are unbinding with a currently mapped processor when the application is called, and the tasks are mapped into an idle area of the application area in sequence according to the sequence of task serial numbers;

(2) The method comprises the steps that a coldest core migration mode in an area is located on a processor which is a overheat processor and is obtained through hot spot detection when the coldest core migration mode is called, then the processor core with the lowest temperature is searched in an application area, when a lowest-temperature processor core is found and migration conditions of the coldest core migration mode in the area are met, namely the processor is an air bubble, namely an idle processor without a mapping task, the processor is not mapped with the mapping task, the task and the overheat processor, namely the original processor are unbinding and mapped to the processor, and if migration conditions of the coldest core migration mode in the area cannot be met, namely the coldest core is not an air bubble, the overheat processor is subjected to down-conversion treatment;

(3) The method comprises the steps that a coldest neighbor core migration mode in an area is located on a overheat processor when a task ID obtained through hot spot detection is called, the processor core with the lowest temperature is searched in 8 adjacent cores adjacent to the processor, if the searched processor core meets the migration condition of the coldest neighbor core migration mode in the area, namely, the task is mapped on the processor core but the temperature of the processor core is not higher than two thirds of the threshold temperature, or the processor is a bubble, the task migration is executed, and if the task is already in the processor, the tasks on the processor and the overheat processor are exchanged, namely, double unbinding-remapping is carried out; if the processor core is in an idle state, executing single unbinding-remapping, and if the migration condition of the task cannot be met, namely the temperature of the processor core is higher than two thirds of the threshold temperature, performing down-conversion treatment on the overheat processor;

step five, according to the mapping mode of the application and the calculation amount-traffic ratio of the application, the maximum number of bubbles of each application must not exceed the task number, and the condition of selecting the migration mode is as follows:

if the number of bubbles is equal to the number of tasks, a square migration mode is selected for the application to keep the communication distance unchanged in the migration process, and the processor operates in an over-frequency mode;

if the bubble number is not equal to the task number, selecting the coldest core migration of the area for the application with the CCR larger than the threshold value, selecting the coldest neighbor core migration of the area for the application with the CCR smaller than the threshold value, wherein the threshold value is 2 h/(h-1), and h is the hop number of the application critical path, namely the longest path hop number of the weighted path.

2. The method according to claim 1, wherein step three is implemented by a global manager, and when the subsequent applications arrive, the global manager counts all available processor areas in the current system, estimates the execution time and the waiting time corresponding to the available processor areas for each subsequent arriving application, and finds the application-available area correspondence relationship with the minimum cost by a branch limit algorithm.

3. The processor resource scheduling method of claim 1, wherein the branch boundary algorithm is: allocating a different number of bubbles for each application, calculating a current total response time at each node as a cost function; the total response time σ is the maximum of the sum of the latency and execution time of the application at the node to which the bubble has been allocated:

σ＝max{η _i +Π _i }，i∈{0,1,…,n}

wherein eta _i To apply i's latency, pi _i The execution time for application i; and (3) expanding branches with slowest lower bound growth in priority each time, cutting off upper nodes with higher cost than the next nodes, namely longer response time, and finally obtaining a bubble distribution result with shortest total response time, namely an application region division result.

4. The processor resource scheduling method according to claim 1, wherein the selectable number of bubbles is a difference between a total number of processors per free area and a number of application tasks; the number of application tasks refers to the number of processors that are equal to the number of processors that the application is running.

Images