本文選題：分布式并行系統(tǒng) + 圖劃分��； 參考：《華中師范大學(xué)》2013年碩士論文

【摘要】：現(xiàn)在,并行計(jì)算的平臺(tái)絕大部分是分布式并行系統(tǒng)。分布式并行系統(tǒng)能否快速有效處理并行計(jì)算,除了依賴(lài)于分布式并行系統(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)和多層圖劃分算法來(lái)研究任務(wù)分配問(wèn)題。多層圖劃分算法分為三個(gè)階段：粗化(聚類(lèi))階段、初始化分階段和細(xì)化階段。以往的聚類(lèi)方法中,某兩個(gè)任務(wù)是否能聚類(lèi)僅僅取決于它們之間的通信代價(jià)。然而這是不夠準(zhǔn)確的,如果一個(gè)任務(wù)能被分配到一個(gè)更好的處理器上,也即在這個(gè)處理器上該任務(wù)總的執(zhí)行代價(jià)要優(yōu)于在之前的處理器上的執(zhí)行代價(jià)。因此本文提出的聚類(lèi)啟發(fā)式算法考慮了任務(wù)之間的通信代價(jià)以及它們的不同。同時(shí),任務(wù)分配到處理器的順序會(huì)影響分配質(zhì)量,因此本文提出了在兩階段方法中采用改進(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í)還必須考慮其在細(xì)化階段時(shí)的代價(jià)。因此,本文所有算法的改進(jìn)是在靜態(tài)劃分的基礎(chǔ)上進(jìn)行的。
[Abstract]:Nowadays, the platform of parallel computing is distributed parallel system. Whether distributed parallel system can deal with parallel computing quickly and effectively depends not only on the performance of distributed parallel system, network bandwidth, parallel algorithm, but also on task allocation and scheduling order. Tasks are assigned to the processor population in a suitable order in order to improve system efficiency and reduce turnaround time. The graph partition algorithm provides a solution to the task assignment problem. The task assignment problem is transformed into graph model, and the graph partition algorithm is used to solve the task assignment problem. The research environment of this paper is a heterogeneous distributed parallel system. Task interaction graph (TIGG) and multi-layer graph partition algorithm are used to study the task assignment problem. The multilayer graph partition algorithm is divided into three stages: coarsening (clustering) phase, initialization stage and thinning stage. In previous clustering methods, whether two tasks can be clustered only depends on the communication cost between them. However, this is not accurate, if a task can be assigned to a better processor, that is, the overall execution cost of the task on this processor is higher than that on the previous processor. Therefore, the proposed clustering heuristic algorithm takes into account the communication cost between tasks and their differences. At the same time, the order in which tasks are assigned to the processor will affect the allocation quality. Therefore, an improved measurement method is proposed to determine the allocation order in the two-phase method, and the FM algorithm is improved in the thinning stage. Finally, a heuristic multilayer partition algorithm based on iteration is proposed in this paper. The proposed improved task allocation algorithm is static, that is, the task assignment is completed by the time the program begins to execute. However, many applications may use dynamic task allocation methods to adapt to various sudden situations, such as increased workload, processor failures and link failures. The improved algorithm is not suitable for dynamic partitioning because the dynamic task allocation method needs to consider the interaction with system components such as the process migration mechanism and the cost of the process migration mechanism. Therefore, all the algorithms in this paper are improved on the basis of static partitioning.
【學(xué)位授予單位】：華中師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2013
【分類(lèi)號(hào)】：TP338.6

【參考文獻(xiàn)】

相關(guān)期刊論文 前9條

1 王征;劉心松;李美安;;一種高效的基于可復(fù)制資源的分布式負(fù)載均衡策略[J];電子學(xué)報(bào);2006年08期

2 朱文興;程泓;;VLSI電路劃分問(wèn)題的分散搜索算法[J];電子學(xué)報(bào);2012年06期

3 冷明;孫凌宇;郁松年;;一種VLSI剖分系統(tǒng)的研究與實(shí)現(xiàn)[J];計(jì)算機(jī)工程與應(yīng)用;2010年03期

4 秦嘯,韓宗芬,龐麗萍;基于異構(gòu)分布式系統(tǒng)的實(shí)時(shí)容錯(cuò)調(diào)度算法[J];計(jì)算機(jī)學(xué)報(bào);2002年01期

5 王友良,葉柏龍;分布式系統(tǒng)中動(dòng)態(tài)負(fù)載平衡的研究[J];科學(xué)技術(shù)與工程;2005年09期

6 朱美強(qiáng);程玉虎;李明;王雪松;馮渙婷;;一類(lèi)基于譜方法的強(qiáng)化學(xué)習(xí)混合遷移算法[J];自動(dòng)化學(xué)報(bào);2012年11期

7 王靈霞;張遠(yuǎn)平;吳佩莉;;蟻群算法求解分布式系統(tǒng)任務(wù)分配問(wèn)題[J];計(jì)算機(jī)工程與設(shè)計(jì);2008年06期

8 劉旭;莫?jiǎng)t堯;;多層次圖排序算法及其在圖剖分中的應(yīng)用[J];數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用;2008年03期

9 陳志剛,李登,曾志文;分布式系統(tǒng)中一種動(dòng)態(tài)負(fù)載均衡策略、相關(guān)模型及算法研究[J];小型微型計(jì)算機(jī)系統(tǒng);2002年12期

相關(guān)博士學(xué)位論文 前1條

1 劉紅衛(wèi);半定規(guī)劃及其應(yīng)用[D];西安電子科技大學(xué);2002年

相關(guān)碩士學(xué)位論文 前2條

1 張漢珍;譜劃分算法中特征向量選取方法的研究[D];西安電子科技大學(xué);2010年

2 劉虎;基于特征約束的四邊形網(wǎng)格劃分算法研究與實(shí)現(xiàn)[D];南京航空航天大學(xué);2007年

，

本文編號(hào)：2030579