【摘要】：近年來，，集群系統(tǒng)成為高性能計算的主流平臺，在此系統(tǒng)上進行并行計算蘊涵著巨大的計算潛力，調度是挖掘這些計算能力的關鍵技術。在并行系統(tǒng)中，應用任務被劃分為多個子任務，有向無環(huán)圖（DAG）因能反映并行系統(tǒng)中各子任務以及這些任務間的依賴關系而被廣泛采用，本文研究基于DAG圖的集群系統(tǒng)任務調度問題，具體如下： （1）對于同構集群下的調度問題，采用表調度技術解決。分析現(xiàn)有表調度算法的不足，在此基礎上提出基于動態(tài)關鍵路徑的全局調度算法GDCP。該算法在調度任務選擇階段準確地賦予任務優(yōu)先級，并結合全局搜索策略選擇處理機。實驗及數(shù)據(jù)分析表明，該算法有效地提高了調度性能。 （2）對于異構集群下的調度問題，采用遺傳調度算法解決。針對傳統(tǒng)遺傳調度算法在種群初始化方式上的缺陷，提出異構系統(tǒng)中改進的遺傳調度算法ISGA。該算法利用任務的屬性值來構造染色體，得到優(yōu)質的初始種群。實驗及數(shù)據(jù)分析表明，該算法可以獲得較好的調度質量。 （3）將本文研究成果應用于與國家電網(wǎng)電力科學研究院合作的項目“實時監(jiān)控系統(tǒng)的并行處理”中，以驗證它們在實際計算環(huán)境中是有效的。
[Abstract]:In recent years, cluster system has become the mainstream platform of high performance computing. Parallel computing on this system has great computing potential. Scheduling is the key technology to mine these computing capabilities. In parallel systems, application tasks are divided into subtasks, and directed acyclic graphs (DAG) are widely used because they can reflect subtasks and their dependencies in parallel systems. In this paper, the task scheduling problem of cluster system based on DAG graph is studied. The details are as follows: (1) Table scheduling technology is used to solve the scheduling problem in isomorphic cluster. Based on the analysis of the shortcomings of the existing table scheduling algorithms, a global scheduling algorithm based on dynamic critical paths (GDCPs) is proposed. The algorithm accurately assigns priority to the task in the scheduling task selection phase and combines with the global search strategy selection processor. Experimental results and data analysis show that the proposed algorithm can effectively improve the scheduling performance. (2) genetic algorithm is used to solve the scheduling problem in heterogeneous clusters. Aiming at the defects of the traditional genetic scheduling algorithm in population initialization, an improved genetic scheduling algorithm ISGA in heterogeneous systems is proposed. The algorithm uses the attribute value of the task to construct the chromosome, and obtains the high quality initial population. Experiments and data analysis show that the algorithm can achieve better dispatching quality. (3) the research results of this paper are applied to the parallel processing of real-time monitoring system, which is a cooperative project with the State Research Institute of Electric Power Sciences of State Grid. To verify that they are valid in a real computing environment.
【學位授予單位】：南京航空航天大學
【學位級別】：碩士
【學位授予年份】：2012
【分類號】：TP338

【參考文獻】

相關期刊論文 前5條

1 舒昌奇,蘆偉;電力系統(tǒng)監(jiān)控的幾種類型對比[J];甘肅科技;2004年08期

2 鐘求喜,謝濤,陳火旺;任務分配與調度的共同進化方法[J];計算機學報;2001年03期

3 石威,鄭緯民;相關任務圖的均衡動態(tài)關鍵路徑調度算法[J];計算機學報;2001年09期

4 周雙娥,袁由光,熊兵周,歐中紅;基于任務復制的處理器預分配算法[J];計算機學報;2004年02期

5 陸鑫達,鄭飛,陳楚詢;異構計算系統(tǒng)的任務調度算法SMT-GA[J];小型微型計算機系統(tǒng);1999年04期

本文編號：2198893