Parallelizing CAD: a timely research agenda for EDA

ABSTRACT

The relative decline of single-threaded processor performance, coupled with the ongoing shift towards on chip parallelism requires that CAD applications run efficiently on parallel microprocessors. We believe that an ad hoc approach to parallelizing CAD applications will not lead to satisfactory results: neither in terms of return on engineering investment nor in terms of the computational efficiency of end applications. Instead, we propose that a key area of CAD research is to identify the design patterns underlying CAD applications and then build CAD application frameworks that aid efficient parallel software implementations of these design patterns. Our initial results indicate that parallel patterns exist in a broad range of CAD problems. We believe that frameworks for these patterns will enable CAD to successfully capitalize on increased processor performance through parallelism.

REFERENCES

• 1: C. Alexander et al. A Pattern Language: Towns, Buildings, Construction. Oxford University Press, USA, 1977.
• 2: K. Asanovic et al. The landscape of parallel computing research: a view from Berkeley. Technical report, Electrical Engineering and Computer Sciences, University of California at Berkeley, 2006.
• 3: K. Asanovic et al. The landscape of parallel computing research: a view from Berkeley 2.0. Technical report, Electrical Engineering and Computer Sciences, University of California at Berkeley, 2007.
• 4: Zhen Cao , Tong Jing , Jinjun Xiong , Yu Hu , Lei He , Xianlong Hong, DpRouter: A Fast and Accurate Dynamic-Pattern-Based Global Routing Algorithm, Proceedings of the 2007 conference on Asia South Pacific design automation, p.256-261, January 23-26, 2007 [doi>10.1109/ASPDAC.2007.357995]
• 5: Tony F. Chan , Jason Cong , Michalis Romesis , Joseph R. Shinnerl , Kenton Sze , Min Xie, mPL6: a robust multilevel mixed-size placement engine, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055185]
• 6: Tung-Chieh Chen , Yao-Wen Chang , Shyh-Chang Lin, IMF: interconnect-driven multilevel floorplanning for large-scale building-module designs, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.159-164, November 06-10, 2005, San Jose, CA
• 7: Tung-Chieh Chen , Zhe-Wei Jiang , Tien-Chang Hsu , Hsin-Chen Chen , Yao-Wen Chang, A high-quality mixed-size analytical placer considering preplaced blocks and density constraints, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233538]
• 8: Minsik Cho , Katrina Lu , Kun Yuan , David Z. Pan, BoxRouter 2.0: architecture and implementation of a hybrid and robust global router, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 9: Chris Chu , Yiu-Chung Wong, Fast and accurate rectilinear steiner minimal tree algorithm for VLSI design, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055145]
• 10: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 11: David Garlan , Mary Shaw, An Introduction to Software Architecture, Carnegie Mellon University, Pittsburgh, PA, 1994
• 12: Andrew B. Kahng , Qinke Wang, A faster implementation of APlace, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123057]
• 13: M. Kleinhans et al. VLSI placement by quadratic programming and slicing optimization. IEEE Trans. on CAD, 10(3): 356--365, 1991.
• 14: Jai-Ming Lin , Yao-Wen Chang, TCG-S: orthogonal coupling of P*-admissible representations for general floorplans, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514127]
• 15: S. MacDonald , J. Anvik , S. Bromling , J. Schaeffer , D. Szafron , K. Tan, From patterns to frameworks to parallel programs, Parallel Computing, v.28 n.12, p.1663-1683, December 2002 [doi>10.1016/S0167-8191(02)00190-4]
• 16: T. G. Mattson, B. A. Sanders, and B. L. Massingill. Patterns for Parallel Programming. Addison-Wesley Professional, USA, 2004.
• 17: Aaron N. Ng , Igor L. Markov , Rajat Aggarwal , Venky Ramachandran, Solving hard instances of floorplacement, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123047]
• 18: Min Pan , C. Chu, FastRoute 2.0: A High-quality and Efficient Global Router, Proceedings of the 2007 conference on Asia South Pacific design automation, p.250-255, January 23-26, 2007 [doi>10.1109/ASPDAC.2007.357994]
• 19: Peter Spindler , Frank M. Johannes, Fast and robust quadratic placement combined with an exact linear net model, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233537]
• 20: Taraneh Taghavi , Xiaojian Yang , Bo-Kyung choi , Maogang Wang , Majid Sarrafzadeh, Dragon2006: blockage-aware congestion-controlling mixed-size placer, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123054]
• 21: Natarajan Viswanathan , Gi-Joon Nam , Charles J. Alpert , Paul Villarrubia , Haoxing Ren , Chris Chu, RQL: global placement via relaxed quadratic spreading and linearization, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278599]
• 22: N. Viswanathan , Min Pan , C. Chu, FastPlace 3.0: A Fast Multilevel Quadratic Placement Algorithm with Placement Congestion Control, Proceedings of the 2007 conference on Asia South Pacific design automation, p.135-140, January 23-26, 2007 [doi>10.1109/ASPDAC.2007.357975]
• 23: H. Murata et al. VLSI Module Placement Based on Rectangle-Packing by the Sequence Pair, IEEE Trans. on CAD 15(12), pp. 1518--1524, 1996.
• 24: Jason Cong , Jie Fang , Kei-Yong Khoo, DUNE: a multi-layer gridless routing system with wire planning, Proceedings of the 2000 international symposium on Physical design, p.12-18, May 2000, San Diego, California, United States [doi>10.1145/332357.332367]
• 25: E. Carlson, R. Rutenbar. A Scanline Data Structure Processor for VLSI Geometry Checking, IEEE Trans. on CAD 6(5), pp. 780--794, September 1987
• 26: Joydeep Mitra , Peng Yu , David Z. Pan, RADAR: RET-aware detailed routing using fast lithography simulations, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065678]
• 27: C. Chiang , A. B. Kahng , S. Sinha , X. Xu, Fast and efficient phase conflict detection and correction in standard-cell layouts, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.149-156, November 06-10, 2005, San Jose, CA
• 28: Nikhil Saluja , Sunil P. Khatri, A robust algorithm for approximate compatible observability don't care (CODC) computation, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996688]
• 29: C. Leiserson and J. Saxe. Retiming Synchronous Circuitry, Algorithmica, vol. 6, pp. 5--35, 1991.
• 30: K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37940]
• 31: E. Lehman et al. Logic decomposition during technology mapping, IEEE Trans. on CAD 16(8): 813--834, 1997.
• 32: Anand Ramalingam , Gi-Joon Nam , Ashish Kumar Singh , Michael Orshansky , Sani R. Nassif , David Z. Pan, An accurate sparse matrix based framework for statistical static timing analysis, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233547]
• 33: S. Devadas, et al. Computation of floating mode delay in combinational circuits: practice and implementation, IEEE Trans. on CAD 12(12): 1924--1936, 1993.
• 34: N. Shenoy , R. K. Brayton , A. L. Sangiovanni-Vincentelli, Graph algorithms for clock schedule optimization, 1992 IEEE/ACM international conference proceedings on Computer-aided design, p.132-136, December 1992, Santa Clara, California, United States
• 35: Prabhakar Goel , Barry C. Rosales, PODEM-X: An automatic test generation system for VLSI logic structures, Proceedings of the 18th conference on Design automation, p.260-268, June 29-July 01, 1981, Nashville, Tennessee, United States
• 36: H. Fujiwara. FAN: A Fanout-Oriented Test Pattern Generation Algorithm, Proc. Int'l Symp. Circuits and Systems, pp. 671--674, 1985.
• 37: Szu-Tsung Cheng , R. K. Brayton, Synthesizing multi-phase HDL programs, Proceedings of the 1996 IEEE International Verilog HDL Conference (IVC '96), p.67, March 26-28, 1996
• 38: S. Devadas, K. Keutzer, S. Malik, Delay computation in combinational logic circuits: theory and algorithms, ICCAD '91, pp. 176--179, 1991.
• 39: E. Goldberg , M. Prasad , R. Brayton, Using SAT for combinational equivalence checking, Proceedings of the conference on Design, automation and test in Europe, p.114-121, March 2001, Munich, Germany
• 40: S. Malik et al. Logic Verification Using Binary-Decision Diagrams in a Logic Synthesis Environment. ICCAD '88, pp. 6--9, 1988.
• 41: Alessandro Cimatti , Edmund M. Clarke , Enrico Giunchiglia , Fausto Giunchiglia , Marco Pistore , Marco Roveri , Roberto Sebastiani , Armando Tacchella, NuSMV 2: An OpenSource Tool for Symbolic Model Checking, Proceedings of the 14th International Conference on Computer Aided Verification, p.359-364, July 27-31, 2002
• 42: Alferd Kölbl , James Kukula , Robert Damiano, Symbolic RTL simulation, Proceedings of the 38th conference on Design automation, p.47-52, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378278]
• 43: L. Nagel. SPICE2: A Computer Program to Simulate Semiconductor Circuits, Memorandum No. ERL-M520, University of California, Berkeley, May 1975.
• 44: Shweta Srivastava , Jaijeet Roychowdhury, Interdependent latch setup/hold time characterization via Euler-Newton curve tracing on state-transition equations, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278515]
• 45: Alan Mishchenko , Satrajit Chatterjee , Robert Brayton, DAG-aware AIG rewriting a fresh look at combinational logic synthesis, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147048]
• 46: Robert King Brayton , Alberto L. Sangiovanni-Vincentelli , Curtis T. McMullen , Gary D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1984
• 47: Tung-Chieh Chen , Yao-Wen Chang, Modern floorplanning based on fast simulated annealing, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055161]
• 48: 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
• 49: M. Hsueh. Symbolic layout and compaction, PhD Thesis, University of California, Berkeley, 1980.
• 50: T. Larrabee. Test pattern generation using Boolean satisfiability, IEEE TCAD, 11, 1, pp. 4--15, 1992.
• 51: Venkatram Krishnaswamy , Prithviraj Banerjee, Actor based parallel VHDL simulation using time warp, Proceedings of the tenth workshop on Parallel and distributed simulation, p.135-142, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 52: Andries Stam, A Framework for Coordinating Parallel Branch and Bound Algorithms, Proceedings of the 5th International Conference on Coordination Models and Languages, p.332-339, April 08-11, 2002
• 53: Wen-mei Hwu , Shane Ryoo , Sain-Zee Ueng , John H. Kelm , Isaac Gelado , Sam S. Stone , Robert E. Kidd , Sara S. Baghsorkhi , Aqeel A. Mahesri , Stephanie C. Tsao , Nacho Navarro , Steve S. Lumetta , Matthew I. Frank , Sanjay J. Patel, Implicitly parallel programming models for thousand-core microprocessors, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278669]
• 54: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 55: Lumsdaine, A., et al., Challenges in Parallel Graph Processing. Parallel Processing Letters, 17(1): 5--20, 2007.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Design

Keywords:
framework, manycore, parallelization, pattern