多處理機計算系統之近似最佳的群組分配演算法

Abstract

排程演算法在決定多處理機電腦系統的工作效率上扮演極重要的角色。在 工作單元具有先後執行順序的需求下，許多不同的啟發式演算法已經提出 最小排程所需時間。然而這些方法均假設無工作單元間的通訊。另外，群 組排程演算法則可應用在多工作單元計算時具單元間通訊，但無單元先後 執行次序的情形。這兩種演算法均未利用多工作單元計算應用環境的知識 。研究人員提出新的群組排程演算法兼顧了工作單元間的通訊及先後執行 順序。本篇論文提出 GS-A, GS-B,和GS-C三個群組演算法含有單元間通訊 及執行時順序。其所處理的排程問題是兼顧不同的輸入圖形特性，並檢測 其在單位時間產量，處理機利用率，及工作單元反應時間的變化情形。這 些演算法以許多不同的計算參數來評測其實驗摩擬。三者之中，以 GS-C 結果最好，其排程時間距最佳值均在百分之三以內。 The scheduling algorithm plays a vital role in determining the performance of a multiprocessor computer system. Various heuristic scheduling algorithms have been proposed to determine the minimum scheduling time needed for multiprocess computations having precedence constraints among processes. However, these algorithms assume no interprocess communication. Alternatively, the group scheduling algorithm is applicable to multiprocess computations having interprocess communications but no precedence constraints. Neither algorithm has taken advantage of knowledge of the application environment for multiprocess computations. New group scheduling algorithms, which take into account both precedence constraints and interprocess communications, are being examined by researchers. This paper proposes three group scheduling algorithms, GS-A, GS- B, and GS-C. All three algorithms include both precedence constraints and interprocess communications. However, each algorithm solves the scheduling problem according to different characteristics of input patterns. The effectiveness of these three algorithms in terms of throughput, processor utilization rate, and response time is examined. Various dependencies of these algorithms on computation parameters are investigated through simulation experiments. Among these three algorithms, GS-C performs best. All shceduling resutls obtained via GS-C are shown to be within 3 percent of optimal.