在有現個處理器之星狀網路上之程式最佳分割

Abstract

如何將許多模組同時分配給多個處理器執行，且使得完成這些模組的代價最小，此問 題一般稱之為模組配置問題。在本篇論文中，我們將針對由一個主要處理器和有限個 衛星征處理器所構成之星狀綱路的硬體架構上研究，且提出一個演算法來解決一些模 組配置問題，也就是將一些具有特殊架構的程式分配給此星狀綱路執行，而使得執行 這些程式的反應時間最短。雖然有許多因素影響程式的分割配置，但是為了簡化此分 割問題，在本篇論文中我們只考慮執行代價與資料傳遞代價二個因素。 本篇論文中我們將解決以下四個在有限個處理器之星狀綱路上的程式分割問題：分割 多個鏈狀架構之平行程式，分割多個任意架構之循序程式，分割單一樹狀之平行程式 ，以及分割多個樹狀之平行程式。在解決這些分割問題的過程當中，我們首先從表示 模組關係的模組圖形中建立一個有方向性的三重加權對偶圖形，第二步將從此有向性 的三重加權對偶圖形中，尋找一條滿足一些條件限制的最佳路徑，而此路徑可表示一 種程式最佳分割策略。 我們提出的多重限制演算法無法解決最廣泛的配置問題，因為此問題屬於NP-complet e 問題，所以最後我們將做一個結論以及提出值得更進一步研究之方向。