Abstract
資料路徑合成(Data Path Synthesis) 是高階合成(High Level Synthesis)中的一個最重要的工作。一般資料路徑合成可分成二個子工作：一為排序(Scheduling), 另一個為配置(Allocation)。排序決定每一個運算(Operation) 要在那一個控制步驟(Control-step)執行，而配置決定每一個運算要由那一個運算元件(Function unit) 來執行。排序問題更可細分為時限(Time-constrained)排序與資源限制(Time-constrained)排序。至於資料路徑合成的目的則在提高資料路徑的執行速度與降低其硬體成本。在本篇論文中，我們提出一組於時限排序問題的演算法。力導向排序(Force-directed Scheduling) 法只是我的方法的一個成員。我的排序方法首先用儘早排序(ASAP Scheduling) 與儘遲排序(ALAP Scheduling) 產生初始的部分排序，然後逐次的利用我所定義的動作(Action)去減少某個運算在排序上的可移度(Mobility), 一直到所有運岸被排好為止。由於每次要減少可移度的運算可能不只一個，所以須要靠成本函數(Cost Function) 來決定如何挑其中的一個，我所提供的成本函數考慮每個運算的危疾度(Critical)，和估計每一個排序要花費的硬體成本與分布圖(Distribution Graph)的均勻程度。除了上述的方法，我還提出如何利用分化與征服(Divide-and-conquer)減少排序所用的時間,并利用一新的精煉演算法來提高分化與征服法所產生結果的品質。所有我所提出來的方法都在SUN 公司的SPARC 電腦上完成程度的寫作與測試無誤。我用了五個例子來測試我的程式的品質。這五個例子由我的程式排序後都有不錯的結果，甚致勝過力導向排序法。而且分化與征服法只要花非常短的時間就可排出不錯的結果。