Handling complexities in modern large-scale mixed-size placement

ABSTRACT

In this paper, we propose an effective algorithm flow to handle large-scale mixed-size placement. The basic idea is to use floorplanning to guide the placement of objects at the global level. The flow consists of four steps: 1) The objects in the original netlist are clustered into blocks; 2) Floorplanning is performed on the blocks; 3) The blocks are shifted within the chip region to further optimize the wirelength; 4) With big macro locations fixed, incremental placement is applied to place the remaining objects. There are several advantages of handling placement at the global level with a floorplanning technique. First, the problem size can be significantly reduced. Second, exact HPWL can be minimized. Third, precise object distribution can be achieved so that legalization only needs to handle minor overlaps among small objects in a block. Fourth, rotation and various placement constraints on macros can be handled. To demonstrate the effectiveness of this new flow, we implement a high-quality floorplan-guided placer called FLOP. We also construct the Modern Mixed-Size (MMS) placement benchmarks which can effectively represent the complexities of modern mixed-size designs and the challenges faced by modern mixed-size placers. Compared with state-of-the-art mixed-size placers and leading macro placers, experimental results show that FLOP achieves the best wirelength, and easily obtains legal solutions on all circuits.

REFERENCES

• 1: T. Taghavi, X. Yang, B.-K. Choi, M. Yang, and M. Sarrafzadeh. Dragon2006: Blockage-aware congestion-controlling mixed-size placer. In Proc. ISPD, pages 209--211, 2006.
• 2: J. A. Roy, S. N. Adya, D. A. Papa, and I. L. Markov. Min-cut floorplacement. IEEE Trans. on Computer-Aided Design, 25(7):1313--1326, July 2006.
• 3: N. Viswanathan, M. Pan, and C. Chu. Fastplace 3.0: A fast multilevel quadratic placement algorithm with placement congestion control. In Proc. ASP-DAC, pages 135--140, 2007.
• 4: A. B. Kahng and Q. Wang. A faster implementation of A Place. In Proc. ISPD, pages 218--220, 2006.
• 5: P. Spindler and F. M. Johannes. Fast and robust quadratic placement combined with an exact linear net model. In Proc. ICCAD, pages 179--186, 2006.
• 6: T. Chan, J. Cong, J. Shinnerl, K. Sze, and M. Xie. mPL6: Enhanced multilevel mixed-sized placement. In Proc. ISPD, pages 212--214, 2006.
• 7: T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang. A high-quality mixed-size analytical placer considering preplaced blocks and density constraints. In Proc. ICCAD, pages 187--192, 2006.
• 8: T.-C. Chen, P.-H. Yuh, Y.-W. Chang, F.-J. Huang, and D. Liu. MP-tree: A packing-based macro placement algorithm for mixed-size designs. In Proc. DAC, pages 447--452, 2007.
• 9: H.-C. Chen, Y.-L. Chuang, Y.-W. Chang, and Y.-C. Chang. Constraint graph-based macro placement for modern mixed-size circuit designs. In Proc. ICCAD, pages 218--223, 2008.
• 10: S. Adya and I. Markov. Consistent placement of macro-blocks using floorplanning and standard-cell placement. In Proc. ISPD, pages 12--17, 2002.
• 11: J. Z. Yan and C. Chu. DeFer: Deferred decision making enabled fixed-outline floorplanner. In Proc. DAC, pages 161--166, 2008.
• 12: T.-C. Chen, Y.-W. Chang, and S.-C. Lin. IMF: Interconnect-driven multilevel floorplanning for large-scale building-module designs. In Proc. ICCAD, pages 159--164, 2005.
• 13: X. Tang, R. Tian, and M. D. F. Wong. Minimizing wire length in floorplanning. IEEE Trans. on Computer-Aided Design, 25(9):1744--1753, September 2006.
• 14: P.-N. Guo, C.-K. Cheng, and T. Yoshimura. An O-tree representation of non-slicing floorplan and its applications. In Proc. DAC, pages 268--273, 1999.
• 15: G.-J. Nam, S. Reda, C. J. Alpert, P. G. Villarrubia, and A. B. Kahng. A fast hierarchical quadratic placement algorithm. IEEE Trans. on Computer-Aided Design, 25(4):678--691, April 2006.
• 16: M. Pan, N. Viswanathan, and C. Chu. An efficient and effective detailed placement algorithm. In Proc. ICCAD, pages 48--55, 2005.
• 17: S. Adya, S. Chaturvedi, J. Roy, D. Papa, and I. Markov. Unification of partitioning, placement and floorplanning. In Proc. ICCAD, pages 550--557, 2004.
• 18: G.-J. Nam, C. J. Alpert, P. Villarrubia, B. Winter, and M. Yildiz. The ISPD2005 placement contest and benchmarks suite. In Proc. ISPD, pages 216--220, 2005.
• 19: G.-J. Nam. ISPD 2006 placement contest: Benchmark suite and results. In Proc. ISPD, pages 167--167, 2006.
• 20: MMS Placement Benchmarks. http://www.public.iastate.edu/~zijunyan/.
• 21: hMetis2.0. http://glaros.dtc.umn.edu/gkhome/.
• 22: QSopt LP Solver. http://www.isye.gatech.edu/~wcook/qsopt/.
• 23: J. Cong and M. Xie. A robust detailed placement for mixed-size ic designs. In Proc. ASP-DAC, pages 188--194, 2006.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design, Performance

Keywords:
floorplanning, incremental placement, mixed-size design