| Circuit partitioning underlies many important problems in VLSI circuit layout and circuit packaging. Recent advances in integrated circuit technology have significantly increased the complexity of circuit partitioning. For example, the new field programmable gate array (FPGA) technology introduces a new partitioning problem called technology mapping. The increasingly popular use of multiple FPGAs and the multiple-chip module chip-packaging technology require new multiple-chip partitioning algorithms. This dissertation presents algorithms in four areas of circuit partitioning: min-cut balanced partitioning, FPGA technology mapping, multiple-chip partitioning, and improving partitioning with gate replication. Our approaches to these problems are based on novel network flow formulations.; The well-known network flow technique is a natural method for finding min-cuts in graphs. However, it was overlooked as a viable approach for circuit partitioning mainly due to its high complexity. Efficient algorithms are given for modeling nets (or hyperedges) exactly by flow networks and for a repeated min-cut bipartition heuristic.; Interconnection delays usually account for a dominant portion of circuit delays. We use a general delay model that allows different delays for different interconnections even if they belong to the same net. An efficient technology mapping algorithm for lookup-table based FPGA designs that achieves provably optimal delays is presented.; Simultaneous area and pin constraints are necessary for multiple-chip implementations. We present a circuit clustering algorithm that minimizes circuit delay subject to both area and pin constraints on each chip.; Gate replication can reduce the number of cut edges substantially in a partitioned circuit. It is particularly useful for fully utilizing pin-limited devices such as multiple-FPGAs. We optimally solve the min-area min-cut replication problem on hypergraphs, which is to determine a replication set for each component such that the cut size of the partition is minimum and the total size of the replication sets is minimum.; All algorithms presented in this dissertation have been implemented, tested on large benchmark circuits, and compared with other well-known algorithms. Experimental results are given to illustrate the effectiveness and efficiency of the algorithms. |
