本文主要研究并行計算系統(tǒng)中的負載平衡算法與并行執(zhí)行時間預測問題。為能較快平衡系統(tǒng)中的負載,提出了“均分負載”平衡算法。該方法先對各處理器結點的已有負載按網(wǎng)絡中各處理器的速度進行劃分,然后把這些劃分好的小負載遷移到對應的處理器上,以平衡系統(tǒng)中各處理器的負載。分析表明:該算法時間性能較好,適于解決系統(tǒng)初始分配負載問題與系統(tǒng)負載極度失衡的平衡問題;但對于負載較平衡的系統(tǒng),其負載遷移量很大。為減小負載遷移量同時保持較快的平衡速度,提出了“二分網(wǎng)絡”平衡算法。該方法按網(wǎng)絡的結點數(shù)把網(wǎng)絡分為兩子網(wǎng)絡,然后按兩子網(wǎng)絡的處理速度之比進行兩子網(wǎng)絡間的負載遷移,遞歸上述過程,直到各子網(wǎng)絡中只有一個結點時,系統(tǒng)經(jīng)負載遷移后可達到平衡狀態(tài)。該算法具有平衡負載速度較快、負載遷移量較小的優(yōu)點,適于大多數(shù)條件下的負載平衡。針對環(huán)與線性陣列的負載平衡速度較慢與遷移量較大的問題,提出了“貪心線性推移”平衡算法。該算法的思想是:把重負載結點過重的那部分負載按線性或環(huán)的路徑推移到下一鄰居結點,循環(huán)推移直到整個系統(tǒng)負載平衡。此算法適用于任何具有哈密頓通路的圖結構網(wǎng)絡。一般情況下,其平衡過程的負載遷移量不大,且平衡負載速度較快... 

【文章頁數(shù)】：102 頁

【學位級別】：博士

【文章目錄】：
中文摘要
ABSTRACT
第一章 緒論
    1.1 選題背景和研究意義
    1.2 本領域研究現(xiàn)狀
    1.3 本文主要研究工作和創(chuàng)新點
    1.4 論文結構
第二章 并行性理論概述
    2.1 并行計算機的分類及其特點
    2.2 并行計算機系統(tǒng)互連
        2.2.1 靜態(tài)互連網(wǎng)絡
        2.2.2 動態(tài)互連網(wǎng)絡
    2.3 負載平衡與執(zhí)行時間預測技術
        2.3.1 動態(tài)負載平衡
        2.3.2 靜態(tài)負載平衡
        2.3.3 并行執(zhí)行時間預測
    2.4 本章小結
第三章 基于無限可分負載的平衡算法
    3.1 引言與相關工作
    3.2 定義和約定
    3.3 負載平衡算法
        3.3.1 “均分負載”平衡算法
        3.3.2 “二分網(wǎng)絡”平衡算法
        3.3.3 “P分網(wǎng)絡”平衡算法
        3.3.4 “貪心線性推移”平衡算法
    3.4 三種算法的性能比較小結
    3.5 本章小結
第四章 基于Johnson變換的并行執(zhí)行時間預測
    4.1 引言
    4.2 Johnson變換
    4.3 正態(tài)樣本的近似分布
    4.4 并行執(zhí)行時間預測模型的實現(xiàn)及其性能分析
    4.5 并行搜索執(zhí)行時間預測模型
    4.6 實驗結果
        4.6.1 常用分布
        4.6.2 實際程序的并行執(zhí)行時間分布
    4.7 本章小結
第五章 總結與展望
    5.1 全文總結
    5.2 研究展望
參考文獻
發(fā)表論文和科研情況說明
致謝



本文編號：3661619