The network partition problem belongs to the class of constrained discrete optimization problems with black-box objective functions and has application in VLSI design. Application of TRUST-TECH has achieved the best results.
A VLSI system is partitioned at several levels due to its complexity: (1) system level partitioning, in which a system is partitioned into a set of sub-systems whereby each sub-system can be designed and fabricated independently on a single PCB; (2) board level partitioning where a PCB is partitioned into VLSI chips; (3) chip level partitioning where a chip is divided into smaller sub-circuits. At each level, the constraints and objectives of the partitioning are different. Partition is also referred to as a cut.
One popular objective function of partition is to minimize the interconnections between partitions, called the cut-set, which is the number of hyperedges crossing the cut. Reducing the interconnections not only reduces the delay but also reduces the interface between the partitions making it easier for independent design and fabrication. A large number of interconnections increase the design area as well as complicating the task of the placement and routing algorithms.
By incorporating the TRUST-TECH-based method with the traditional FM method, the quality of the solution is significantly improved. The improvements range from 9.5% to 268%, where it achieve significant improvements on large circuits and noticeable improvements on small circuits.