Abstract
資料路徑合成（Data Path Synthesis ）一般可分為兩個子問題，即為資料路徑排程問題（Scheduling）及配置問題（Allocation）。資料路徑排程問題的目標是把運算動成（Operation ）排到適當的控制週期（control step）中，並且將使用的運算元件成本極小化。配置問題則是配置資料路徑中所須的運算元件，暫存器，多工器及連結線路。資料路徑的排程問題決定資料路徑成本及執行速度的權衡。一旦所有的運算動作排好後，所須運算元件的個數及型別，變數的生命週期（對暫存器的配置有直接的影響）及時脈限制…等都會被固定下來，所以一個優良的排程器是極為重要的。在本篇論文中，我們提出了一個新的方法來解決資料路徑的排程問題。它包括有三部份：儘早排程法（ASAP Scheduling ），儘遲排程法（ALAP Scgeduling ）及一個整數線性規劃模式（ILP formulation ）。在給定的控制週期數下，透過儘早排程法及儘遲排程法能得到每個運算動作的可移動程度（mobility），再據以建立一適當的整數線性規劃模式，該模式的解即對應一個有最小運算元件成本的排程。此整數線性規劃模式在稍加修改後尚能處理多重週期運算動作（Multicycle Operat-ions），一個控制週期包含多重運算動作（Multiple Operations per Cycle ），管線式資料路徑（Pipelined Data Path ），互斥運算動作（Mutually Exclusive Op-ertions ）及變數生命週期考慮（Variables' Lifetime Consideration ）的一般情況。此模式中的變數及限制式個數是可接受的，並經實驗而知資料路徑排程問題可運用此模式有效而快速的解決。一個包含２６個加法運算動作和８個乘法運算動作的濾波器，在VAX ８８００上從１７到２１個控制週期均可在１５秒內得到最佳排程。對於所有測試的例子，我們提出的這個模式都能在極短時間內得到最佳解，亦即最小運算元件成本的排程。