Circuit Folding: From Combinational to Sequential Circuits

This is my Master’s Thesis and is the extended research of the ICCAD 2019 paper and DAC 2020 paper.

Abstract:
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.

Click the links to view the thesis [PDF | Airiti lib], the source code and the slides.

To cite the thesis, you may use the following BibTex entry.

@mastersthesis{Chien:Thesis:2020,
    author  = {Po-Chun Chien},
    title   = {Circuit Folding: From Combinational to Sequential Circuits},
    school  = {National Taiwan University},
    year    = {2020},
    doi     = {10.6342/NTU202001058}
}