A timing-driven multi-way partitioning system for integrated circuits and multichip systems

This dissertation presents partitioning algorithms to enable an automatic layout package to (1) divide and conquer the physical design process of complex circuits such as FPGA circuits or mixed macro/standard cell circuits and (2) physically partition a circuit onto multiple chips for a given multi-chip package or board. We propose a complete partitioning system consisting of a netlist clustering algorithm, a timing driven multi-way rectilinear partitioning algorithm, and a pin assignment algorithm.; Our new rectilinear partitioning algorithm is implemented using simulated annealing which allows the incorporation of distance and signal path timing constraints. The new linear time netlist clustering algorithm obtained significant reduction in the complexity of large circuits which resulted in significant improvement of the run time for our new rectilinear partitioning algorithm. We have introduced complete timing delay models which we use to satisfy the timing requirements for single chip and multichip partitioning for multiple technologies.; We have improved the placement results of an industrial FPGA architecture by using the partitioner for global placement before detailed placement. The average improvement was 90% over the only available industrial placement tool. For several industrial circuits, our MCM partitioning approach has outperformed the recursive mincut bi-partitioning algorithm by 34% in nets cut and an industrial FPGA partitioner by 73% in terms of unrouted nets on average. In comparison to the only other multiple FPGA partitioning approach which was applied to the Xilinx mapped MCNC benchmarks, we produced partitioned results with 7.5% lower total dollar cost.; Using the performance optimization capabilities in our approach we have successfully partitioned the MCNC Xilinx FPGA benchmarks satisfying the critical path constraints and achieving a significant reduction in the longest path delay. An average reduction of 17% in the longest path delay was achieved at the cost of 5% increase in total wire length and 17% increase in nets cut.