异构计算系统中能量感知利润最大化在线算法  

An Online Algorithm for Energy-aware Profit MaximizingProblem in Heterogeneous Computing System

作　　者：张庆辉 李伟东 张学杰[1] ZHANG Qinghui;LI Weidong;ZHANG Xuejie(School of Information Science and Engineering,Yunnan University,Kunming 650500,China;School of Mathematics and Statistics,Yunnan University,Kunming 650500,China)

机构地区：[1]云南大学信息学院,云南昆明650500 [2]云南大学数学与统计学院,云南昆明650500

出　　处：《郑州大学学报（理学版）》2024年第1期47-52,共6页Journal of Zhengzhou University:Natural Science Edition

基　　金：国家自然科学基金项目(12071417,61762091,62062065);云南大学第十三届研究生科研创新项目(2021Z079)。

摘　　要：异构计算系统中的任务调度仅以能耗优化为目标,往往会忽略最大完工时间带来的负面影响。此外,庞大的机器与任务数量为调度决策带来了极大的时间成本。以异构计算系统管理者单位时间收益最大化为目标,建立了考虑任务包的能量感知利润最大化问题模型,并为之设计了一种高效的在线算法。每到达一个用户,该在线算法能够通过系统当前状态构造多个线性方程组,并求得利润最大的解,即当前用户提交任务的分配策略。同时计算了该算法的运行时间复杂度为O(nm 4)。通过与另外两种常用算法进行对比,提出的在线算法能够在多项式时间内,得到目标值拟最优的调度方案。Task scheduling in heterogeneous computing systems only targeted at energy consumption optimization,which could ignore the negative impact of maximum completion time.In addition,the large number of machines and tasks could incur a significant time cost for scheduling decisions.A energy-aware profit maximizing problem considering bag-of-tasks with the goal of maximizing the profit per unit time for managers of heterogeneous computing systems was built,and an efficient online algorithm was designed.For each user,the online algorithm could construct multiple sets of system of linear equations based on the system′s current state,and solve the most profitable solution which was the allocation strategy for the tasks submitted by the current user.The running time of the algorithm was O(nm 4).The proposed algorithm was compared with the other two common algorithms.The proposed online algorithm could obtain a quasi-optimal scheduling scheme in polynomial time.

关 键 词：异构计算系统 作业调度 能量感知 负载均衡 任务包 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]