Recent research presents a technique to enumerate all valid assignments of “twiddle factors” for power-of-two fast Fourier transform (FFT) flow graphs. Brute-force search employing state-of-the-art Boolean satisfiability (SAT) solvers can then be used to find FFT algorithms within this large solution space which have desirable characteristics. Surprisingly, this approach has discovered FFT algorithms requiring fewer operations than the split-radix algorithm even when all twiddle factors are nthroots of unity. This paper reviews and then extends this prior research to examine fast discrete convolution algorithms when implemented via FFT and inverse FFT (IFFT) algorithms. In particular, we find that the combination of FFT and IFFT algorithms in fast convolution permits greater freedom when selecting valid twiddle factor assignments. We exploit this freedom and use SAT solvers to find new fast convolution algorithms with the lowest operation counts known.

This paper presents a new tool for SystemVerilog RTL modifications with on-the-fly validation of local RTL changes. The tool, SV-rewrite, imports an initial version of SystemVerilog RTL and elaborates it into a hierarchical design description visualized as structural diagrams. From the design cockpit the user can select any set of visualized components, open a favorite text editor, modify then validate the new RTL description, and finally substitute this new rewritten RTL into the larger model to replace the originally selected components. This process of local validated rewrites can be repeated until the entire RTL is safely rewritten. We studied RTL abstraction using SV-rewrite to abstract the Pentium 80602 (P54CS) integer execution unit and register file. We have produced a significantly more readable RTL that is 2 to 3 times smaller than the original one. The abstracted RTL was validated by booting Linux on an FPGA-based emulation platform.

We describe a set of techniques for representing the high-level behavior of a digital subsystem as a collection of nondeterministic finite automata, NFA. Desired behavioral dynamics such as functional dependencies, sequential timing, and sequencing, and control state are similarly modeled. Using techniques similar to that used in formal model checking, we implicitly explore the possible execution sequences of the system, obeying all imposed constraints. This provides a very general, systematic mechanism for performing high-level synthesis of cyclic, control dominated behaviors, constrained by arbitrary sequential constraints. In this paper, we show that these techniques are scalable to practical problem sizes and complexities by constructing a high-level model of a (MIPS IV) RISC microprocessor and then performing exact scheduling and related design tradeoffs on this model. The model is constructed at the level of register transactions to address the majority of contention and arbitration issues of architectural interest.

This paper presents an exact technique for scheduling looping data-flow graphs that implicitly supports functional pipelining and loop winding. Automata-based symbolic modeling provides efficient representation of all causal executions of a given behavioral description subject to finite state bounds. Since a complete set of scheduling solutions is found, further incremental refinements, such as sequential interface protocol constraints, can be easily accommodated. Efficiency In the implementation Is maintained by careful formulation of the automata and by judicious exploration techniques. Results are presented for traditionally referenced benchmarks, several large synthetic benchmarks, and a practical industrial example.

This paper presents a very general, exact technique for scheduling looping data-flow graphs. In contrast to the conventional technique using loop iteration variables and integer linear programming, the new technique uses implicit symbolic automata techniques to represent the problem instance. The new technique has several advantages, such as incremental refinement, efficient variable usage and ability to accommodate practical design constraints. A small case study demonstrates the flexibility and viability of this technique.

This paper presents a technique for highly constrained event sequence scheduling. System resource protocols as well as an external interface protocol are described by non-deterministic finite automata (NFA). All valid schedules which adhere to interfacing constraints and resource bounds for flow graph described behavior are determined exactly. A model and scheduling results are presented for an extensive design example.

This paper presents an efficient encoding and automaton construction which improves performance of automata-based scheduling techniques. The encoding preserves knowledge of what operations occurred previously but excludes when they occurred, allowing greater sharing among scheduling traces. The technique inherits all of the features of BDD-based control dominated scheduling including systematic speculation. Without conventional pruning, all schedules for several large samples are quickly constructed.