Abstract
傳統上, 我們都用一般用途電腦(general purpose computer)來執行一個程式, 它首先將程式轉換成與機器相關之機器碼(machine dependent code), 然后在其硬體上來執行。隨著IC制造技術的進步, 超大型積體電路(VLSI Circuit)的密度越來越高, 同時其制造成本也逐漸降低, 使得設計一個晶片來執行某一特定的工作成為可行, 在這種情況下, 由於硬體(hardware)可針對某工作作特殊的配置, 使得其resource使用率及performance 均可大為提高。然而對於特殊用途的晶片, 若由人工來設計, 不但其設計成本太高, 且需花費太長的時間, 此時一個設計自動化(Design Automation) 的CAD Tool就格外的需要。一般而言, 所謂高階合成(High Level Synthesis)系統, 能將高階語言描述的Behav-ioral specification 轉換成為相對應功能之晶片硬體架構(architectural specif-ication)之輸出。設計一套高階合成系統主要包括以下四個部分: 程式剖析(parsin-g)、運算元排序(operation scheduling)、硬體配置(hardware allocation)、 控制器(controller)合成。程式剖析是將原始程式轉換成控制/ 資料流程圖(CDFG), 運算元排序則是根據控制/ 資料流程圖, 將運算排在適當的步驟。而硬體配置是將物體(如運算、變數以及資料傳輸) 指定給特定的硬體 (如函數單元、暫存器及接線)。 最后, 根據排序后之資料流程圖與配置的資料路徑(data path),可以合成需要的控制單元。本論文主要探討硬體配置方面的問題, 是屬於清華大學電子設計自動化 (Tsing-Hua university Electronic Design Automation)計劃中高階合成系統的一部分。以往的資料路徑配置之研究, 大多採用逐步架構(constructive)之方法, 將之分為數個步驟, 配置記憶體單元同時把變數指定給暫存器, 配置函數單元同時將運算指定給函數單元, 最后再配置所需傳送資料的路徑, 這種一步步合成的設計通常不是最佳的設計。我們的資料路徑配置器, 則結合了逐步架構及反覆精煉(iterative refinement)的方法。首先, 前處理階段配置最佔體積之硬體資源(Area Dominant Resource), 之后在資料路徑架構階段則分成三個步驟: 資料傳輸結合(data transfer binding)、 運算元指派(operation assignment)及變數結合(variable binding), 每一個步驟均先將欲處理之物體如資料傳輸、運算元或變數分組成群集(cluster),再利用分支設限(br-anch and bound) 的方法架構出資料路徑。最后, 在反覆精煉階段再將資料路徑以總體(global)、反覆(iterative) 的方式來做進一步的改善, 每一次的精煉, 都經過如下之步驟: 評估每一個物體的binding quality,利用關係網路(relation network),隨機的選出一組相關的物體, 對其重新指派以得到一個更佳的設計。在此論文中, 我們分析了資料路徑配置的一些問題, 提出了若干定理及證明, 一些新的觀念, 如利用物體指派之相關性建立關係網路, 及評估物體binding quality 之方法等, 並提出一套整體資料路徑配置的演算法, 能在合理(reasonable)時間內得到極佳的結果。