基于能耗和成本的资源管理与调度策略研究

发布时间：2020-07-12 05:08

【摘要】：大规模计算系统采用高性能网络互联和并行处理方式显著提高了系统性能,不仅在石油勘探、国防航天、气象预报、军事模拟、工业设计等领域广泛应用,而且在金融证券、电信行业、政府信息化、教育、网络游戏等新兴领域的需求也迅猛增长,是人类探索未知世界的最有力武器。随着系统规模的不断扩大,高端计算从单一追求高性能向高效能发展。鉴于高端计算系统高昂的运行成本、低可靠性和对环境的影响,能耗管理不仅是电池驱动设备的研究热点,也成为数据和计算中心运行的关键问题。随着技术创新,服务器的初始购置成本趋于下降,资本支出、营业费用和环境影响等的能耗相关成本却在持续上升。因此,提高功耗效率、实现绿色计算,是计算机和IT行业的技术发展潮流。能耗指标作为一种系统需求,一方面受应用执行效率的影响,反过来其也会以资源或者服务使用成本的形式来影响用户。资源或服务使用成本的反映形式之一为价格。目前定价机制普遍缺少精确的数学模型,且很少与能耗指标相关联。这导致既不能保证系统能耗的有效降低,也不能优化用户的资源或服务使用成本,损害了市场双方的利益。因此,基于定价的成本优化管理是十分必要的。另外,从全局来看,整个系统资源的负载不均衡也会导致系统的运行成本增加、效能降低；同时,由于缺少协同,用户对优质资源的使用冲突,也使得用户资源或服务使用成本不降反增。因此,基于协作的负载均衡研究也是降低双方成本耗费的必要手段之一系统效能的高低不仅依赖于系统硬件,很大程度上也由部署在体系架构上的资源管理系统决定。资源管理主要负责响应用户的资源请求、有效调度任务和合理分配资源,以保证用户的性能需求以及资源的使用效率。任务调度是资源管理的核心,为了优化某个目标函数,其在一组具有任意特性的处理机中对任务集合进行排序和资源分配。多任务的调度问题鉴于其NP复杂性、环境的多样性、应用的新需求和调度目标的折中性等,一直没有得到很好的解决,尤其在IT能耗成为影响全球能源和环境重要因素的背景下。本课题在国家863计划和自然科学基金项目的支持下,针对大规模计算系统高效能需求的能耗和成本管理问题,以资源管理和任务调度为手段,通过分析功耗感知的资源管理方法、任务调度模型和当前调度算法的局限性,抽象出几个颇具挑战性的调度问题。这些调度问题的解决可有效弥补当前调度研究的局限和空白,有效兼顾不同运行环境的差异性、不同调度技术的单一性、不同应用的计算密集或者数据密集特性,以及不同QoS约束与性能指标的冲突性等问题。随着IT能耗持续上升、云计算商业模式日益普及和系统规模的不断扩大,围绕节能减排、市场模型和调度协同等问题的资源管理和调度策略研究具有重大的理论和应用价值。针对基于能耗和成本的资源管理与调度,开展了如下研究和创新工作：首先是基于独立任务的能耗感知调度。随着新技术迅速发展和系统更新换代,异构计算系统较同构计算系统更为普遍通用,但其在最大程度发挥并行处理优势的同时也增加了应用执行的复杂性和多样性。在分析已有调度算法和常用功耗感知资源管理技术优缺点的基础上,本文提出了独立任务在异构系统中基于动态电源管理技术的能耗感知时限调度算法。该算法面向高性能计算领域的长时间运行独立任务,不同于实时系统的周期性任务,也区别于类似http请求的短时间处理任务。通过分析异构多计算机系统的调度模型和兼顾应用的时限约束条件,首先证明该问题的NP复杂性,将其形式化并转换为整数线性规划模型,并设计了一个基于动态电源管理的高效时限调度算法,不仅从理论上给出其最差下界的求证过程,还用实验验证了其性能,有效弥补了只使用动态电压频率调整技术解决该类问题的片面性。实验表明,提出的算法具有与最优算法类似的能耗效率；与最早交期算法(EDD)相比,当时限值松弛时,平均节省能耗2%-20%,当时限值紧缩时,平均节省能耗5%-44%。为促进算法的市场化应用,基于提出的单位成本度量,本文还设计了将成本与能耗相关联的定价机制,并为用户提供了调节使用成本的手段,极大提高了用户节能的积极性。其次,是基于依赖任务的能耗感知调度。对高度数据密集型工作负载的支持正成为下一代计算和数据中心的关键技术,因此,提出适合该类应用特征的特定调度框架和算法是亟待解决的问题。为解决已有依赖任务能耗感知调度在调度技术、通信能耗优化、系统异构性和静态能耗等方面的局限性,本文提出了数据密集应用在不同环境下的能耗感知调度算法。首先研究同构计算系统,建立相应的系统模型、应用模型和能耗模型,提出面向数据密集应用的能耗感知调度框架。然后以框架为基准,进一步平衡应用的优先约束性、系统的异构性和不同性能指标冲突性的关系,提出数据密集应用在兼顾计算资源和通信资源异构的环境中的能耗感知调度方案。对同构计算系统,根据是否支持动态电压频率调整技术,建立不同的系统模型,对其调度分别予以讨论。数据密集应用具有海量数据传输,其复杂的优先约束关系、通信时间、通信能耗均不可忽略,因此引入考虑降低通信成本的方法,如任务复制、任务聚类、动态映射参数等,来适应该领域的特定需求。随着芯片微型化和多核技术的发展,泄漏电流引起的静态功耗由于单位工艺尺寸内电子组件数的增加而呈指数增长,因此引入粗粒度或细粒度的动态电源管理技术来降低不可忽略的静态能耗。另外,算法的调度性能和能耗指标是相互冲突的,本文各种技术的引入和实施均对执行时间和能耗指标进行了有效的限定折中。实验表明,各种调度框架和方案的提出,既适应了环境和应用的特征,又可高效地保证调度目标的实现。再次,研究基于定价的成本优化调度。系统的能耗指标以资源或服务使用成本的形式反映给用户。为保证系统和用户双方的利益,本文以市场驱动的执行引擎调度框架为基础,提出基于边际定价和成本梯度的成本优化调度算法。该算法从用户角度出发,提出对资源分配、提供者利润和成本调度均有重要影响的定价机制。该定价机制利用经济学的边际原理,建立了精确的数学模型,其兼顾多个资源的有限使用特性,取得了较高的资源节点收益和资源利用率。成本优化调度则以动态的方式实施全图调度,克服了任务图划分策略的弊端,具有较好的成本优化能力。成本梯度因子通过查找以最大时间降低获得最小成本增加的服务,在算法实施陷入困境时帮助快速地找到近似最优服务。在算法执行过程中,还使用了有效的剪枝策略,降低了调度的计划时间。另外,在分析成本优化映射问题的过程中,提出了一种新颖的矩阵树形扩展分析方法,使问题的分析既直观又高效。最后,提出基于协作机制的双层负载均衡调度策略。该策略兼顾执行引擎和底层资源两个层面的负载均衡,为提高系统性能和降低成本提供了有力保障。用户提交的应用首先提交给执行引擎解析,解析后的任务传给底层调度器,最后由具体系统资源完成任务的执行。因此,执行引擎相对大规模计算平台,属于所提交应用的上层服务。本文策略旨在解决系统具有多个调度入口、多执行引擎之间缺乏协作和底层资源调度冲突的问题。首先详细分析了调度引擎的功能框架和负载消耗,并在此基础上给出引擎和资源节点的实时负载模型和即将执行应用的预测负载模型。提出协作式体系结构,调度器和资源的状态信息通过监控、计划和分析线程实时收集和评估,为效用函数的计算提供准确依据。提出的基于性能模型的高层和底层调度算法,既兼顾了调度引擎和底层资源的负载均衡,又考虑了应用的执行时间和传输时间等服务质量的需求。在上述研究工作的基础上,下一步还需要在静态功耗优化、资源综合管理和实验评测等方面进一步开展工作。
【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2012
【分类号】：TP302.7

【参考文献】