星狀網路上之程式最佳動態分配

Abstract

所謂的分配問題，乃是給定一個用某種特殊連接結構相連的多重電腦系統，以及一些 彼此以某種方式聯系之模組所構成的程式。我們的目的便是希望將這些程式用某種方 式分配給這些處理機去執行，使得執行它們所需的總代價為最低。 Bokhari 在1988提出一演算法用以解決如何將多個任意架構的循序程式置於星狀網路 上執行的靜態分配問題，而使得其執行和聯系的時間為最短。在這篇論文中，我們將 考慮多個任意架構的循序程式如何放在星狀網路上執行的動態分配問題。我們將Bolh an的靜態分配模式加以延伸并提出一動態分配演算法來求得一最佳動態分配使得系統 所需之執行、聯繫和搬移的總時間為最短。其中靜態和動態分配的最大區別在於：若 是採用靜態分配，則任一模組在整個程式的執行過程中始終固定在某一處理機上執行 。但若是採用動態分配，則任一模組可在程式執行過程中，任意地在不同的處理機間 作搬動，而使得程式的執行更具效率。 當搬移時間趨近無窮大時，我們證明動態演算法的解和靜態的解相等。為了評估該演 算法262 個例子被模擬在IBMRS6000/320 工作站上，我們演算法所需的時間除以Bodh ari的時間的平均比率值約為0.865。從這些實驗可歸納出我們的演算法不錯。最後， 文中并有結論和今後繼續研究的方向。