Constructive Logic and Layout Synthesis

This book examines the extension of constructive library-aware logic synthesis to he 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 consisting of library primitives. 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.