Characterization and parameterized generation of digital circuits

grantor: University of TorontoThe development of new architectures for Field-Programmable Gate Arrays (FPGAs) and other forms of digital circuits, and the computer-aided design (CAD) software tools for these devices is greatly hampered by the lack of realistic test circuits or benchmarks that exercise them properly. Benchmarking is a crucial process in the design of CAD algorithms, as layout problems are typically NP-hard and heuristic algorithms are required. This thesis investigates combinatorial structure in digital circuits. We define and analyze a series of graph-theoretic properties of combinational and sequential circuits, including a theoretical characterization of reconvergent fanout and metrics to capture the inherent locality found in hand-made or synthesized circuits, and propose a new model for describing sequential and hierarchical circuits. By measuring these characteristics on public and proprietary industrial circuits, we determine a realistic profile of circuits. From our set of new characteristics, we define the new combinatorial problem of parameterized random circuit generation, advancing a new paradigm for benchmarking in computer-aided design. We then present a heuristic algorithm which solves it, fully implemented in a publicly available tool, scGEN. Heuristic methods can only be judged on their actual results, and a key feature of the research is the empirical validation of the generated circuits. We compare standard post-layout metrics for the circuits produced by scGEN with existing benchmark circuits and with random graphs, showing conclusively both that the generated circuits are very good proxies for real circuits and that random graphs are not.Ph.D