【摘要】：大規(guī)模計(jì)算系統(tǒng)采用高性能網(wǎng)絡(luò)互聯(lián)和并行處理方式顯著提高了系統(tǒng)性能,不僅在石油勘探、國(guó)防航天、氣象預(yù)報(bào)、軍事模擬、工業(yè)設(shè)計(jì)等領(lǐng)域廣泛應(yīng)用,而且在金融證券、電信行業(yè)、政府信息化、教育、網(wǎng)絡(luò)游戲等新興領(lǐng)域的需求也迅猛增長(zhǎng),是人類探索未知世界的最有力武器。 隨著系統(tǒng)規(guī)模的不斷擴(kuò)大,高端計(jì)算從單一追求高性能向高效能發(fā)展。鑒于高端計(jì)算系統(tǒng)高昂的運(yùn)行成本、低可靠性和對(duì)環(huán)境的影響,能耗管理不僅是電池驅(qū)動(dòng)設(shè)備的研究熱點(diǎn),也成為數(shù)據(jù)和計(jì)算中心運(yùn)行的關(guān)鍵問(wèn)題。隨著技術(shù)創(chuàng)新,服務(wù)器的初始購(gòu)置成本趨于下降,資本支出、營(yíng)業(yè)費(fèi)用和環(huán)境影響等的能耗相關(guān)成本卻在持續(xù)上升。因此,提高功耗效率、實(shí)現(xiàn)綠色計(jì)算,是計(jì)算機(jī)和IT行業(yè)的技術(shù)發(fā)展潮流。 能耗指標(biāo)作為一種系統(tǒng)需求,一方面受應(yīng)用執(zhí)行效率的影響,反過(guò)來(lái)其也會(huì)以資源或者服務(wù)使用成本的形式來(lái)影響用戶。資源或服務(wù)使用成本的反映形式之一為價(jià)格。目前定價(jià)機(jī)制普遍缺少精確的數(shù)學(xué)模型,且很少與能耗指標(biāo)相關(guān)聯(lián)。這導(dǎo)致既不能保證系統(tǒng)能耗的有效降低,也不能優(yōu)化用戶的資源或服務(wù)使用成本,損害了市場(chǎng)雙方的利益。因此,基于定價(jià)的成本優(yōu)化管理是十分必要的。另外,從全局來(lái)看,整個(gè)系統(tǒng)資源的負(fù)載不均衡也會(huì)導(dǎo)致系統(tǒng)的運(yùn)行成本增加、效能降低；同時(shí),由于缺少協(xié)同,用戶對(duì)優(yōu)質(zhì)資源的使用沖突,也使得用戶資源或服務(wù)使用成本不降反增。因此,基于協(xié)作的負(fù)載均衡研究也是降低雙方成本耗費(fèi)的必要手段之一 系統(tǒng)效能的高低不僅依賴于系統(tǒng)硬件,很大程度上也由部署在體系架構(gòu)上的資源管理系統(tǒng)決定。資源管理主要負(fù)責(zé)響應(yīng)用戶的資源請(qǐng)求、有效調(diào)度任務(wù)和合理分配資源,以保證用戶的性能需求以及資源的使用效率。任務(wù)調(diào)度是資源管理的核心,為了優(yōu)化某個(gè)目標(biāo)函數(shù),其在一組具有任意特性的處理機(jī)中對(duì)任務(wù)集合進(jìn)行排序和資源分配。多任務(wù)的調(diào)度問(wèn)題鑒于其NP復(fù)雜性、環(huán)境的多樣性、應(yīng)用的新需求和調(diào)度目標(biāo)的折中性等,一直沒(méi)有得到很好的解決,尤其在IT能耗成為影響全球能源和環(huán)境重要因素的背景下。 本課題在國(guó)家863計(jì)劃和自然科學(xué)基金項(xiàng)目的支持下,針對(duì)大規(guī)模計(jì)算系統(tǒng)高效能需求的能耗和成本管理問(wèn)題,以資源管理和任務(wù)調(diào)度為手段,通過(guò)分析功耗感知的資源管理方法、任務(wù)調(diào)度模型和當(dāng)前調(diào)度算法的局限性,抽象出幾個(gè)頗具挑戰(zhàn)性的調(diào)度問(wèn)題。這些調(diào)度問(wèn)題的解決可有效彌補(bǔ)當(dāng)前調(diào)度研究的局限和空白,有效兼顧不同運(yùn)行環(huán)境的差異性、不同調(diào)度技術(shù)的單一性、不同應(yīng)用的計(jì)算密集或者數(shù)據(jù)密集特性,以及不同QoS約束與性能指標(biāo)的沖突性等問(wèn)題。隨著IT能耗持續(xù)上升、云計(jì)算商業(yè)模式日益普及和系統(tǒng)規(guī)模的不斷擴(kuò)大,圍繞節(jié)能減排、市場(chǎng)模型和調(diào)度協(xié)同等問(wèn)題的資源管理和調(diào)度策略研究具有重大的理論和應(yīng)用價(jià)值。 針對(duì)基于能耗和成本的資源管理與調(diào)度,開(kāi)展了如下研究和創(chuàng)新工作： 首先是基于獨(dú)立任務(wù)的能耗感知調(diào)度。隨著新技術(shù)迅速發(fā)展和系統(tǒng)更新?lián)Q代,異構(gòu)計(jì)算系統(tǒng)較同構(gòu)計(jì)算系統(tǒng)更為普遍通用,但其在最大程度發(fā)揮并行處理優(yōu)勢(shì)的同時(shí)也增加了應(yīng)用執(zhí)行的復(fù)雜性和多樣性。在分析已有調(diào)度算法和常用功耗感知資源管理技術(shù)優(yōu)缺點(diǎn)的基礎(chǔ)上,本文提出了獨(dú)立任務(wù)在異構(gòu)系統(tǒng)中基于動(dòng)態(tài)電源管理技術(shù)的能耗感知時(shí)限調(diào)度算法。該算法面向高性能計(jì)算領(lǐng)域的長(zhǎng)時(shí)間運(yùn)行獨(dú)立任務(wù),不同于實(shí)時(shí)系統(tǒng)的周期性任務(wù),也區(qū)別于類似http請(qǐng)求的短時(shí)間處理任務(wù)。通過(guò)分析異構(gòu)多計(jì)算機(jī)系統(tǒng)的調(diào)度模型和兼顧應(yīng)用的時(shí)限約束條件,首先證明該問(wèn)題的NP復(fù)雜性,將其形式化并轉(zhuǎn)換為整數(shù)線性規(guī)劃模型,并設(shè)計(jì)了一個(gè)基于動(dòng)態(tài)電源管理的高效時(shí)限調(diào)度算法,不僅從理論上給出其最差下界的求證過(guò)程,還用實(shí)驗(yàn)驗(yàn)證了其性能,有效彌補(bǔ)了只使用動(dòng)態(tài)電壓頻率調(diào)整技術(shù)解決該類問(wèn)題的片面性。實(shí)驗(yàn)表明,提出的算法具有與最優(yōu)算法類似的能耗效率；與最早交期算法(EDD)相比,當(dāng)時(shí)限值松弛時(shí),平均節(jié)省能耗2%-20%,當(dāng)時(shí)限值緊縮時(shí),平均節(jié)省能耗5%-44%。為促進(jìn)算法的市場(chǎng)化應(yīng)用,基于提出的單位成本度量,本文還設(shè)計(jì)了將成本與能耗相關(guān)聯(lián)的定價(jià)機(jī)制,并為用戶提供了調(diào)節(jié)使用成本的手段,極大提高了用戶節(jié)能的積極性。 其次,是基于依賴任務(wù)的能耗感知調(diào)度。對(duì)高度數(shù)據(jù)密集型工作負(fù)載的支持正成為下一代計(jì)算和數(shù)據(jù)中心的關(guān)鍵技術(shù),因此,提出適合該類應(yīng)用特征的特定調(diào)度框架和算法是亟待解決的問(wèn)題。為解決已有依賴任務(wù)能耗感知調(diào)度在調(diào)度技術(shù)、通信能耗優(yōu)化、系統(tǒng)異構(gòu)性和靜態(tài)能耗等方面的局限性,本文提出了數(shù)據(jù)密集應(yīng)用在不同環(huán)境下的能耗感知調(diào)度算法。首先研究同構(gòu)計(jì)算系統(tǒng),建立相應(yīng)的系統(tǒng)模型、應(yīng)用模型和能耗模型,提出面向數(shù)據(jù)密集應(yīng)用的能耗感知調(diào)度框架。然后以框架為基準(zhǔn),進(jìn)一步平衡應(yīng)用的優(yōu)先約束性、系統(tǒng)的異構(gòu)性和不同性能指標(biāo)沖突性的關(guān)系,提出數(shù)據(jù)密集應(yīng)用在兼顧計(jì)算資源和通信資源異構(gòu)的環(huán)境中的能耗感知調(diào)度方案。對(duì)同構(gòu)計(jì)算系統(tǒng),根據(jù)是否支持動(dòng)態(tài)電壓頻率調(diào)整技術(shù),建立不同的系統(tǒng)模型,對(duì)其調(diào)度分別予以討論。數(shù)據(jù)密集應(yīng)用具有海量數(shù)據(jù)傳輸,其復(fù)雜的優(yōu)先約束關(guān)系、通信時(shí)間、通信能耗均不可忽略,因此引入考慮降低通信成本的方法,如任務(wù)復(fù)制、任務(wù)聚類、動(dòng)態(tài)映射參數(shù)等,來(lái)適應(yīng)該領(lǐng)域的特定需求。隨著芯片微型化和多核技術(shù)的發(fā)展,泄漏電流引起的靜態(tài)功耗由于單位工藝尺寸內(nèi)電子組件數(shù)的增加而呈指數(shù)增長(zhǎng),因此引入粗粒度或細(xì)粒度的動(dòng)態(tài)電源管理技術(shù)來(lái)降低不可忽略的靜態(tài)能耗。另外,算法的調(diào)度性能和能耗指標(biāo)是相互沖突的,本文各種技術(shù)的引入和實(shí)施均對(duì)執(zhí)行時(shí)間和能耗指標(biāo)進(jìn)行了有效的限定折中。實(shí)驗(yàn)表明,各種調(diào)度框架和方案的提出,既適應(yīng)了環(huán)境和應(yīng)用的特征,又可高效地保證調(diào)度目標(biāo)的實(shí)現(xiàn)。 再次,研究基于定價(jià)的成本優(yōu)化調(diào)度。系統(tǒng)的能耗指標(biāo)以資源或服務(wù)使用成本的形式反映給用戶。為保證系統(tǒng)和用戶雙方的利益,本文以市場(chǎng)驅(qū)動(dòng)的執(zhí)行引擎調(diào)度框架為基礎(chǔ),提出基于邊際定價(jià)和成本梯度的成本優(yōu)化調(diào)度算法。該算法從用戶角度出發(fā),提出對(duì)資源分配、提供者利潤(rùn)和成本調(diào)度均有重要影響的定價(jià)機(jī)制。該定價(jià)機(jī)制利用經(jīng)濟(jì)學(xué)的邊際原理,建立了精確的數(shù)學(xué)模型,其兼顧多個(gè)資源的有限使用特性,取得了較高的資源節(jié)點(diǎn)收益和資源利用率。成本優(yōu)化調(diào)度則以動(dòng)態(tài)的方式實(shí)施全圖調(diào)度,克服了任務(wù)圖劃分策略的弊端,具有較好的成本優(yōu)化能力。成本梯度因子通過(guò)查找以最大時(shí)間降低獲得最小成本增加的服務(wù),在算法實(shí)施陷入困境時(shí)幫助快速地找到近似最優(yōu)服務(wù)。在算法執(zhí)行過(guò)程中,還使用了有效的剪枝策略,降低了調(diào)度的計(jì)劃時(shí)間。另外,在分析成本優(yōu)化映射問(wèn)題的過(guò)程中,提出了一種新穎的矩陣樹(shù)形擴(kuò)展分析方法,使問(wèn)題的分析既直觀又高效。 最后,提出基于協(xié)作機(jī)制的雙層負(fù)載均衡調(diào)度策略。該策略兼顧執(zhí)行引擎和底層資源兩個(gè)層面的負(fù)載均衡,為提高系統(tǒng)性能和降低成本提供了有力保障。用戶提交的應(yīng)用首先提交給執(zhí)行引擎解析,解析后的任務(wù)傳給底層調(diào)度器,最后由具體系統(tǒng)資源完成任務(wù)的執(zhí)行。因此,執(zhí)行引擎相對(duì)大規(guī)模計(jì)算平臺(tái),屬于所提交應(yīng)用的上層服務(wù)。本文策略旨在解決系統(tǒng)具有多個(gè)調(diào)度入口、多執(zhí)行引擎之間缺乏協(xié)作和底層資源調(diào)度沖突的問(wèn)題。首先詳細(xì)分析了調(diào)度引擎的功能框架和負(fù)載消耗,并在此基礎(chǔ)上給出引擎和資源節(jié)點(diǎn)的實(shí)時(shí)負(fù)載模型和即將執(zhí)行應(yīng)用的預(yù)測(cè)負(fù)載模型。提出協(xié)作式體系結(jié)構(gòu),調(diào)度器和資源的狀態(tài)信息通過(guò)監(jiān)控、計(jì)劃和分析線程實(shí)時(shí)收集和評(píng)估,為效用函數(shù)的計(jì)算提供準(zhǔn)確依據(jù)。提出的基于性能模型的高層和底層調(diào)度算法,既兼顧了調(diào)度引擎和底層資源的負(fù)載均衡,又考慮了應(yīng)用的執(zhí)行時(shí)間和傳輸時(shí)間等服務(wù)質(zhì)量的需求。 在上述研究工作的基礎(chǔ)上,下一步還需要在靜態(tài)功耗優(yōu)化、資源綜合管理和實(shí)驗(yàn)評(píng)測(cè)等方面進(jìn)一步開(kāi)展工作。
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2012
【分類號(hào)】：TP302.7

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 李潔;;ICT與節(jié)能減排及標(biāo)準(zhǔn)研究進(jìn)展[J];電信網(wǎng)技術(shù);2009年09期

2 韓建軍;甘露;阮幼林;李慶華;Abbas A.Essa;;多處理器環(huán)境中基于節(jié)能及容錯(cuò)的實(shí)時(shí)動(dòng)態(tài)調(diào)度算法[J];計(jì)算機(jī)研究與發(fā)展;2008年04期

3 解玉鳳;魏少軍;;實(shí)時(shí)周期任務(wù)的非占先式能耗感知調(diào)度[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2006年02期

4 賀小川;賈焰;;搶占閾值調(diào)度的功耗優(yōu)化[J];計(jì)算機(jī)學(xué)報(bào);2008年11期

5 郭兵;沈艷;邵子立;;綠色計(jì)算的重定義與若干探討[J];計(jì)算機(jī)學(xué)報(bào);2009年12期

6 鄭湃;崔立真;王海洋;徐猛;;云計(jì)算環(huán)境下面向數(shù)據(jù)密集型應(yīng)用的數(shù)據(jù)布局策略與方法[J];計(jì)算機(jī)學(xué)報(bào);2010年08期

7 林闖;田源;姚敏;;綠色網(wǎng)絡(luò)和綠色評(píng)價(jià):節(jié)能機(jī)制、模型和評(píng)價(jià)[J];計(jì)算機(jī)學(xué)報(bào);2011年04期

8 趙榮彩,唐志敏,張兆慶,Guang R.Gao;軟件流水的低功耗編譯技術(shù)研究[J];軟件學(xué)報(bào);2003年08期

9 王桂彬;楊學(xué)軍;徐新海;林一松;李鑫;;異構(gòu)系統(tǒng)功耗感知的并行循環(huán)調(diào)度方法[J];軟件學(xué)報(bào);2011年09期

10 吳健;鄧?yán)?胡正國(guó);;網(wǎng)格計(jì)算經(jīng)濟(jì)模型中的價(jià)格協(xié)商和管制[J];西北工業(yè)大學(xué)學(xué)報(bào);2008年04期

本文編號(hào)：2751475