ON THE INTRINSIC RENT PARAMETER AND SPECTRA-BASED PARTITIONING METHODOLOGIES

The complexity of circuit designs has necessitated a top-down approach to layout synthesis. A large body of work shows that a good layout hi erarchy, or partitioning tree, as measured by the associated Rent para meter, will correspond to an area-efficient layout. We define the intr insic Rent parameter of a netlist to be the minimum possible Rent para meter of any partitioning tree for the netlist. Experimental results s how that spectra-based ratio cut partitioning algorithms yield partiti oning trees with the lowest observed Rent parameter over all benchmark s and over all algorithms tested. For examples where the intrinsic Ren t parameter is known, spectral ratio cut partitioning yields a partiti oning tree with Rent parameter essentially identical to this theoretic al optimum. These results have deep implications with respect to both the choice of partitioning algorithms for top-down layout, as well as new approaches to layout area estimation. The paper concludes with dir ections for future research, including several promising techniques fo r fast estimation of the (intrinsic) Rent parameter.