邏輯電路摺疊：由組合電路轉換至序向電路

Circuit Folding: From Combinational to Sequential Circuits

錢柏均(Po-Chun Chien)

指導教授 ： 江介宏

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2020年)

https://doi.org/10.6342/NTU202001058

摘要

在這篇論文中，我們制訂了時框展開（time-frame expansion）之逆操作──時框摺疊（time-frame folding）。 時框展開為一常用於自動測試圖樣產生及模型檢查之技術，它會將一序向邏輯電路展開成一組和邏輯電路；而時框摺疊則會進行反方向的操作，但由於每個時框下的分支電路都可能是不同的，因此它是一個相當複雜的技術。 時框摺疊可應用於測試平台生成及有界策略一般化的領域中。 我們提出的演算法可以找到一個最小的有限狀態機，有著與欲折疊的電路相同的輸入/輸出行為表現。 再者，我們將時框摺疊延伸為功能性電路摺疊，並另外提出了結構性電路折疊。 藉由上述兩個電路摺疊技術，我們可以於現場可程式化邏輯閘陣列（FPGA）中達到分時多工之效果，以解決FPGA中輸入及輸出接腳不足的瓶頸。 大多現有的研究是以實體設計的角度去解決此瓶頸，並設法藉由電路分割或繞線去減少切點網路之數量。 我們所提出的方法以不同的角度切入，並可以在帶寬及通量兩者間提供自由的取捨。 實驗的結果顯示出時框摺疊有著電路簡化的能力；同時也展現了結構性電路摺疊之效力及可拓展性，以及功能性電路摺疊之優化能力，幫助我們得到更少的查找表及正反器之電路形式。

關鍵字

邏輯電路摺疊 ； 函式分解 ； 接腳數簡化 ； 有限狀態自動機最小化 ； 時框展開 ； 時框摺疊 ； 分時多工

並列摘要

In the thesis, we formulate time-frame folding (TFF) as the reverse operation of timeframe expansion in automatic test pattern generation (ATPG) and (un)bounded model checking. While the latter converts a sequential circuit into a combinational one for some expansion bound of k time-frames, the former attempts the opposite, which can be highly non-trivial as the subcircuit of each time-frame can be distinct. TFF arises naturally in the context of testbench generation and bounded strategy generalization. We propose an algorithm that finds a minimum-state finite state machine consistent with the input-output behavior of the combinational circuit under folding. Furthermore, we extend TFF as functional circuit folding and introduce structural circuit folding. Through the two folding methods, we formulate a new approach at the logic level to achieve time multiplexing, which is an important technique to overcome the bandwidth bottleneck of limited input-output pins in FPGAs. Most prior work tackles the problem of time multiplexing from a physical design standpoint to minimize the number of cut nets or Time Division Multiplexing (TDM) ratio through circuit partitioning or routing. Our formulation is orthogonal to the previous ones and provides a smooth trade-off between bandwidth and throughput. Empirical evaluation of TFF demonstrates its ability in circuit size compaction. Experiments also show the effectiveness of the structural method and improved optimality of the functional method on look-up-table and flip-flop usage.

並列關鍵字

circuit folding ； functional decomposition ； pin-count reduction ； state minimization ； time-frame expansion ； time-frame folding ； time multiplexing

參考文獻

A. Abel and J. Reineke. MEMIN: SAT-based exact minimization of incompletely specified Mealy machines. In Proceedings of International Conference of Computer-Aided Design (ICCAD), pages 94–101, 2015.

D. Angluin. Learning regular sets from queries and counterexamples. Information and Computation, 75(2):87 – 106, 11 1987.

R. Ashenhurst. The Decomposition of Switching Functions, volume 29, pages 74–116. Computation Lab, Harvard University, 1959.

J. Babb, R. Tessier, and A. Agarwal. Virtual wires: Overcoming pin limitations in FPGA-based logic emulators. In Proceedings of IEEE Workshop on FPGAs for Custom Computing Machines, pages 142–151, 1993.

A. Biere, A. Cimatti, E. Clarke, and Y. Zhu. Symbolic model checking without BDDs. In Proceedings of International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pages 193–207, 1999.