透過預排式處理器分配技術在多叢集系統中增進平行工作排程效能

Improving Parallel Job Scheduling Performance in Multi-cluster through Look-Ahead Processor Allocation

史伯其(Po-Chi Shih)

指導教授 ： 鍾葉青

國立清華大學/電機資訊學院/資訊工程學系/博士(2012年)

https://doi.org/10.6843/NTHU.2012.00498

摘要

多叢集系統是一個廣泛應用於超級電腦、格網計算及雲端計算的基礎架構，如何有效率的運用多叢集中的資源也因此受到越來越多的重視，其中最主要的挑戰就是如何做資源排程，其中如何將資源分配給各個工作是個重要的議題，一個聰明的資源分配方法要能有效的考量工作提出的需求，以及目前的資源使用狀態，來增進系統效能。
本論文探討異質多叢集系統中的處理器分配議題，主要負責在多叢集所有可用的處理器中選擇該分配那些處理器給每個工作，傳統的處理器分配方法僅考量單一效能因素，如資源碎裂或是速度異質性，因此產生了如Best-Fit及Fastest-First這樣的分配方法。然而這些方法僅能在某些工作特性下表現優秀。在本論文中我們提出預排式處理器分配方法，此方法利用目前在等待中的工作所提供的資訊，例如有多少工作在等待、這些工作的執行順序、它們需求的處理器數目及預估的執行時間等，來決定要分配哪個叢集的處理器給每個工作，因此資源的分配是動態的，並且會依照目前的工作及資源使用狀況來決定。
我們透過廣泛的模擬實驗來評估所提出方法的效能，實驗變因包括各種可能影響效能的因素如工作特性及資源的組成。實驗結果顯示出預排式處理器分配方法的效能，在絕大多的實驗變因中都能比傳統的處理器分配方法有更好的表現。另外，結果也顯示了工作執行時間預估的優點，即便在時間預估的非常不準確的情況下都能有不錯的效能表現。若能得到準確的時間預估，則所提出的方法可以比傳統的方法最高提升4倍的效能。

關鍵字

平行工作排程 ； 處理器分配 ； 異質多叢集系統 ； 預排

並列摘要

Multi-cluster are an important and commonly used architecture in supercomputing, grid computing and the emerging cloud computing paradigm. Techniques for efficiently exploiting multi-cluster resources become increasingly significant. A critical aspect of exploiting these resources is the challenge of scheduling, in which how to allocate resources to each job is an important issue. Intelligent allocation algorithm can make good use of the information provided by the submitted jobs and current resource status to improve the system performance.
In this dissertation we focus on the issues of processor allocation in heterogeneous multi-cluster (HMC) system. In a HMC system, processor allocation is responsible for choosing available processors among clusters for job execution. Traditionally, processor allocation in HMC considers only single performance factor, resource fragmentation or processor heterogeneity, which leads to heuristics such as Best-Fit (BF) and Fastest-First (FF). However, those heuristics only favor certain types of workloads and cannot be changed adaptively. In this dissertation we propose the look-ahead processor allocation technique, which make use of the information of the waiting jobs, such as amount, execution sequence, processor requirement, and runtime estimation, to guide the decision of processor allocation. Thus, the allocation decision is made dynamically according to current workload and resource configurations.
Extensive simulations that consider different workload and resource configurations are conducted for performance evaluation. Simulation results show the effectiveness of look-ahead processor allocation methods, which can achieve better performance than traditional allocation methods for most cases. Results also indicate that the information of estimated job runtime can efficiently improve the system performance, even with high estimation error. With precise job runtime, the performance improvement can be made up to four times over traditional methods.

並列關鍵字

parallel job scheduling ； processor allocation ； heterogeneous multi-cluster ； look-ahead

參考文獻

D. Lifka, "The ANL/IBM SP scheduling system," Proceedings of the International Workshop on Job Scheduling Strategies for Parallel Processing, pp. 295-303, 1995.

[3] I. Foster, "The Grid: A New Infrastructure for 21st Century Science," Physics Today, vol. 55, pp. 42-47, 2002.

[4] M. Armbrust, et al., "Above the clouds: A berkeley view of cloud computing," EECS Department, University of California, Berkeley, Tech. Rep. UCB/EECS-2009-28, 2009.

[5] A. Bucur and D. Epema, "The Influence of the Structure and Sizes of Jobs on the Performance of Co-allocation," Job Scheduling Strategies for Parallel Processing, pp. 154-173, 2000.

[8] J. Qin and M. A. Bauer, "A Study on Job Co-Allocation in Multiple HPC Clusters," High-Performance Computing in an Advanced Collaborative Environment, 2006. HPCS 2006. 20th International Symposium on, pp. 3-3, 2006.