Timing-driven placement based on monotone cell ordering constraints

ABSTRACT

In this paper, we present a new timing-driven placement algorithm, which attempts to minimize zigzags and crisscrosses on the timing-critical paths of a circuit. We observed that most of the paths that cause timing problems in the circuit meander outside the minimum bounding box of the start and end nodes of the path. To limit this undesirable behavior, we impose a physical constraint on the placement problem, i.e., we assign a preferred signal direction to each critical path in the circuit. Starting from an initial placement solution, by using a move-based optimization strategy, these preferred directions force cells to move in a direction that maximizes the monotonic behavior of the timing-critical paths in the new placement solution. To make the direction assignment tractable, we implicitly group all circuit paths into a set of input-output conduits and assign a unique preferred direction to each such conduit. We integrated this idea into a recursive bipartitioning-based placement framework with a min-cut objective function. Experimental results on a set of standard placement benchmarks show that-this approach improves the result of a state-of-the-art industrial placement tool for all the benchmark circuits while increasing the wire length by a tolerable amount.

REFERENCES

• 1: Jason Cong , Xin Yuan, Multilevel global placement with retiming, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775887]
• 2: Miloš Hrkić , Miloš Hrkić , John Lillis , Giancarlo Beraudo, An approach to placement-coupled logic replication, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996761]
• 3: Prashant Saxena , Bill Halpin, Modeling repeaters explicitly within analytical placement, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996759]
• 4: Giancarlo Beraudo , John Lillis, Timing optimization of FPGA placements by logic replication, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775885]
• 5: Xiaojian Yang , Bo-Kyung Choi , Majid Sarrafzadeh, Timing-driven placement using design hierarchy guided constraint generation, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.177-180, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774598]
• 6: Karthik Rajagopal , Tal Shaked , Yegna Parasuram , Tung Cao , Amit Chowdhary , Bill Halpin, Timing driven force directed placement with physical net constraints, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640016]
• 7: Jason Cong , Sung Kyu Lim, Performance driven multiway partitioning, Proceedings of the 2000 conference on Asia South Pacific design automation, p.441-446, January 2000, Yokohama, Japan [doi>10.1145/368434.368736]
• 8: Andrew B. Kahng , Xu Xu, Local unidirectional bias for smooth cutsize-delay tradeoff in performance-driven bipartitioning, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640019]
• 9: Andrew B. Kahng , Stefanus Mantik , Igor L. Markov, Min-max placement for large-scale timing optimization, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505423]
• 10: Wonjoon Choi , Kia Bazargan, Incremental Placement for Timing Optimization, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.463, November 09-13, 2003 [doi>10.1109/ICCAD.2003.84]
• 11: Bill Halpin , C. Y. Roger Chen , Naresh Sehgal, Timing driven placement using physical net constraints, Proceedings of the 38th conference on Design automation, p.780-783, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379065]
• 12: Sung-Woo Hur , Tung Cao , Karthik Rajagopal , Yegna Parasuram , Amit Chowdhary , Vladimir Tiourin , Bill Halpin, Force directed mongrel with physical net constraints, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775888]
• 13: Wilsin Gosti , Amit Narayan , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Wireplanning in logic synthesis, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.26-33, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288556]
• 14: Cristinel Ababei , Navaratnasothie Selvakkumaran , Kia Bazargan , George Karypis, Multi-objective circuit partitioning for cutsize and path-based delay minimization, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.181-185, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774599]
• 15: Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Can recursive bisection alone produce routable placements?, Proceedings of the 37th conference on Design automation, p.477-482, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337549]
• 16: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 17: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual conference on Design automation, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
• 18: Natarajan Viswanathan , Chris Chong-Nuen Chu, FastPlace: efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981072]
• 19: Yih-Chih Chou , Youn-Long Lin, A performance-driven standard-cell placer based on a modified force-directed algorithm, Proceedings of the 2001 international symposium on Physical design, p.24-29, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369722]
• 20: S. Iman, M. Pedram, C. Fabian, and J. Cong, "Finding unidirectional cuts based on physical partitioning and logic restructuring", In Proceedings of the 4th ACM/IEEE Physical Design Workshop, 187--198, 1993.
• 21: Chanseok Hwang , Massoud Pedram, PMP: performance-driven multilevel partitioning by aggregating the preferred signal directions of I/O conduits, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120903]
• 22: Andrew B. Kahng , Igor L. Markov , Sherief Reda, Boosting: Min-Cut Placement with Improved Signal Delay, Proceedings of the conference on Design, automation and test in Europe, p.21098, February 16-20, 2004

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids
  B.m MISCELLANEOUS
      Subjects: Design management

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Design, Performance