一個爲格網資源拓撲網目化之搜尋方法

Abstract

在平行處理的研究中，工作排程以及資源選擇是很重要的議題。透過工作排程我們可以清楚瞭解各個子工作之間執行的順序性以及執行的時效性，目的就是為了將工作的總體執行時間壓縮到最短。而在資源選擇的議題上，有些工作可能需要大量的計算，有些工作可能需要大量的通訊，針對不同的工作性質所選擇的資源將有所不同。在格網運算的環境上，一件平行工作透過工作排程以及資源選擇所選出來資源將會以不規則拓撲的型態分佈在網路上。另外在平行處理的應用方面，有很多的規則型態的連接網路常被用來執行平行程式以便於加速平行處理的速度。 這篇論文主要的研究目標在於提出一個方法將一個在格網運算環境中經過工作排程以及資源選擇所得到的不規則的格網資源拓撲對應到一般平行處理所使用的規則的通訊網路拓撲上。我們採用啟發式搜尋法的方式來實作，並從得到的規則拓撲上瞭解該規則拓撲所呈現出的計算能力以及通訊能力，以便比較策略之間的差異性。

經過實驗的結果我們得到以下結論，隨著計算節點的增加使得格網的整體計算能力與通訊能力都會增加。排列策略的影響主要是在前期的區塊在Mesh上的排列組合方式。而依附策略對整體Mesh的影響計算能力與通訊能力的影響則是比較大的。計算能力優先的依附策略能夠使平均最小計算能力與平均計算能力之間的差距較小，通訊能力優先的依附策略能夠使平均最小通訊能力與平均通訊能力之間的差距較小。

In parallel processing research, job scheduling and resource selection are two important issues. Through scheduling can find execution order and execution time for every sub-task in an effort to shorten the total execution time. In the resource selection issue, some tasks maybe need a great deal of computation, others may require a large amount of communication. Resource selection is influenced by the requirements of task quality, and different requirements may result in varying resource selection. In the grid computational environment, resources selected by job scheduling and resource selection of a task are placed on irregular topology. On the implement of parallel processing, many regular connection networks are used to speed up parallel program execution. This thesis proposes a mapping method that embeds irregular grid resource topology produced by job scheduling and resource selection to a regular connection network topologies. We use a heuristic search method to find and implement the computational ability and communication ability on regular connection network topologies. With the proposed method, we are allowed to observe the performance differences among various selection policies. Based on the of the experiment result, we have found that the increase in computational nodes helps enhance the computation and communication capability of the grid computing. The permutations of the blocks on the mesh are mainly influenced by the permutation policy. The computational-ability-first attach policy can make the minimum computational ability close to average computational ability, and the communication-ability-first attach policy can make the minimum communication ability close to average communication ability.