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

Abstract

一個有效率的工作排程方法為使異質系統達到高效能的重要因素之一。工作排程方法的作用即藉由安排應用程式中的工作置於處理器上，使得應用程式能更有效率的執行。這個問題亦為NP-complete的問題。我們在研究中發現，多數的工作排程方法都假設系統的處理器由全連通網路鏈結而成且假設不可能發生鏈結碰撞的情形。為了得到更正確且有效率的排程結果，我們將可能發生鏈結碰撞的情形納入系統假設中。我們提出一個有效率的工作排程方法，此方法會先透過一個工作優先權函數計算每個工作的優先權，接下來再一一選擇擁有較高優先權的工作分配給具有最短工作完成時間的處理器執行。模擬結果顯示出我們所提出的方法明顯在效能上優於其他同樣解決此類問題的方法。

Effective application scheduling is critical for achieving high performance in heterogeneous computing environments. An application scheduling problem is to find the minimum schedule length by arranging tasks of application on computing resources. This problem is a NP-complete problem. Most task scheduling algorithms assume fully connected heterogeneous processors and ignore contention on the network links. For more accurate and efficient schedules, we take the link contention constraints into our system model. We propose a Duplication-based Earliest Finish Time (DEFT) algorithm to solve the scheduling problem effectively. The DEFT algorithm selects the task with highest bottom_level value at each step and assigns the selected task to the processor, which minimizes its earliest finish time by a task duplication mechanism. The simulation studies, based on randomly generated graphs, show that our scheduling algorithm significantly surpasses other algorithms in terms of minimizing the scheduling length of applications.