規律演算法上工作程序安排及處理處分配問題之研究

Abstract

本計畫將要研究規律演算法上安排工作程 序(Time schedule,簡稱排程)和處理機分配(Processor allocation)的問題,並且提出更有效率的方法,解 決某些這類型之問題.我們的研究可分為兩個 部分:第一個部分是針對資料流動圖(Data-flow graph)找其最佳速率排程;第二個部分則是找一 個有系統的時空映射法,將一規律演算法映射 到線性陣列.對於第一個部分,我們將嘗試對資 料流動圖做追蹤(traverse)及重新定時(retime),以 推導出一追蹤圖;接著,我們將設法對此追蹤圖 做拓樸排序,以推衍一基本時序式樣;最後,希望 藉著重覆此式樣,得到該資料流動圖之最佳速 率排程.若以上的觀念是正確的話,則我們將可得到一個複雜度小於過去最好方法的設計程式 .對於第二個問題,我們基本的想法是採用一個 兩步驟的設計原則;在第一步驟裡,我們將設法 把一個已獨立分解的規律演算法,藉著一單位 模組(unimodular)矩陣,轉換到一對等之演算法,其 相依矩陣為一單位矩陣;在第二步驟裡,我們將 嘗試把此對等之演算法,藉著一特定之轉換矩 陣,映射到模組可擴展的線性陣列.如此,若要映 射原先的規律演算法到此線性陣列,則可應用此單位模組矩陣和該特定轉換矩陣之乘積做為 時空映射矩陣.若此法可行的話,則我們提出了 一個有效率的方法設計規律演算法的線性陣列 .此法的時間複雜度和問題大小無關,而只和規 律演算法的維數有關.此外,我們將更進一步地 證明所設計出來的線性陣列,無論是在時間或 空間上,都是近似最佳的設計.