SMP叢集上考量記憶體之平行排程演算法

Abstract

近年來，需要大規模計算、大量記憶體、以及儲存空間的問題，例如生物資訊、物理學、天文學、氣象預測、地震預報，以及各式各樣的商業問題等等，越來越多，且日益複雜。為了幫助人們解決這些問題，電腦科學家們努力不懈投入與高性能計算環境相關的軟硬體之研究與開發，叢集系統就是其中之一。
本論文主要在SMP(Symmetric Shared-Memorg Multiprocessor)cluster上，parallel jobs的backfilling scheduling 演算法研究。在叢集環境上，為了能有效利用系統資源，排程方法考慮的元素也從只考慮CPU(Central Processing Unit)到同時考慮CPU以及記憶體兩者，先前學者已經證實同時考慮CPU以及記憶體能有效減少反應時間，然而若嚴格限制系統資源必須足夠提供工作所需求的記憶體和CPU，才能允許該工作執行，這樣的作法導致許多jobs必須花費相當長的等待時間。
我們提出一個有限度放寬記憶體容量上限的方式，當記憶體不足以讓工作執行的時候，便將排程方法所允許的系統記憶體上限略為提高，讓原本無法執行的工作能夠執行，因此該工作的等待時間便能夠縮短。然而此方法會讓所有執行中工作的總需求記憶體比原本高，因此系統會產生較多的page faults，導致執行中工作的執行時間將比原本的情況下還要長，所以總體的執行時間拉長。我們的排程方法便是在等待時間和執行時間兩者中找出最佳化。我們撰寫模擬器模擬一個較大規模叢集系統，使用具有公信力的trace，實驗的結果證實我們提出的有限度放寬記憶體容量上限能讓反應時間更進一步的減少。This paper studies the parallel job scheduling algorithm on SMP clusters. To reduce the number of page faults and shorten the executing time of jobs, previous research suggests that we must consider CPU and memory at the same time. That is, the ready jobs can't be executed until they get enough memory and CPU resources. In this way, as the memory resource can't satisfy the running jobs immediately, the jobs must spend time in waiting memory.
Instead of waiting for enough memory, in this paper, we suggest that the memory restriction can be lessened. Our method will reduce the waiting time without increasing too many page faults. That is, the method balances the execution time and waiting time at the same time. Experimental results show that our method performs better than some known job scheduling algorithms.