并行計算中圖劃分算法的研究.pdf

1、現(xiàn)在，并行計算的平臺絕大部分是分布式并行系統(tǒng)。分布式并行系統(tǒng)能否快速有效處理并行計算，除了依賴于分布式并行系統(tǒng)性能、網(wǎng)絡(luò)帶寬、并行算法等，還與任務(wù)分配和調(diào)度順序有關(guān)。以一種合適的順序?qū)⑷蝿?wù)分配到處理器群上，以便提高系統(tǒng)使用效率和減少周轉(zhuǎn)時間是任務(wù)分配的目。圖劃分算法為任務(wù)分配問題提供了解決方法。將任務(wù)分配問題轉(zhuǎn)換為圖模型，使用圖劃分算法解決任務(wù)分配問題。
　　本文的研究環(huán)境是異構(gòu)的分布式并行系統(tǒng)，使用任務(wù)交互圖(TIG)和多層圖劃

2、分算法來研究任務(wù)分配問題。多層圖劃分算法分為三個階段:粗化（聚類）階段、初始化分階段和細(xì)化階段。以往的聚類方法中，某兩個任務(wù)是否能聚類僅僅取決于它們之間的通信代價。然而這是不夠準(zhǔn)確的，如果一個任務(wù)能被分配到一個更好的處理器上，也即在這個處理器上該任務(wù)總的執(zhí)行代價要優(yōu)于在之前的處理器上的執(zhí)行代價。因此本文提出的聚類啟發(fā)式算法考慮了任務(wù)之間的通信代價以及它們的不同。同時，任務(wù)分配到處理器的順序會影響分配質(zhì)量，因此本文提出了在兩階段方法中采用

3、改進(jìn)的度量方式來決定分配順序，并在細(xì)化階段改進(jìn)了FM算法。最后，本文提出了一種基于迭代改進(jìn)的啟發(fā)式多層劃分算法NTAT。
　　文中提出的改進(jìn)的任務(wù)分配算法是靜態(tài)的，也就是說在程序開始執(zhí)行時任務(wù)分配已經(jīng)完成。但是，很多應(yīng)用中可能會使用動態(tài)的任務(wù)分配方法以適應(yīng)各種突然出現(xiàn)的情況，如工作量增加、處理器故障和鏈路故障等。改進(jìn)的算法不適于動態(tài)劃分的情況，因為動態(tài)的任務(wù)分配方法需要考慮與系統(tǒng)組件之間的交互，如與進(jìn)程遷移機(jī)制的交互，同時還必須考