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

【摘要】：現(xiàn)在,并行計算的平臺絕大部分是分布式并行系統(tǒng)。分布式并行系統(tǒng)能否快速有效處理并行計算,除了依賴于分布式并行系統(tǒng)性能、網(wǎng)絡帶寬、并行算法等,還與任務分配和調(diào)度順序有關。以一種合適的順序將任務分配到處理器群上,以便提高系統(tǒng)使用效率和減少周轉時間是任務分配的目。圖劃分算法為任務分配問題提供了解決方法。將任務分配問題轉換為圖模型,使用圖劃分算法解決任務分配問題。 本文的研究環(huán)境是異構的分布式并行系統(tǒng),使用任務交互圖(TIG)和多層圖劃分算法來研究任務分配問題。多層圖劃分算法分為三個階段：粗化(聚類)階段、初始化分階段和細化階段。以往的聚類方法中,某兩個任務是否能聚類僅僅取決于它們之間的通信代價。然而這是不夠準確的,如果一個任務能被分配到一個更好的處理器上,也即在這個處理器上該任務總的執(zhí)行代價要優(yōu)于在之前的處理器上的執(zhí)行代價。因此本文提出的聚類啟發(fā)式算法考慮了任務之間的通信代價以及它們的不同。同時,任務分配到處理器的順序會影響分配質(zhì)量,因此本文提出了在兩階段方法中采用改進的度量方式來決定分配順序,并在細化階段改進了FM算法。最后,本文提出了一種基于迭代改進的啟發(fā)式多層劃分算法NTAT。 文中提出的改進的任務分配算法是靜態(tài)的,也就是說在程序開始執(zhí)行時任務分配已經(jīng)完成。但是,很多應用中可能會使用動態(tài)的任務分配方法以適應各種突然出現(xiàn)的情況,如工作量增加、處理器故障和鏈路故障等。改進的算法不適于動態(tài)劃分的情況,因為動態(tài)的任務分配方法需要考慮與系統(tǒng)組件之間的交互,如與進程遷移機制的交互,同時還必須考慮其在細化階段時的代價。因此,本文所有算法的改進是在靜態(tài)劃分的基礎上進行的。
[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.
【學位授予單位】：華中師范大學
【學位級別】：碩士
【學位授予年份】：2013
【分類號】：TP338.6

【參考文獻】

相關期刊論文 前9條

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

2 朱文興;程泓;;VLSI電路劃分問題的分散搜索算法[J];電子學報;2012年06期

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

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

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

6 朱美強;程玉虎;李明;王雪松;馮渙婷;;一類基于譜方法的強化學習混合遷移算法[J];自動化學報;2012年11期

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

8 劉旭;莫則堯;;多層次圖排序算法及其在圖剖分中的應用[J];數(shù)值計算與計算機應用;2008年03期

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

相關博士學位論文 前1條

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

相關碩士學位論文 前2條

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

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

，

本文編號：2030579