發(fā)布時(shí)間：2020-10-16 03:55

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

【參考文獻(xiàn)】

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

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

本文編號(hào)：2842718