共用匯流排及記憶體之多處理機系統上的最佳工作指派

Abstract

在本論文中我們提出了共用記憶體單一匯流排之多處理機系統上的最佳工作指派的方 法。一個工作事先被分割成許多適當的工作模組，工作模組之間有優先順序存在，經 本論文所提之方法可在共用記憶體單一匯流排之多處理機系統上得到最佳的工作指派 ，也就是說，此工作的執行時間最短。我們修改了一般用來表示工作模組系統的傳統 表示圖，簡化了整個問題的複雜度。如此，工作模組間資料傳遞的動作可被視為一組 讀出與寫入共同記憶體動作之組合。另外，我們利用工作模組系統的拓撲次序把優先 順序關係包含在最佳解之中，使得工作指派的問題更接近實際的應用。最佳工作指派 的找尋被表示成狀態空間找尋的問題，然後用人工智慧中所提之A * 演算法來解它。 為了加快找尋的速度，我們提出了啟發函數，減少了很多不必要的節點擴展，使得演 算法的效率大為提高。舉便說明及實驗結果印證了我們所提之方法的可行性。最後， 我們舉了一個工作指派的例子，並在個人電腦區域網路上執行，說明了所提之方法對 於實際工作在多處理機系統上的可用性。