基于能耗和成本的資源管理與調(diào)度策略研究.pdf

1、大規(guī)模計(jì)算系統(tǒng)采用高性能網(wǎng)絡(luò)互聯(lián)和并行處理方式顯著提高了系統(tǒng)性能，不僅在石油勘探、國防航天、氣象預(yù)報、軍事模擬、工業(yè)設(shè)計(jì)等領(lǐng)域廣泛應(yīng)用，而且在金融證券、電信行業(yè)、政府信息化、教育、網(wǎng)絡(luò)游戲等新興領(lǐng)域的需求也迅猛增長，是人類探索未知世界的最有力武器。
　　 隨著系統(tǒng)規(guī)模的不斷擴(kuò)大，高端計(jì)算從單一追求高性能向高效能發(fā)展。鑒于高端計(jì)算系統(tǒng)高昂的運(yùn)行成本、低可靠性和對環(huán)境的影響，能耗管理不僅是電池驅(qū)動設(shè)備的研究熱點(diǎn)，也成為數(shù)據(jù)和計(jì)算中心

2、運(yùn)行的關(guān)鍵問題。隨著技術(shù)創(chuàng)新，服務(wù)器的初始購置成本趨于下降，資本支出、營業(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í)行效率的影響，反過來其也會以資源或者服務(wù)使用成本的形式來影響用戶。資源或服務(wù)使用成本的反映形式之一為價格。目前定價機(jī)制普遍缺少精確的數(shù)學(xué)模型，且很少與能耗指標(biāo)相關(guān)聯(lián)。這導(dǎo)致既不能保證系統(tǒng)能耗的有效降

3、低，也不能優(yōu)化用戶的資源或服務(wù)使用成本，損害了市場雙方的利益。因此，基于定價的成本優(yōu)化管理是十分必要的。另外，從全局來看，整個系統(tǒng)資源的負(fù)載不均衡也會導(dǎo)致系統(tǒng)的運(yùn)行成本增加、效能降低;同時，由于缺少協(xié)同，用戶對優(yōu)質(zhì)資源的使用沖突，也使得用戶資源或服務(wù)使用成本不降反增。因此，基于協(xié)作的負(fù)載均衡研究也是降低雙方成本耗費(fèi)的必要手段之一。
　　 系統(tǒng)效能的高低不僅依賴于系統(tǒng)硬件，很大程度上也由部署在體系架構(gòu)上的資源管理系統(tǒng)決定。資源管理

4、主要負(fù)責(zé)響應(yīng)用戶的資源請求、有效調(diào)度任務(wù)和合理分配資源，以保證用戶的性能需求以及資源的使用效率。任務(wù)調(diào)度是資源管理的核心，為了優(yōu)化某個目標(biāo)函數(shù)，其在一組具有任意特性的處理機(jī)中對任務(wù)集合進(jìn)行排序和資源分配。多任務(wù)的調(diào)度問題鑒于其NP復(fù)雜性、環(huán)境的多樣性、應(yīng)用的新需求和調(diào)度目標(biāo)的折中性等，一直沒有得到很好的解決，尤其在IT能耗成為影響全球能源和環(huán)境重要因素的背景下。
　　 本課題在國家863計(jì)劃和自然科學(xué)基金項(xiàng)目的支持下，針對大規(guī)模

5、計(jì)算系統(tǒng)高效能需求的能耗和成本管理問題，以資源管理和任務(wù)調(diào)度為手段，通過分析功耗感知的資源管理方法、任務(wù)調(diào)度模型和當(dāng)前調(diào)度算法的局限性，抽象出幾個頗具挑戰(zhàn)性的調(diào)度問題。這些調(diào)度問題的解決可有效彌補(bǔ)當(dāng)前調(diào)度研究的局限和空白，有效兼顧不同運(yùn)行環(huán)境的差異性、不同調(diào)度技術(shù)的單一性、不同應(yīng)用的計(jì)算密集或者數(shù)據(jù)密集特性，以及不同QoS約束與性能指標(biāo)的沖突性等問題。隨著IT能耗持續(xù)上升、云計(jì)算商業(yè)模式日益普及和系統(tǒng)規(guī)模的不斷擴(kuò)大，圍繞節(jié)能減排、市場模

6、型和調(diào)度協(xié)同等問題的資源管理和調(diào)度策略研究具有重大的理論和應(yīng)用價值。
　　 針對基于能耗和成本的資源管理與調(diào)度，開展了如下研究和創(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)勢的同時也增加了應(yīng)用執(zhí)行的復(fù)雜性和多樣性。在分析已有調(diào)度算法和常用功耗感知資源管理技術(shù)優(yōu)缺點(diǎn)的基礎(chǔ)上，本文提出了獨(dú)立任務(wù)在異構(gòu)系統(tǒng)中基于動態(tài)電

7、源管理技術(shù)的能耗感知時限調(diào)度算法。該算法面向高性能計(jì)算領(lǐng)域的長時間運(yùn)行獨(dú)立任務(wù)，不同于實(shí)時系統(tǒng)的周期性任務(wù)，也區(qū)別于類似http請求的短時間處理任務(wù)。通過分析異構(gòu)多計(jì)算機(jī)系統(tǒng)的調(diào)度模型和兼顧應(yīng)用的時限約束條件，首先證明該問題的NP復(fù)雜性，將其形式化并轉(zhuǎn)換為整數(shù)線性規(guī)劃模型，并設(shè)計(jì)了一個基于動態(tài)電源管理的高效時限調(diào)度算法，不僅從理論上給出其最差下界的求證過程，還用實(shí)驗(yàn)驗(yàn)證了其性能，有效彌補(bǔ)了只使用動態(tài)電壓頻率調(diào)整技術(shù)解決該類問題的片面性。

8、實(shí)驗(yàn)表明，提出的算法具有與最優(yōu)算法類似的能耗效率;與最早交期算法(EDD)相比，當(dāng)時限值松弛時，平均節(jié)省能耗2％-20％，當(dāng)時限值緊縮時，平均節(jié)省能耗5％-44％。為促進(jìn)算法的市場化應(yīng)用，基于提出的單位成本度量，本文還設(shè)計(jì)了將成本與能耗相關(guān)聯(lián)的定價機(jī)制，并為用戶提供了調(diào)節(jié)使用成本的手段，極大提高了用戶節(jié)能的積極性。
　　 其次，是基于依賴任務(wù)的能耗感知調(diào)度。對高度數(shù)據(jù)密集型工作負(fù)載的支持正成為下一代計(jì)算和數(shù)據(jù)中心的關(guān)鍵技術(shù)，因此

9、，提出適合該類應(yīng)用特征的特定調(diào)度框架和算法是亟待解決的問題。為解決已有依賴任務(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)的

10、環(huán)境中的能耗感知調(diào)度方案。對同構(gòu)計(jì)算系統(tǒng)，根據(jù)是否支持動態(tài)電壓頻率調(diào)整技術(shù)，建立不同的系統(tǒng)模型，對其調(diào)度分別予以討論。數(shù)據(jù)密集應(yīng)用具有海量數(shù)據(jù)傳輸，其復(fù)雜的優(yōu)先約束關(guān)系、通信時間、通信能耗均不可忽略，因此引入考慮降低通信成本的方法，如任務(wù)復(fù)制、任務(wù)聚類、動態(tài)映射參數(shù)等，來適應(yīng)該領(lǐng)域的特定需求。隨著芯片微型化和多核技術(shù)的發(fā)展，泄漏電流引起的靜態(tài)功耗由于單位工藝尺寸內(nèi)電子組件數(shù)的增加而呈指數(shù)增長，因此引入粗粒度或細(xì)粒度的動態(tài)電源管理技術(shù)來降

11、低不可忽略的靜態(tài)能耗。另外，算法的調(diào)度性能和能耗指標(biāo)是相互沖突的，本文各種技術(shù)的引入和實(shí)施均對執(zhí)行時間和能耗指標(biāo)進(jìn)行了有效的限定折中。實(shí)驗(yàn)表明，各種調(diào)度框架和方案的提出，既適應(yīng)了環(huán)境和應(yīng)用的特征，又可高效地保證調(diào)度目標(biāo)的實(shí)現(xiàn)。
　　 再次，研究基于定價的成本優(yōu)化調(diào)度。系統(tǒng)的能耗指標(biāo)以資源或服務(wù)使用成本的形式反映給用戶。為保證系統(tǒng)和用戶雙方的利益，本文以市場驅(qū)動的執(zhí)行引擎調(diào)度框架為基礎(chǔ)，提出基于邊際定價和成本梯度的成本優(yōu)化調(diào)度算法

12、。該算法從用戶角度出發(fā)，提出對資源分配、提供者利潤和成本調(diào)度均有重要影響的定價機(jī)制。該定價機(jī)制利用經(jīng)濟(jì)學(xué)的邊際原理，建立了精確的數(shù)學(xué)模型，其兼顧多個資源的有限使用特性，取得了較高的資源節(jié)點(diǎn)收益和資源利用率。成本優(yōu)化調(diào)度則以動態(tài)的方式實(shí)施全圖調(diào)度，克服了任務(wù)圖劃分策略的弊端，具有較好的成本優(yōu)化能力。成本梯度因子通過查找以最大時間降低獲得最小成本增加的服務(wù)，在算法實(shí)施陷入困境時幫助快速地找到近似最優(yōu)服務(wù)。在算法執(zhí)行過程中，還使用了有效的剪枝

13、策略，降低了調(diào)度的計(jì)劃時間。另外，在分析成本優(yōu)化映射問題的過程中，提出了一種新穎的矩陣樹形擴(kuò)展分析方法，使問題的分析既直觀又高效。
　　 最后，提出基于協(xié)作機(jī)制的雙層負(fù)載均衡調(diào)度策略。該策略兼顧執(zhí)行引擎和底層資源兩個層面的負(fù)載均衡，為提高系統(tǒng)性能和降低成本提供了有力保障。用戶提交的應(yīng)用首先提交給執(zhí)行引擎解析，解析后的任務(wù)傳給底層調(diào)度器，最后由具體系統(tǒng)資源完成任務(wù)的執(zhí)行。因此，執(zhí)行引擎相對大規(guī)模計(jì)算平臺，屬于所提交應(yīng)用的上層服務(wù)。

14、本文策略旨在解決系統(tǒng)具有多個調(diào)度入口、多執(zhí)行引擎之間缺乏協(xié)作和底層資源調(diào)度沖突的問題。首先詳細(xì)分析了調(diào)度引擎的功能框架和負(fù)載消耗，并在此基礎(chǔ)上給出引擎和資源節(jié)點(diǎn)的實(shí)時負(fù)載模型和即將執(zhí)行應(yīng)用的預(yù)測負(fù)載模型。提出協(xié)作式體系結(jié)構(gòu)，調(diào)度器和資源的狀態(tài)信息通過監(jiān)控、計(jì)劃和分析線程實(shí)時收集和評估，為效用函數(shù)的計(jì)算提供準(zhǔn)確依據(jù)。提出的基于性能模型的高層和底層調(diào)度算法，既兼顧了調(diào)度引擎和底層資源的負(fù)載均衡，又考慮了應(yīng)用的執(zhí)行時間和傳輸時間等服務(wù)質(zhì)量的需