Parallel algorithms for logic synthesis

The size of the VLSI circuit is increasing at a very rapid pace, and soon the sequential algorithms running on a uniprocessor will be inadequate to handle such large circuits. Parallel processing can be used to reduce the computation time considerably with almost no degradation in the quality. Most of the parallel algorithms developed for VLSI CAD applications, however, are designed for one specific parallel architecture. As a result, considerable effort and expense are needed to port them to different parallel machines. The ongoing ProperCAD project at the University of Illinois offers a bright solution to that problem by allowing the user to develop parallel algorithms on the top of a portable framework such that the programs developed will run unchanged on a variety of parallel machines, both shared and distributed memory machines. In this thesis, parallel algorithms for combinational logic synthesis using two approaches are developed: (1) the Transduction method, which uses the concept of a set of permissible functions to perform various logic transformations to reduce the size of logic circuit, and (2) the MIS approach, which uses algebraic factoring and node simplification for the purpose of logic minimization. The parallel algorithms developed in this thesis offer three major contributions. First, the parallel algorithms use an asynchronous, message-driven computing model with no synchronizing barriers separating phases of parallel computation. Second, these algorithms are portable across a wide variety of parallel architectures, shared memory machines such as Encore Multimax and Sequent Symmetry, distributed memory machines such as Intel/860, and networks of workstations. Finally, these algorithms are built around well defined sequential algorithm interfaces, so that the parallel algorithms can benefit from the future improvements and expansions of the sequential algorithms. Very large circuits, however, can not he handled as a whole by any synthesis algorithm. Those circuits are partitioned, and then the partitions are synthesized independently in parallel. A parallel synthesis system based on the partitioning approach is also described in this thesis.U of I OnlyETDs are only available to UIUC Users without author permissio