技术领域technical field
本发明涉及计算机软件调度节能领域，尤其涉及一种云环境下模块化并行作业的动态节能调度方法。The invention relates to the field of computer software scheduling and energy saving, in particular to a dynamic energy-saving scheduling method for modularized parallel operations in a cloud environment.
背景技术Background technique
随着云计算、信息服务、Web2.0、SaaS、互联网+等理念和技术的快速发展，以及大数据平台的出现，并行算法得到了广泛应用。由于并行算法节省了大量的时间，在不同行业均有了优越的表现，例如气象，遥感，军事等。编写并行算法对于非计算机专业的研究人员是件困难的事，因此，在非计算机行业，更多的采用的是模块化并行算法。模块化并行算法的优点是将数据广播，消息传递，计算同步等同步控制信息隐藏起来，保证非计算机行业的科学家，按照自己的思路编写并行程序，减少专业问题之外的内容。同时，模块化并行算法能耗也越来越大。并行作业的节能调度与传统的并行任务调度(非以节能为目地)相比，主要目标不是减少任务总体完成时间(调度长度)，而是尽量减少使用资源数目和占用时间，提高资源利用率，达到整个系统性能和能耗之间的平衡。With the rapid development of concepts and technologies such as cloud computing, information services, Web2.0, SaaS, and Internet+, as well as the emergence of big data platforms, parallel algorithms have been widely used. Since the parallel algorithm saves a lot of time, it has excellent performance in different industries, such as meteorology, remote sensing, military and so on. Writing parallel algorithms is difficult for non-computer professionals. Therefore, in non-computer industries, more modular parallel algorithms are used. The advantage of the modular parallel algorithm is that it hides synchronous control information such as data broadcasting, message transmission, and computing synchronization, so that scientists who are not in the computer industry can write parallel programs according to their own ideas and reduce content other than professional issues. At the same time, the energy consumption of modular parallel algorithms is also increasing. Compared with the traditional parallel task scheduling (not for the purpose of energy saving), the energy-saving scheduling of parallel jobs is not to reduce the overall task completion time (scheduling length), but to minimize the number of resources used and occupied time, and improve resource utilization. To achieve a balance between the overall system performance and energy consumption.
现有方法大多数需要知道程序的结构图，实际上，程序的结构图本身可能非常复杂，对其调度，计算复杂度很高。本发明提出了模块化并行程序的调度方法，模块化并行程序的各个作业同时获得资源，作业完成后，同时释放资源。Most of the existing methods need to know the structure graph of the program. In fact, the structure graph of the program itself may be very complex, and its scheduling has a high computational complexity. The invention proposes a scheduling method for a modularized parallel program. Each job of the modularized parallel program obtains resources at the same time, and releases the resources at the same time after the jobs are completed.
发明内容Contents of the invention
发明目的：本发明目的是提供一种云环境下模块化并行作业的动态节能调度方法。Purpose of the invention: The purpose of the invention is to provide a dynamic energy-saving scheduling method for modularized parallel jobs in a cloud environment.
技术方案：本发明包括以下步骤：Technical solution: the present invention comprises the following steps:
(1)根据系统日志，计算系统平均负载及作业平均并行度；(1) According to the system log, calculate the average load of the system and the average degree of parallelism of the job;
(2)根据系统的平均负载，寻找资源的参考工作状态，包括计算资源的工作频率与工作电压；(2) According to the average load of the system, find the reference working status of the resource, including the working frequency and working voltage of the computing resource;
(3)假设资源工作在参考工作状态下，且作业的并行度为平均并行度，计算此时作业的能耗及工作量；(3) Assuming that the resource is working in the reference working state, and the parallelism of the job is the average parallelism, calculate the energy consumption and workload of the job at this time;
(4)与步骤(3)得到的结果进行对比，寻找可能比步骤(3)更小能耗的调度方法，若有更新调度方法，若没有则采取步骤(3)的方法。(4) Compare with the results obtained in step (3), find a scheduling method that may consume less energy than step (3), if there is an updated scheduling method, if not, take the method of step (3).
所述步骤(1)中系统平均负载及作业平均并行度的计算以资源作业的实际计算量为准。In the step (1), the calculation of the average system load and the average degree of parallelism of the job is based on the actual calculation amount of the resource job.
所述步骤(2)中的参考工作状态是在满足系统平均负载且系统总能耗最小时，资源的工作状态。The reference working state in the step (2) is the working state of the resources when the average load of the system is satisfied and the total energy consumption of the system is minimum.
所述步骤(2)中参考工作状态的寻找采用全局查找方法。The search for the reference working state in the step (2) adopts a global search method.
所述步骤(4)中的调度方法为：先选择可以满足当前作业的资源种类，再根据作业的时间期限与能耗要求，进行进一步调度。The scheduling method in the step (4) is: first select the type of resources that can satisfy the current job, and then perform further scheduling according to the time limit and energy consumption requirements of the job.
有益效果：本发明不需要知道作业的内部结构，控制简单，首先从全局计算能耗，使能耗处于较低的水平，通过节省资源，实现作业的动态调度。Beneficial effects: the invention does not need to know the internal structure of the job, and the control is simple. Firstly, the energy consumption is calculated from the whole, so that the energy consumption is at a lower level, and the dynamic scheduling of the job is realized by saving resources.
附图说明Description of drawings
图1为本发明的流程图；Fig. 1 is a flowchart of the present invention;
图2为本发明的实施流程图。Fig. 2 is the implementation flowchart of the present invention.
具体实施方式Detailed ways
下面结合附图对本发明作进一步说明。The present invention will be further described below in conjunction with accompanying drawing.
如图1所示，本发明包括以下步骤：As shown in Figure 1, the present invention comprises the following steps:
(1)根据系统日志，计算系统平均负载及作业平均并行度，其计算以资源作业的实际计算量为准：(1) According to the system log, calculate the average load of the system and the average degree of parallelism of the job. The calculation is based on the actual calculation amount of the resource job:
假设系统已经完成了NUMJ(1≤temp≤NUMJ)个作业：Suppose the system has completed NUMJ (1≤temp≤NUMJ) jobs:
J＝{j1，...，jtemp，...jNUMJ} (1)J={j1 ,...,jtemp ,...jNUMJ } (1)
对于这些作业，其分配资源数量为：For these jobs, the assigned resource quantities are:
R＝{r1，...，rtemp，...rNUMJ} (2)R={r1 ,...,rtemp ,...rNUMJ } (2)
这些资源的工作频率及工作电压分别是F及V(计算资源的工作频率及工作电压一经分配，不再改变)：The operating frequency and operating voltage of these resources are F and V respectively (the operating frequency and operating voltage of computing resources will not change once allocated):
F＝{f1，...，ftemp，...fNUMJ} (3)F={f1 ,...,ftemp ,...fNUMJ } (3)
则总的计算耗费为CS：Then the total calculation cost is CS:
总的执行时间是et，则平均负载AL为:The total execution time is et, then the load average AL is:
对于模块化并行作业jtemp，假设它的并行度为(1,pltemp)：For a modular parallel job jtemp , assuming its degree of parallelism is (1,pltemp ):
其中：表示作业jtemp在并行度为时，执行时间为in: Indicates that the parallelism of job jtemp is , the execution time is
对于作业集合J，其实际的并行度为：For job set J, its actual parallelism is:
J＝{sl1，...，sltemp，...slNUMJ} (7)J = {sl1 ,..., sltemp ,...slNUMJ } (7)
则所有作业平均并行度(在实际调度时，我们认为这个是参考并行度)为：Then the average parallelism of all jobs (in actual scheduling, we consider this to be the reference parallelism) is:
(2)根据系统的平均负载，寻找资源的参考工作状态，包括计算资源的工作频率与工作电压，参考工作状态指当系统负载工作在平均水平时，使整个系统的能耗处于最低的工作状体。(2) According to the average load of the system, find the reference working state of the resource, including the working frequency and voltage of the computing resource. The reference working state refers to the working state where the energy consumption of the entire system is at the lowest when the system load is working at an average level. body.
根据DVFS模型，计算资源Pdy的动态能耗为:According to the DVFS model, the dynamic energy consumption of the computing resource Pdy is:
Pdy＝αClVs2fs (9)Pdy =αCl Vs2 fs (9)
其中，α，Cl，Vs及fs分别表示计算资源的翻转率，负载电容的容值，工作电压，工作频率。其中，一般把αCl当作常数。Among them, α, Cl , Vs and fs represent the turnover rate of the computing resources, the capacitance of the load capacitor, the operating voltage, and the operating frequency, respectively. Among them, αCl is generally regarded as a constant.
基于上述资源的动态能耗的计算方法，模块化并行作业的动态能耗为：Based on the calculation method of dynamic energy consumption of the above resources, the dynamic energy consumption of modular parallel jobs is:
其中，st，num，Ns分别表示计算资源的时钟周期，分配资源数量及计算需要的周期个数(slot)；分别表示资源在相应的时钟周期内的工作状态(电压、工作频率)。Among them, st, num, and Ns represent the clock cycle of computing resources, the number of allocated resources, and the number of cycles (slots) required for computing, respectively; Respectively represent the working state (voltage, working frequency) of the resource in the corresponding clock cycle.
由于计算资源的静态能耗Pst是常值，所以静态能耗Est仅同计算时间及资源类型相关。Since the static energy consumption Pst of computing resources is a constant value, the static energy consumption Est is only related to computing time and resource type.
Est＝st*num*Pst (11)Est ＝st*num*Pst (11)
模块化并行作业的计算能耗为E：The computational energy consumption of a modular parallel job is E:
E＝Edy+Est (12)E＝Edy +Est (12)
假设计算资源类型A(CPU类型)，具有nums个工作状态：Suppose computing resource type A (CPU type) has nums working states:
A＝{(v1，f1，p1)，...，(vtemp，ftemp，ptemp)，...(vnums，fnums，fnums)} (13)A={(v1 , f1 , p1 ), ..., (vtemp , ftemp , ptemp ), ... (vnums , fnums , fnums )} (13)
其中，vtemp，ftemp，ptemp分别表示资源工作电压，工作频率及相应的功耗。Wherein, vtemp , ftemp , and ptemp represent resource operating voltage, operating frequency, and corresponding power consumption, respectively.
假设系统总共有NUMK种资源，类型A类资源共有num(A)种。首先对所有资源按照ptemp/vtemp升序排列，平均功耗越低，说明其效率越高。假设公式(10)中，已经完成按平均功耗从低到高的排列顺序。Assume that the system has a total of NUMK resources, and there are num(A) resources of type A. First, arrange all resources in ascending order of ptemp /vtemp , the lower the average power consumption, the higher the efficiency. Assume that in the formula (10), the order of the average power consumption from low to high has been completed.
参考工作状态指当系统负载工作在平均水平时，使整个系统的能耗处于最低的工作状体。根据这个目标，采用全局查找方法，查找需要的资源(类型及数量)及其工作状态。假设系统总共有NUMK种资源，第i种资源共有num(i)个资源，并具有nums(A)个状态，假设R是所有资源的集合：R＝[1，2...，NUMK]。The reference working state refers to the working state that keeps the energy consumption of the entire system at the lowest level when the system load is working at an average level. According to this goal, use the global search method to find the required resources (type and quantity) and their working status. Assume that the system has NUMK resources in total, and the i-th resource has num(i) resources and nums(A) states. Suppose R is a collection of all resources: R=[1, 2..., NUMK].
对于这些资源，采用算法生成所有可能的排列组合，以此组合作为排列顺序：sol＝perms(R)。For these resources, an algorithm is used to generate all possible permutations and combinations, and this combination is used as the permutation order: sol=perms(R).
sol的行数即为可能的调度顺序，总共有Πnum(i)种可能性。假设row(sol)为获得排列组合的行数，下列算法为获得参考工作状态的具体过程：The number of rows in sol is the possible scheduling sequence, and there are Πnum(i) possibilities in total. Assuming that row(sol) is the number of rows obtained for permutation and combination, the following algorithm is the specific process for obtaining the reference working status:
算法1：Algorithm 1:
根据以上方法，资源调度顺序存储于第selrid个组合，相应的资源工作状态存于每一种资源数量存于rnum中。以此方法，完成资源的参考工作状态的计算。According to the above method, the resource scheduling sequence is stored in the selrid combination, and the corresponding resource working status is stored in The quantity of each resource is stored in rnum. In this way, the calculation of the reference working state of the resource is completed.
(3)假设作业工作在平均并行度下，资源工作在参考状态下，计算其能耗，及计算总量耗费，并对其时间期限进行判断，判断是否能按要求完成。(3) Assuming that the job is working under the average degree of parallelism and the resource is working in the reference state, calculate its energy consumption and total consumption, and judge its time limit to determine whether it can be completed as required.
其中参考状态能耗计算方式为：平均并行度*资源参考状态下功耗*计算时间。平均并行度为资源数量。计算总量耗费为：平均并行度*资源参考状态下工作频率*计算时间。The energy consumption in the reference state is calculated as: average degree of parallelism * power consumption in the resource reference state * computing time. The average degree of parallelism is the number of resources. The total calculation cost is: average parallelism * operating frequency in resource reference state * calculation time.
(4)基于参考工作状态的资源调度方法为：(4) The resource scheduling method based on the reference working state is:
以上部分已经从全局角度完成了资源的参考状态的计算，但是对于各个作业，由于其本身的特点，时间要求，具体算法，需要进一步调整。对于作业集合J，其对应的时间期限为：The above part has completed the calculation of the reference state of resources from a global perspective, but for each job, due to its own characteristics, time requirements, and specific algorithms, further adjustments are required. For job set J, the corresponding time limit is:
D＝{d1，...，dtemp，...dNUMJ}D={d1 , . . . , dtemp , . . . dNUMJ }
在调度过程中，用一个参数saver计算当前作业节省的资源(以参考工作状态的频率为标准)。其调度方法为：先选择可以满足当前作业的资源种类，再根据时间作业的时间期限，能耗要求，进行进一步调度：如果某个方法(作业的并行度，资源的工作状态)比参考状态、平均并行度情况下更能节省能耗，并节省标准工作能源，那么就选择它，并计算saver；否则按照参考电压及工作状态执行。In the scheduling process, a parameter saver is used to calculate the resources saved by the current job (based on the frequency of the reference work status). The scheduling method is: first select the type of resources that can satisfy the current job, and then perform further scheduling according to the time limit of the time job and energy consumption requirements: if a certain method (the degree of parallelism of the job, the working status of the resource) is better than the reference status, In the case of average parallelism, it can save more energy consumption and standard work energy, then select it and calculate the saver; otherwise, execute according to the reference voltage and working state.
其具体算法如下：The specific algorithm is as follows:
算法2：Algorithm 2:
图2为本发明的实施流程图：Fig. 2 is the implementation flowchart of the present invention:
1.从历史数据收集所有作业J的分配资源数量R，资源工作频率信息F，并将这些信息作为中心调度的基础信息，以后执行的作业，不断更新历史数据，作为未来调度依据；1. Collect the number of allocated resources R and resource operating frequency information F of all jobs J from historical data, and use these information as the basic information for central scheduling, and continuously update historical data for future jobs to be used as the basis for future scheduling;
2.根据步骤1获得的历史数据，计算平均负载AL，平均并行度AP；2. Calculate the average load AL and average parallelism AP based on the historical data obtained in step 1;
3.根据历史信息计算资源的参考工作状态，即每一种资源的工作频率与工作电压，参考状态是在满足系统平均负载情况下，各种计算资源调度的数量及处于的工作状态(工作频率、工作电压等)，算法一给出了具体的过程，其具体方法为假设系统的负载为平均负载，通过计算资源可能的分配数量与工作状态，寻找最小能耗时的相关参数(选择计算资源种类、数量及其工作状态等)；3. Calculate the reference working status of resources based on historical information, that is, the working frequency and working voltage of each resource. The reference status is the number of various computing resource scheduling and the working status (working frequency) under the condition of meeting the average load of the system. , working voltage, etc.), Algorithm 1 gives a specific process, the specific method is assuming that the load of the system is an average load, by calculating the possible allocation of resources and the working status, to find the relevant parameters of the minimum energy consumption (select computing resources type, quantity and working status, etc.);
4.根据步骤3，假设工作在参考状态下，作业具有平均并行度情况下的能耗seg，及计算总量sin；4. According to step 3, assuming that the work is in the reference state and the job has an average degree of parallelism, the energy consumption seg and the total amount of calculation sin;
5.寻找作业的工作状态，使能耗及计算总量分别小于上一步的结果，若找到，则用新的调度方法替换，算法2给出了具体过程，其具体过程为：通过改变计算资源数量、模块化并行作业并行度、计算资源工作状态，计算不同情况下的能耗及计算规模，如果两者分别小于能耗及计算规模则采取新的调度方案；5. Find the working status of the job, so that the energy consumption and the total calculation amount are respectively smaller than the results of the previous step. If found, replace it with a new scheduling method. Algorithm 2 gives the specific process. The specific process is: by changing the computing resources Quantity, parallelism of modularized parallel jobs, working status of computing resources, and energy consumption and computing scale in different situations are calculated. If the two are less than energy consumption and computing scale, a new scheduling scheme is adopted;
6.经过一定时间段后，重新收集历史数据，转至第一步。6. After a certain period of time, collect historical data again and go to the first step.
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201810419583.XACN108829500B (en) | 2018-05-04 | 2018-05-04 | A dynamic energy-saving scheduling method for modular parallel jobs in cloud environment |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201810419583.XACN108829500B (en) | 2018-05-04 | 2018-05-04 | A dynamic energy-saving scheduling method for modular parallel jobs in cloud environment |
| Publication Number | Publication Date |
|---|---|
| CN108829500Atrue CN108829500A (en) | 2018-11-16 |
| CN108829500B CN108829500B (en) | 2022-05-27 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201810419583.XAActiveCN108829500B (en) | 2018-05-04 | 2018-05-04 | A dynamic energy-saving scheduling method for modular parallel jobs in cloud environment |
| Country | Link |
|---|---|
| CN (1) | CN108829500B (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101674194A (en)* | 2009-09-28 | 2010-03-17 | 北京航空航天大学 | Cluster load model based on log feature analysis and modeling method thereof |
| US20110161637A1 (en)* | 2009-12-28 | 2011-06-30 | Samsung Electronics Co., Ltd. | Apparatus and method for parallel processing |
| CN102521047A (en)* | 2011-11-15 | 2012-06-27 | 重庆邮电大学 | Method for realizing interrupted load balance among multi-core processors |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101674194A (en)* | 2009-09-28 | 2010-03-17 | 北京航空航天大学 | Cluster load model based on log feature analysis and modeling method thereof |
| US20110161637A1 (en)* | 2009-12-28 | 2011-06-30 | Samsung Electronics Co., Ltd. | Apparatus and method for parallel processing |
| CN102521047A (en)* | 2011-11-15 | 2012-06-27 | 重庆邮电大学 | Method for realizing interrupted load balance among multi-core processors |
| Title |
|---|
| 方兴: "实时多核系统面向负载均衡的任务分区调度算法", 《舰船电子工程》* |
| Publication number | Publication date |
|---|---|
| CN108829500B (en) | 2022-05-27 |
| Publication | Publication Date | Title |
|---|---|---|
| CN103235742B (en) | Dependency-based parallel task grouping scheduling method on multi-core cluster server | |
| Tang et al. | CPU–GPU utilization aware energy-efficient scheduling algorithm on heterogeneous computing systems | |
| Yao et al. | Evaluating and analyzing the energy efficiency of CNN inference on high‐performance GPU | |
| Li et al. | Energy-aware scheduling for frame-based tasks on heterogeneous multiprocessor platforms | |
| CN107861796B (en) | A Virtual Machine Scheduling Method Supporting Energy Consumption Optimization of Cloud Data Centers | |
| CN115168027A (en) | A computing resource measurement method based on deep reinforcement learning | |
| CN113886080B (en) | High-performance cluster task scheduling method, device, electronic device and storage medium | |
| CN107168770A (en) | A kind of cloud data center workflow schedule of low energy consumption and resource provision method | |
| CN106371924B (en) | A Task Scheduling Method for Minimizing Energy Consumption of MapReduce Cluster | |
| Song et al. | An efficient scheduling algorithm for energy consumption constrained parallel applications on heterogeneous distributed systems | |
| KR101770736B1 (en) | Method for reducing power consumption of system software using query scheduling of application and apparatus for reducing power consumption using said method | |
| Panda et al. | An efficient task consolidation algorithm for cloud computing systems | |
| WO2022141735A1 (en) | Processing apparatus, processing method, and related device | |
| Lu et al. | Mildip: An energy efficient code offloading framework in mobile cloudlets | |
| CN111240818B (en) | A method for task scheduling and energy saving in a heterogeneous system environment with multiple identical GPUs | |
| CN108429784B (en) | An energy efficiency priority cloud resource allocation and scheduling method | |
| Chen et al. | Joss: Joint exploration of cpu-memory dvfs and task scheduling for energy efficiency | |
| CN109582119B (en) | Double-layer Spark energy-saving scheduling method based on dynamic voltage and frequency adjustment | |
| HajiKhodaverdian et al. | Reinforcement learning-based task scheduling using dvfs techniques in mobile devices | |
| Li et al. | Energy efficient scheduling with probability and task migration considerations for soft real-time systems | |
| CN108829500B (en) | A dynamic energy-saving scheduling method for modular parallel jobs in cloud environment | |
| CN117215732A (en) | Task scheduling method, device, system and related equipment | |
| Yu et al. | Segment based power-efficient scheduling for real-time DAG tasks on edge devices | |
| CN100483354C (en) | Method for allocating task and elongating cell usage time to multi-state monoprocessor | |
| CN111221640A (en) | A GPU-CPU collaborative energy-saving method |
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| CB02 | Change of applicant information | Address after:210044 No. 219 Ningliu Road, Jiangbei New District, Nanjing City, Jiangsu Province Applicant after:Nanjing University of Information Science and Technology Address before:211500 Yuting Square, 59 Wangqiao Road, Liuhe District, Nanjing City, Jiangsu Province Applicant before:Nanjing University of Information Science and Technology | |
| CB02 | Change of applicant information | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |