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

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

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

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