單匯流排型式多處理機中, 工作分配問題之研究

Abstract

本論文提出一套適合系統模擬程式在單匯流排型式多處理機系統上平行運算的工作分 派方法。所解決的問題是﹕在K 部相同型式的處理機系統上，如何分派程式之資料流 程圖中的運算工作，使得程式能在較短的時間內執行完成。 首先，把資料流程圖分割成許多可平行處理的樹狀架構小流程。目的在提高資料相依 的先後兩個節點被分派在同一部處理機的情形，以減少執行時處理機之間通訊的需要 次數。而所建構的小流程之執行時間，則以理想之最短執行時間為上限。對分割後的 所有樹狀架構小流程，再依可否分配在同一部處理機執行的測試結果，分派到合適的 處理機上。所謂合適，是指節點的運算時間不會互相重疊。即使有重疊，也以重疊最 少為要求。最後，設定各節點的執行優先權，儘量提早完成需透過匯流排送出資料的 運算，以進一步降低處理機之間互相延遲的情形。排程中並安排收送資料的時間，以 符合執行時的實際情況。