
RECTANGLE PACKING BASED PLACEMENTAbstractThe first and the most critical stage in VLSI physical design is placement, the background of which is the rectangle packing problem: Given a set of rectangular modules of arbitrary sizes, place them without overlap on a plane within a rectangle of minimum area. Since the variety of the packing is uncountably infinite, the key issue for discrete optimization is the introduction of a finite solution space which includes an optimal solution and excludes infeasible solutions. The main contribution of this work is in the introduction of such a solution space where each packing is represented by a pair of module name sequences, called sequencepair. Using the solution space, simulated annealing method is carried out with a conventional wiring estimation formula to solve building block placement problems. The biggest MCNC benchmark example ami49 is placed promisingly in about 30 minutes on a SunSS2. Relevant PapersH. Murata, K.Fujiyoshi, S.Nakatake, and Y.Kajitani, "VLSI Module Placement Based on RectanglePacking by the SequencePair" , IEEE Trans. on CAD, Vol. 15, No. 12, pp.15181524, Dec. 1996.

Contact 
©20022018 U.C. Regents 