Constructive logic and layout synthesis.

This dissertation examines the extension of constructive library-aware logic synthesis to the physical placement stage of integrated circuit design. Constructive logic synthesis differs from traditional synthesis approaches in that it builds a circuit netlist incrementally starting from the primary inputs and proceeding towards the primary outputs. In each iteration of this procedure, the semantic structure of the unsynthesized logic functions is utilized to identify and extract a small subcircuit that consists of library primitives reflecting that structure. In particular, functional symmetry is used to obtain support-reducing decompositions that lead to high-quality implementations in terms of both area and delay. Effectively, the algorithm interleaves the steps of technology-independent decomposition and technology-dependent mapping into library cells in a way that mitigates its greedy nature. Conjecturing that the addition of a placement step to this methodology would further improve synthesis quality we developed the COLOSSEUM system which synthesizes circuits by incremental decomposition, mapping, and placement. We describe the algorithms used in COLOSSEUM and analyze the quality of the designs it generates under a variety of options for decomposition and placement. The empirical results we obtained, however, suggest that adding a placement step to constructive synthesis produces no noticeable improvement in design quality. This strongly suggests that our original conjecture is false, and we examine possible reasons for such a negative result.Ph.D.Applied SciencesComputer scienceUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/126529/2/3253374.pd