Sequence-pair based placement method for hard/soft/pre-placed modules

ABSTRACT

This paper proposes a placement method for a mixed set of hard, soft, and pre-placed modules, based on a placement topology representation called sequence-pair. Under one sequence-pair, a convex optimization problem is efficiently formulated and solved to optimize the aspect ratios of the soft modules. The method is used in two ways: i) directly applied in simulated annealing to present the most exact placement method, ii) applied as a post process in an approximate placement method for faster computation. The performance of these two methods are reported using MCNC benchmark examples.

REFERENCES

• 1: K. Wang and W.-K. Chen. Floorplan axes opt~mlzation using network analogous approach. In Proc. IEEE International Symposium on Circuits and Systemsj pages 167-170, 1995.
• 2: T.-S. Moll, T.-S. Chang, and S. L. Hakimi. Globally optimal floorplanning for a layout problem. IEEE Trans. on Circuit and Systems- I.- Fundamental Theory and Applications, 43(9):713-720, Sep 1996.
• 3: D. F. Wong , C. L. Liu, A new algorithm for floorplan design, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.101-107, July 1986, Las Vegas, Nevada, United States
• 4: Y. Lai and S. Leiwand. Algorithms for floorplan design via rectangular dualization. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 7(12):1278--1289, Dec 1988.
• 5: Shigetoshi Nakatake , Kunihiro Fujiyoshi , Hiroshi Murata , Yoji Kajitani, Module placement on BSG-structure and IC layout applications, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.484-491, November 10-14, 1996, San Jose, California, United States
• 6: Hiroshi Murata , Kunihiro Fujiyoshi , Shigetoshi Nakatake , Yoji Kajitani, Rectangle-packing-based module placement, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.472-479, November 05-09, 1995, San Jose, California, United States
• 7: H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani. VLSI module placement based on rectangle-packing by the sequence-pair. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 15(12):1518- 1524, Dec 1996.
• 8: M. Kang and W. Dai. General floorplanning with L- shaped, T-shaped and soft blocks based on bounded slicing grid structure. In Proc. Asia and South Pacific Design Automation Conf. 1997, pages 265-270, 1997.
• 9: H. Murata , K. Fujiyoshi , M. Kaneko, VLSI/PCB placement with obstacles based on sequence-pair, Proceedings of the 1997 international symposium on Physical design, p.26-31, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267675]
• 10: H. Marata, K. Fujiyoshi, T. Watanabe, and Y. Kajitani. A mapping from sequence-pair to rectangular dissection, in Proc. Asia and South Pacific Design Automation Conf. 1997, pages 625-633, 1997.
• 11: Pravin M. Vaidya, A new algorithm for minimizing convex functions over convex sets, Mathematical Programming: Series A and B, v.73 n.3, p.291-341, June 30, 1996 [doi>10.1007/BF02592216]
• 12: S. S. Sapatnekar, V. B. Rao, P. M. Vaidya, and S. M. Kang. An exact solution to the transistor sizing problem for CMOS circuits using convex optimization. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 12(11):1621-1634, Nov 1993.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout
  B.8 Performance and Reliability

General Terms:
Algorithms, Design, Performance, Theory