并行計(jì)算中圖劃分算法的研究.pdf

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

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

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