一個在異質系統上考量連結碰撞的有效工作排程方法

Abstract

豐富及各具特色的運算資源使得異質系統很適合處理平行化或者是分散式的應用程式。所謂的工作排程就是將應用程式中的工作妥善安排在運算資源上，使得應用程式能夠更有效率的執行。因此，異質系統需要一個有效工作排程方法來提升系統的效能。為了使得工作排程問題更為實際，我們額外又將可能發生連結碰撞的狀況納入系統的假設。我們延伸傳統list工作排程方法的精神提出一個預測通訊排程演算法。此方法的第一步驟，我們採用了一個新的工作優先函數，能夠同時考量關鍵路徑和工作的通訊行為。在第二個步驟，我們透過一個預測通訊的機制來選擇最恰當的處理器。模擬效能評估顯示我們所提出的方法在效能以及效率上都能夠比其他同樣解決此類問題的方法來得出色。詳細的演算法以及效能評估會在此論文中一一介紹。

Sufficient and various computing resources make heterogeneous computing system suitable for parallel and distributed application. A task scheduling problem is to find the minimum schedule length by arranging tasks of application on computing resources. In order to make this problem more practical, we take the link contention constraints into our system model. We extend from the list-scheduling algorithm and propose an effective and efficient algorithm called Communication Look-ahead Scheduling (CLS) algorithm. In the first phase of our method, we propose a new priority function which integrates both information from the concept of critical path and the communication behavior of each task. In the second phase, we select the appropriate processor for a task by means of communication look-ahead. According to the performance evaluations, our method is superior to other methods both in effectiveness and efficiency. The detailed description of our algorithm and performance evaluation will be given in the literature.