| Circuit partitioning divides a given circuit into a collection of smaller subcircuits while satisfying the given area and/or pin constraints. In order to keep up with the rapid increase of system complexity due to substantial advances in VLSI process technology, partitioning is performed at various level of design hierarchy until subproblems become more manageable.;The conventional objective of partitioning is to minimize the interconnect among the partitioned circuits. On the other hand, under the new interconnect-centric design paradigm, partitioning is seen as the crucial step that defines the local and global interconnects [Con99]. To meet the performance requirement of today's complex design, performance driven partitioners must consider the amount of interconnect induced by partitioning (measured by its cutsize) as well as its impact on performance (measured by its delay). Many proposed cutsize driven partitioners do not consider delay, while many proposed delay driven partitioners do not consider cutsize. As a result, there is a strong need for a performance driven partitioner that considers both cutsize and delay and provides smooth cutsize/delay tradeoff.;This dissertation studies the performance driven circuit partitioning problem under the objective of simultaneous cutsize and delay minimization. Our focus is first to identify and analyze the limitation of current state-of-the-art in cutsize driven and delay driven partitioners, and then to develop efficient, effective, and scalable solutions for simultaneous cutsize and delay minimization for today's large scale circuits. Our proposed solutions include (i) modified iterative improvement methods [CLL+97, CL98, WLCS00, CL00c], (ii) multi-level methods [CL00a, CLW00], and (iii) geometric embedding method [CL00b]. |
