On the intrinsic Rent parameter and spectra-based partitioning methodologies

The complexity of circuit designs requires a top-down approach to layout synthesis. A good partitioning hierarchy, as measured by the associated Rent parameter, will correspond to an area-efficient layout. The intrinsic Rent parameter of a netlist is defined as the minimum possible Rent parameter of any partitioning hierarchy for the netlist. Experimental results show that spectra-based ratio cut partitioning methods yield partitioning hierarchies with the lowest observed Rent parameter over all benchmarks and over all algorithms tested. For examples where the intrinsic Rent parameter is known, spectral ratio cut partitioning yields a Rent parameter essentially identical to this theoretical optimum. Additional theoretical results are provided to support the close relationship between spectral partitioning and the intrinsic Rent parameter