并行計算系統(tǒng)的負載平衡算法與并行執(zhí)行時間預測.pdf

1、本文主要研究并行計算系統(tǒng)中的負載平衡算法與并行執(zhí)行時間預測問題。 為能較快平衡系統(tǒng)中的負載，提出了“均分負載”平衡算法。該方法先對各處理器結點的已有負載按網絡中各處理器的速度進行劃分，然后把這些劃分好的小負載遷移到對應的處理器上，以平衡系統(tǒng)中各處理器的負載。分析表明：該算法時間性能較好，適于解決系統(tǒng)初始分配負載問題與系統(tǒng)負載極度失衡的平衡問題；但對于負載較平衡的系統(tǒng)，其負載遷移量很大。 為減小負載遷移量同時保持較快的平衡

2、速度，提出了“二分網絡”平衡算法。該方法按網絡的結點數(shù)把網絡分為兩子網絡，然后按兩子網絡的處理速度之比進行兩子網絡間的負載遷移，遞歸上述過程，直到各子網絡中只有一個結點時，系統(tǒng)經負載遷移后可達到平衡狀態(tài)。該算法具有平衡負載速度較快、負載遷移量較小的優(yōu)點，適于大多數(shù)條件下的負載平衡。 針對環(huán)與線性陣列的負載平衡速度較慢與遷移量較大的問題，提出了“貪心線性推移”平衡算法。該算法的思想是：把重負載結點過重的那部分負載按線性或環(huán)的路徑推

3、移到下一鄰居結點，循環(huán)推移直到整個系統(tǒng)負載平衡。此算法適用于任何具有哈密頓通路的圖結構網絡。一般情況下，其平衡過程的負載遷移量不大，且平衡負載速度較快。此外，還對網狀網等網絡結構的“貪心線性推移”平衡算法進行改進，而得到分兩階段的貪心線性推移平衡算法。實驗與分析表明：當平衡條件減弱時，這種改進能較大地提高算法的時間性能。 為解決由具有獨立同分布隨機執(zhí)行時間的子任務組成的并行任務的執(zhí)行時間預測問題，提出了基于Johnson分布的并