Abstract
所謂矽編譯器，是將用高階語言描述的behavioual specification編譯轉換成對映功能之晶版輸出。我們THEDA group 自行發展了一套矽騙譯器系統，可以把用我們定義之高階語言ABDL所描述的behavioual spec-ification,轉換成對映之linear topology架構的晶片輸出。設計一套矽編譯器系統主要包括以下四個部分：程式剖析(parsing)、 排序(scheduling)、配置(allocation)、控制器(controller)合成。程試剖析是將原始程式轉換成控制/ 資料流程圖(CDFG)。排序則是根據控制/ 資料流程圖，將運算排在適當的步驟。而配置是將物體( 如運算、變數以及資料傳愉) 指定給特定硬體( 如函數單元、暫存器及接線) 。最後，根據排序後之資料流程圖與配置的資料路徑(data path) ，可以合成需要的控制單元。本篇論文是研究排序的問題。以往排序問題之研究，很多都只限於一個基本區塊(basic block) 內之運算的排序，亦即只能處理直接碼(straight code) ，稱之為區域排序(local scheduling)。我們的排序器，則能處理結構化程式，即能同時處理由IFC、CASE 及LOOP所產生的許多基本區塊之排序稱之為整體排序(global scheduling) 。整體排序問題，是考慮運算可以從一個基本區塊移到另一個基本區塊，以期得到整體的最佳解。因為允許運算可以排在最適當的區塊，所以整體排序要遠比單單只有區域排序來得好。我們分析了結構化程式的特性，提出了若干定理及證明，可以了解在結構化程式的前提下，一個運算如何能在各個基本區塊間移動。根據我們提出的定理及證明，我們提出一套整體排序的演算法，可以在很短時間內，得到接近最佳解結果。