一個為格網資源拓樸網目化之方形覆蓋方法

Abstract

格網運算具有多樣性的資源可滿足使用者不同服務需求。由於運算密集(computing-intensive)及通訊密集(communication-intensive)問題則有各自考量的因素來進行資源選擇，所以對於資源選擇策略有所區別。平行處理問題還必須要經由排程方法來將子任務分派至運算格網的運算節點上。然而在一般網路上，資源選擇及工作排程所指派的運算節點座落在網路中不同位置，如何將散亂且能力不均等的運算節點轉換的與交連網路(interconnection network)架構一樣有效率是一個重要問題。 本篇論文主要研究目在於提出一個ISPA演算法來將格網資源拓樸虛擬地轉換至規則的網目拓樸(mesh topology)，格網資源拓樸的資源被重新組織於虛擬網目(virtual mesh)之中。我們的演算法中主要分為兩部份，利用排列策略先將大部分的虛擬節點進行指派給運算節點，再使用依附策略將剩餘虛擬節點進行依附。經由彈性的依附策略選擇，虛擬網目上可以呈現不同分配運算能力(通訊能力)狀態。ISPA演算法解決運算導向(通訊導向)的問題。 根據實驗結果得到以下結論，排列策略影響在於區塊排列程序中基本區塊排列方式的多寡，而依附策略影響整體虛擬網目中虛擬節點運算能力變異數及虛擬連結平均通訊能力。在經由適當的資源選擇下，運算導向的依附策略所得到的虛擬節點運算能力變異數小於等於其他依附策略。通訊導向的依附策略所得到的虛擬連結平均通訊能力大於等於其他依附策略。本篇論文所提出的演算法在處理通訊導向問題時，經由適當的排列策略與依附策略選擇下能比PaGrid分割器減少2~7%的通訊量而獲得較好的表現。由於排列程序的演算法複雜度較高，為未來可改進的方向。

Grid computing deals with deploying various computing and network resources for meeting diverse users demands. Each grid-computing problem, either computing-intensive or communication-intensive, has its own requirements in selecting resources. Paralleling a grid-computing problem starts with dividing the problem into several pieces, called subtasks, and allocating grid resources to them. Then computing nodes in different locations are configured in some topology. And this is determined through resource selection and job scheduling. The key to successful resource selection and job scheduling lies in balancing the load of both computation on nodes with different computing power, and communication on the underlying interconnection network that supports the topology. This is a critical issue that has attracted a lot of research attention in the grid-computing area. In this thesis, we propose the ISPA algorithm to transform a network resource topology of grid into a regular mesh topology. The grid computing resources are organized to form a virtual mesh. The proposed ISPA algorithm consists of two major phases. In the first phase, the majority of the virtual nodes are assigned to some computing nodes by a permuting process. In the second phase, the remaining virtual nodes are assigned through an attaching process. With flexible and versatile choices in attaching nodes, the ISPA algorithm can exert different ways of distributing resources to solve the computing-oriented and communication-oriented problems effectively. Based on simulation results, we come to the following conclusions. The permuting policy plays an import role in determining the number basic blocks of permutation. The attaching policy has influence on the variance of computational ability of virtual nodes and the average communication ability of virtual links. We find that the computation-oriented policies allow the ISPA algorithm to achieve lower variance of computational ability of virtual nodes than the other policies. We also find that the communication-oriented policies enable the ISPA algorithm to attain higher communication ability of virtual links than the other policies for attaching processes. In respect to dealing with communication-oriented problems, the proposed algorithm shows a significant reduction in communications by 2~7%, compared with the PaGrid. However, the permuting process in ours proposed algorithm requires a high complexity in computation. And this deservers further attention of future research.