受芯片制造工藝、芯片材料的物理特性、能耗、散熱等問題的限制，單核處理器的頻率提升速度已無法跟上高性能計算對計算能力需求的增長速度。有鑒于此，基于多核處理器的并行架構(gòu)得到了廣泛的發(fā)展。如何充分地利用各種并行架構(gòu)中大量的計算資源已成為高性能計算領(lǐng)域的研究熱點之一。特別地，如何通過優(yōu)化任務(wù)調(diào)度在不修改并行程序的前提下提高并行程序的性能、節(jié)省執(zhí)行并行程序的能耗、均衡并發(fā)運行的程序的性能更是重中之重。 針對目前主流的各種并行架構(gòu)，本文完整并深入地研究了這些架構(gòu)中的高性能低能耗的優(yōu)化任務(wù)調(diào)度策略，設(shè)計并實現(xiàn)了面向復(fù)雜并行架構(gòu)的運行時高性能低功耗任務(wù)調(diào)度系統(tǒng)：HPEE系統(tǒng)。HPEE系統(tǒng)由緩存感知雙層任務(wù)竊取模塊（CAB）、位置感知任務(wù)竊取模塊（LAWS）、帶寬感知核分配模塊（BWC）、負(fù)載感知任務(wù)調(diào)度模塊（WATS）、高能效負(fù)載感知任務(wù)調(diào)度模塊（EEWA）等五個主要模塊組成。這些模塊涉及的并行架構(gòu)包括：多路多核架構(gòu)、使用NUMA內(nèi)存系統(tǒng)的多路多核架構(gòu)、非對稱多核架構(gòu)、以及支持動態(tài)電壓頻率調(diào)節(jié)技術(shù)的多核架構(gòu)。 在多路多核架構(gòu)中，同一處理器中的核之間共享緩存但是不同處理器中的核之間僅共享主存。因此，針對多路多核架構(gòu)，我們主要對共享緩存的使用進行優(yōu)化。如果該架構(gòu)僅執(zhí)行一個程序，HPEE系統(tǒng)使用緩存感知雙層任務(wù)竊取模塊，將該程序共享數(shù)據(jù)的任務(wù)調(diào)度到同一個處理器中�；诖朔椒�，各任務(wù)間的共享數(shù)據(jù)只需要被讀入共享緩存一次，同一處理器中的核可以直接從共享緩存中高速訪問該數(shù)據(jù)。實驗結(jié)果表明，和傳統(tǒng)任務(wù)竊取策略相比，緩存感知雙層任務(wù)竊取模塊可以減少并行程序74.4%的運行時間。 如果該多路多核架構(gòu)底層使用NUMA內(nèi)存架構(gòu)，HPEE系統(tǒng)使用位置感知任務(wù)竊取模塊，將一個程序的數(shù)據(jù)集平均分配到不同的內(nèi)存節(jié)點中，并將各任務(wù)分配到本地內(nèi)存節(jié)點存儲其數(shù)據(jù)的處理器中。使用該方法，各任務(wù)都能從本地內(nèi)存節(jié)點或者共享緩存中高速地訪問數(shù)據(jù)。實驗結(jié)果表明，和傳統(tǒng)任務(wù)竊取調(diào)度器相比，位置感知任務(wù)竊取模塊可以減少并行程序54.2%的運行時間。 然而，如果一個多路多核架構(gòu)上有多個并行程序并發(fā)運行，那么這些程序?qū)⒏偁幱嬎阗Y源（核）和存儲資源（緩存、緩存帶寬）。如何合理地將計算資源和存儲資源動態(tài)分配給并發(fā)運行的并行程序是使這些程序獲得良好且均衡性能所亟需解決的問題。針對該問題，基于各程序的實時需求，HPEE系統(tǒng)使用帶寬感知核分配模塊周期性地對計算資源和存儲資源進行重分配。在保證每個程序需求的前提下，如果一個處理器的共享緩存帶寬已被大量占用，那么帶寬感知核分配模塊將該處理器中的空閑核分配給計算密集型程序。反之亦然，通過這種方式，帶寬感知核分配模塊可以最小化共享緩存競爭并進而提高并發(fā)運行的程序的性能。實驗結(jié)果表明，和傳統(tǒng)的空分共享相比，帶寬感知核分配模塊能夠減少并發(fā)運行程序高達(dá)54.7%的運行時間。 在非對稱多核架構(gòu)中，不同的核運行于不同的頻率且每個核的頻率在執(zhí)行程序過程中不可變。在此種架構(gòu)中，如何保證不同頻率的核間的負(fù)載均衡是最優(yōu)化并行程序性能所面臨的關(guān)鍵問題。針對該問題，基于實時采集的程序中各任務(wù)的負(fù)載信息，HPEE系統(tǒng)使用負(fù)載感知任務(wù)調(diào)度模塊來進行優(yōu)化任務(wù)調(diào)度�；谌蝿�(wù)類型及同類任務(wù)的歷史負(fù)載，該模塊使用一種基于歷史的任務(wù)分配策略將待執(zhí)行的高負(fù)載的任務(wù)分配給高頻率的核。與此同時，由于歷史信息具有部分不精確性，所以該模塊進一步使用一種動態(tài)的基于偏好的任務(wù)竊取策略在運行時均衡負(fù)載。實驗結(jié)果表明，和采用傳統(tǒng)隨機任務(wù)竊取系統(tǒng)相比，負(fù)載感知任務(wù)調(diào)度模塊能夠減少并行程序82.7%的運行時間。 在支持動態(tài)電壓頻率調(diào)節(jié)技術(shù)的多核架構(gòu)中，HPEE系統(tǒng)使用高能效負(fù)載感知任務(wù)調(diào)度模塊來進行高能效優(yōu)化任務(wù)調(diào)度�；谌蝿�(wù)類型及同類任務(wù)的歷史負(fù)載，該模塊使用一種負(fù)載感知頻率調(diào)節(jié)器按照并行程序的負(fù)載自動搜索執(zhí)行該程序所應(yīng)該使用的最佳頻率配置。與此同時，由于歷史信息具有部分不精確性，所以該模塊進一步使用一個基于偏好的任務(wù)調(diào)度器來平衡各核間負(fù)載。實驗表明，高能效負(fù)載感知任務(wù)調(diào)度模塊能夠在僅輕微降低程序性能的條件下減少能耗高達(dá)29.8%（性能損失少于3.7%）。
【學(xué)位單位】：上海交通大學(xué)
【學(xué)位級別】：博士
【學(xué)位年份】：2014
【中圖分類】：TP332;TP38
【文章目錄】：
摘要
ABSTRACT
目錄
表格索引
插圖索引
第一章 引言
    1.1 并行架構(gòu)
        1.1.1 多路多核架構(gòu)
        1.1.2 非對稱多核架構(gòu)
    1.2 任務(wù)調(diào)度策略/并行編程環(huán)境
        1.2.1 手動任務(wù)調(diào)度策略/編程環(huán)境
        1.2.2 自動任務(wù)調(diào)度策略/編程環(huán)境
    1.3 現(xiàn)有任務(wù)竊取調(diào)度系統(tǒng)
        1.3.1 MIT Cilk
        1.3.2 TBB
        1.3.3 X10
    1.4 HPEE 任務(wù)調(diào)度系統(tǒng)概述
第二章 緩存感知雙層任務(wù)竊取模塊 (CAB)
    2.1 研究背景
    2.2 研究動機
        2.2.1 問題描述
        2.2.2 解決方案
    2.3 模塊設(shè)計
    2.4 任務(wù)圖切分器
        2.4.1 FTO 方案
        2.4.2 GTO 方案
    2.5 雙層任務(wù)竊取調(diào)度器
        2.5.1 任務(wù)竊取策略
        2.5.2 任務(wù)生成模式
    2.6 時間/空間復(fù)雜度分析
        2.6.1 傳統(tǒng)任務(wù)竊取策略的時間/空間復(fù)雜度
        2.6.2 CAB 模塊的時間復(fù)雜度
        2.6.3 CAB 模塊的空間復(fù)雜度
    2.7 具體實現(xiàn)
        2.7.1 編譯器支持
        2.7.2 運行時系統(tǒng)支持
    2.8 實驗驗證
        2.8.1 CAB-FTO 的性能
        2.8.2 CAB-GTO 的性能
        2.8.3 可用性討論
        2.8.4 評測結(jié)果總結(jié)
    2.9 相關(guān)工作
    2.10 本章小結(jié)
第三章 位置感知任務(wù)竊取模塊 (LAWS)
    3.1 研究背景
    3.2 研究動機
    3.3 模塊設(shè)計
        3.3.1 總體設(shè)計
        3.3.2 負(fù)載均衡任務(wù)分配器
        3.3.3 自動任務(wù)圖切分器
        3.3.4 三層任務(wù)竊取調(diào)度器
        3.3.5 理論驗證
    3.4 具體實現(xiàn)
    3.5 實驗驗證
        3.5.1 LAWS 模塊的性能
        3.5.2 自動任務(wù)圖切分器的有效性
        3.5.3 LAWS 模塊的可擴展性
        3.5.4 可用性討論
    3.6 相關(guān)工作
    3.7 本章小結(jié)
第四章 帶寬感知核分配模塊 (BWC)
    4.1 研究背景
    4.2 研究動機
        4.2.1 核分配策略簡介
        4.2.2 研究動機
    4.3 模塊設(shè)計
        4.3.1 策略設(shè)計
        4.3.2 工作線程管理器
        4.3.3 帶寬感知的核分配器
    4.4 具體實現(xiàn)
    4.5 實驗驗證
        4.5.1 實驗平臺搭建
        4.5.2 BWC 模塊的性能
        4.5.3 BWC 模塊的平衡性
        4.5.4 BWC 動態(tài)調(diào)整的有效性
        4.5.5 BWC 模塊的可擴展性
        4.5.6 運行周期長度的影響
        4.5.7 BWC 模塊的額外開銷
        4.5.8 可用性討論
    4.6 相關(guān)工作
    4.7 本章小結(jié)
第五章 負(fù)載感知任務(wù)調(diào)度模塊 (WATS)
    5.1 研究背景
    5.2 研究動機
        5.2.1 問題描述
        5.2.2 最優(yōu)解決方案
        5.2.3 近最優(yōu)解決方案
    5.3 模塊設(shè)計
        5.3.1 基于歷史的任務(wù)分配
        5.3.2 基于偏好的任務(wù)竊取
    5.4 具體實現(xiàn)
    5.5 實驗驗證
        5.5.1 WATS 模塊的性能
        5.5.2 基于歷史任務(wù)分配的可擴展性
        5.5.3 基于偏好任務(wù)竊取的有效性
        5.5.4 加入任務(wù)搶奪策略
        5.5.5 可用性討論
    5.6 相關(guān)工作
    5.7 本章小結(jié)
第六章 高能效負(fù)載感知任務(wù)調(diào)度模塊 (EEWA)
    6.1 研究背景
    6.2 研究動機
        6.2.1 問題描述
        6.2.2 解決方案
    6.3 模塊設(shè)計及實現(xiàn)
        6.3.1 負(fù)載感知頻率調(diào)節(jié)器
        6.3.2 基于偏好的任務(wù)調(diào)度器
    6.4 實驗驗證
        6.4.1 EEWA 模塊的能效
        6.4.2 探測階段變化的有效性
        6.4.3 EEWA 的額外開銷
        6.4.4 EEWA 的可擴展性
        6.4.5 可用性討論
    6.5 相關(guān)工作
    6.6 本章小結(jié)
第七章 全文總結(jié)
    7.1 研究總結(jié)
    7.2 研究展望
參考文獻
致謝
攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文目錄
攻讀學(xué)位期間參與的項目

【參考文獻】

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

1 陳全;鄧倩妮;;云計算及其關(guān)鍵技術(shù)[J];計算機應(yīng)用;2009年09期

本文編號：2842718