Abstract
本篇論文主耍在研究一些技術之間的關係 － 分別應用在順序邏輯電路（ sequential logic circuit）中的重排時間（retiming）和周邊重排時間 （peripheral retiming），及高階合成（high-level synthesis）中的 導管法（pipelining）和迴圈折疊（loop folding）。本篇論文證明了迴 圈折疊（loop folding）的結果可由重排時間（retiming）及導管法( pipelining）的組合來達成，或用擴充重排時間（extensive retiming） 來達成；同樣地，周邊重排時間（peripheral retiming）的結果也可由 迴圈折疊（loop folding）或擴充重排時間（extensive retiming）的技 術來達成。這項發現將對順序邏輯電路（sequential logic circuit）及 高階合成（high-level synthesis）兩個領域的研究非常有幫助，我們便 利用這些技術之間的相關性發展了一個方法來最佳化邏輯電路的時間（ minimize the clock period of a sequential logic circuit）。我們 所提出的這個方法有兩項最主要的貢獻：１．提供原來重排時間（ retiming）的問題有更深入地了解，同時我們這個方法大大降低了重排時 間（retiming）的時間複雜度（time complexity）； ２．提供設計者更 大的設計空間來選擇最好的時間╱空間比例（area/speed tradeoff）。 我們將這個方法用Ｃ語言寫成程式，同時將它整合在由加州大學伯克箂分 校（U. C. Berkeley）所發展的系統ＳＩＳ底下，我們用這個方法實驗了 許多測試電路（benchmarks），實驗結果顯示：我們的方法不但非常有效 率－比傳統重排時間（retiming）的方法快１００倍以上；同時非常有實 用性－提供傳統重排時間（retiming）的方法以外更大的設計空間來選擇 最好的時間╱空間比例（area/speed tradeoff opportunity）。 The relationship between some techniques for sequential logic synthesis (i.e., retiming and peripheral retiming) and high- level synthesis (i.e., pipelining and loop folding) are studied in this paper. We prove that the problem of loop folding is equivalent to that of the combination of retiming and pipelining; the result of peripheral retiming can be accomplished by extensive retiming, or by loop folding. This discovery makes it possible to exchange the techniques developed previously for these two problems and, hence, cross- fertilize both areas. To show the usefulness of this discovery, we propose an algorithm, based on the relationship, for minimizing the clock period of sequential circuits. The proposed algorithm provides not only further insight into retiming but also a much greater area/speed design tradeoff opportunity compared with that of using retiming alone. The experimental results on a set of benchmarks indicate that the proposed algorithm is 2-order faster than Saxe's relaxation algorithm implemented in the SIS package.