多處理機系統上工作配置問題之研究

Abstract

在本篇論文中，我們提出一個一般化的工作系統模式和一個啟發式演算法則用以解決 多處理機系統上工作配置和排程之問題；亦即，如何將一些彼此間具有工作間通訊和 存在著執行順序關係的工作配置於某些處理機上。值得一提的是，我們並不假設處理 機採用不可搶奪的排程策略，而是假設每一處理機均由所有配置其上的工作公平地使 用。本論文所提出的啟發式演算法則採用事件驅動的方式，而其所訴求之目的則為縮 短系統執行結束所需時間。為了評估所提之啟發式演算法則，我們將其用以解決數千 個已知最佳配置的工作－處理機系統；和最佳配置比較起來，所提之啟發式演算法則 可以產生相當不錯的配置結果。