ECE 1387: CAD For Digital Circuit
Synthesis and Layout

J. Anderson
Fall 2011

Tentative Lecture Schedule and Reading List

  • Lecture 1: Introduction and Overview
  • Lecture 2: Detailed Routing (applied to FPGAs)
    • Background Literature:
      • C.Y. Lee, "An algorithm for path connections and its applications," IRE Transactions on Electronic Computers,vol. 10, pp. 346-365, Sept. 1961. (PDF)  (Classic paper on maze routing)
      • See Section III-D of: M.A. Breuer, M. Sarrafzadeh, F. Somenzi, "Fundamental CAD algorithms," IEEE Transactions on CAD, Vol. 19, No. 12, pp. 1449-1475, December 2000 (PDF)
      • J.S. Rose, S.D. Brown, "Flexibility of interconnection structures for field-programmable gate arrays", IEEE Journal of Solid State Circuits, Vol. 26 No. 3, pp. 277-282, March 1991. (reference only; classic paper that may help with assignment #1) (PDF)
      • S.D. Brown, J.S. Rose, Z.G. Vranesic, "A detailed router for field-programmable gate arrays," IEEE Transactions on CAD, Vol. 11, No. 5, pp. 620-628, May 1992. (reference only: may help with assignment #1) (PDF)
      • Jordan S. Swartz, Vaughn Betz, Jonathan Rose: A Fast Routability-Driven Router for FPGAs. FPGA 1998: 140-149 (PDF).
  • Lecture 3: Timing-Driven Routing
    • Background Literature:
      • Derivation of the closed-form Elmore delay formula for RC tree delay (source: Prof. Lei He, UCLA) (PDF)
      • Ravi Nair, "A simple yet effective technique for global wiring," IEEE Transactions on CAD, Vol. 6, No. 2, pp. 165-172, 1987. (PDF)
      • J. Rubenstein, P. Penfield, M. A. Horowitz, “Signal delay in RC tree networks,” IEEE Transactions on CAD, vol. 2, no. 3, pp. 202-211, July 1983. (PDF)
      • W.C. Elmore, "The transient response of damped linear networks," Journal of Applied Physics, Vol. 19, pp. 55-63, January 1948.
      • Larry McMurchie, Carl Ebeling. "PathFinder: A negotiation-based performance-driven router for FPGAs," ACM International Symposium on Field Programmable Gate Arrays, pp. 111-117, 1995. (PDF)
  • Lecture 4: Timing-Driven Routing (cont), Intro to Placement
    • Background Literature:
      • R. Fung, V. Betz, and W. Chow, "Slack Allocation and Routing to Improve FPGA Timing While Repairing Short-Path Violations," IEEE Trans. on Computer-Aided Design of Circuits and Systems, April 2008, pp. 686 - 697. (PDF)
      • Moffitt, M. D., Roy, J. A., and Markov, I. L. 2008. The coming of age of (academic) global routing. In Proceedings of the 2008 international Symposium on Physical Design (Portland, Oregon, USA, April 13 - 16, 2008). ISPD '08. pp. 148-155. (PDF)
      • Hadsell, R.T.; Madden, P.H., "Improved global routing through congestion estimation," Design Automation Conference, 2003. Proceedings , pp. 28-31, 2-6 June 2003  (PDF)
  • Lecture 5: Placement (Analytical Techniques)
    • Background Literature:
      • Viswanathan, N.; Chu, C.C.-N., "FastPlace: efficient analytical placement using cell shifting, iterative local refinement,and a hybrid net model," Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on , vol.24, no.5, pp. 722-733, May 2005  (PDF)
      • Sigl, G.; Doll, K.; Johannes, F.M.; , "Analytical placement: a linear or a quadratic objective function?," IEEE/ACM Design Automation Conference,  pp.427-432, 1991.  (PDF)
      • K. P. Vorwerk, A. Kennings, A. Vannelli, "Engineering details of a stable force-directed placer", IEEE/ACM International Conference on Computer-Aided Design, 2004, pp. 573-580. (optional: on implementing/optimizing Eisenmann's algorithm) (PDF)
      • Natarajan Viswanathan, Gi-Joon Nam, Charles Alpert, Paul Villarrubia, Haoxing Ren, and Chris Chu, RQL: Global Placement via Relaxed Quadratic Spreading and Linearization IEEE/ACM Design Automation Conference, pages 453-458, 2007. (PDF)
      • Huimin Bian, Andrew C. Ling, Alexander Choong, Jianwen Zhu: Towards scalable placement for FPGAs. ACM FPGA 2010: 147-156. (PDF)
      • J. M. Kleinhans, G. Sigl, F. M. Johannes, K. J. Antreich, "GORDIAN: VLSI placement by quadratic programming and slicing optimization, " IEEE Transactions on CAD, Vol. 10, No. 3, pp. 356-365, 1991. (optional: classic paper) (PDF)
  • Lecture 6: Placement (Simulated Annealing)
    • Background Literature:
      • S. Kirkpatrick, C. Gellat, M. Vecchi, "Optimization by simulated annealing," Science, 220:671-680, 1983. (PDF)
      • C. Sechen, A. Sangiovanni-Vincentelli, "The TimberWolf placement and routing package," IEEE Journal of Solid State Circuits, Vol. 20, No. 2, pp. 432-439, 1985. (PDF)
      • V. Betz, J. Rose, "VPR: A new packing, placement and routing tool for FPGA research," International Workshop on Field-Programmable Logic and Applications, London, UK, 1997, pp. 213 - 222. (PDF)
      • Chih-liang Eric Cheng, "Risa: Accurate And Efficient Placement Routability Modeling," Computer-Aided Design, 1994., IEEE/ACM International Conference on , vol., no., pp.690-695, 6-10 Nov 1994. (PDF)
  • Lecture 7: Timing Analysis and Slack Allocation
    • Background Literature:
      • R. B. Hitchcock, G. L. Smith, D. D. Cheng, "Timing analysis of computer hardware," IBM Journal of Research and Development, 26(1):100-105, January 1982. (PDF)
      • Jon Frankle, "Iterative and adaptive slack allocation for performance-driven layout and FPGA routing," ACM/IEEE Design Automation Conference, 1992, pp. 536-542. (PDF)
      • H. Youssef, E. Shragowitz, "Timing constraints for correct performance," IEEE International Conference on Computer-Aided Design, 1990, pp. 24-27. (PDF)
      • H. Chang and S. S. Sapatnekar, “Statistical Timing Analysis Under Spatial Correlations,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 24, No. 9, pp. 1467 – 1482, September 2005. (PDF)
  • Lecture 8: Partitioning (Branch and Bound)
    • Background Literature:
      • A nice overview of branch and bound that I found on the web is called "Branch and Bound Algorithms - Principles and Examples", by Jens Clausen. (PDF)
      • B. Kernighan, S. Lin, "An efficient heuristic procedure for partitioning of electrical circuits," Bell System Technical Journal, pp. 291-307, 1970. (classic paper). (PDF)
      • A. E. Caldwell, A. B. Kahng, I. L. Markov, "Optimal Partitioners and End-case Placers for Standard-cell Layout", IEEE Trans. on CAD, vol. 19, no. 11, pp. 1304-1314, 2000. (PDF)
  • Lecture 9: Partitioning (FM/Multi-Level with hMetis)
    • Background Literature:
      • C. M. Fiduccia, R. M. Mattheyses. "A linear-time heuristic for improving network partitions," ACM/IEEE Design Automation Conference, pp 174-181, 1982. (PDF)
      • G. Karypis, R. Aggarwal, V. Kumar, S. Shekhar, "Multilevel hypergraph partitioning: Applications in the VLSI domain," IEEE Transactions on VLSI Systems, 07(01):69-79, March 1999. (PDF)
      • A. E. Caldwell, A. B. Kahng and I. L. Markov, "Can Recursive Bisection Alone Produce Routable Placements?", Proc. Design Automation Conf., Los Angeles, June 2000, pp. 693-698. (PDF)
      • Lars W. Hagen, Dennis J.-H. Huang, Andrew B. Kahng: On implementation choices for iterative improvement partitioning algorithms. IEEE Trans. on CAD of Integrated Circuits and Systems 16(10): 1199-1205 (1997)  (PDF)
  • Lecture 10: Technology Mapping (Dynamic Programming)
    • Background Literature:
      • An intro to dynamic programming can be found in chapter 15 of T.H. Cormen, C.E. Leiserson, R.L. Rivest, "Introduction To Algorithms - Second Edition", McGraw-Hill, 2001.
      • A clear overview of dynamic programming, with a few examples, can be found in Wikipedia (here)
      • A. Mishchenko, S. Chatterjee, and R. Brayton, "Improvements to technology mapping for LUT-based FPGAs", to appear in  IEEE Transactions on CAD, 2007.  (PDF)
      • K. Keutzer, "DAGON: Technology Binding and Local Optimization by DAG Matching," ACM/IEEE Design Automation Conference, 1987, pp. 341-347. (PDF)
      • J.H. Anderson and F. N. Najm, "Power-Aware Technology Mapping for LUT-Based FPGAs," IEEE International Conference on Field-Programmable Technology (FPT), Hong Kong, 2002, pp. 211 - 218. (PDF)
      • K. C. Chen, J. Cong, Y. Ding, A. B. Kahng and P. Trajmar, "DAG-MAP: Graph Based FPGA Technology Mapping For Delay Optimization", IEEE Design and Test, September 1992, pp. 7-20. (PDF) (describes how to break an arbitrary Boolean Network into smaller k-input functions)
  • Lecture 11: Tech Mapping and Logic Synthesis
    • Background Literature:
      • Jason H. Anderson, Chirag Ravishankar: FPGA power reduction by guarded evaluation. FPGA 2010: 157-166  (PDF)
      • A. Mishchenko, S. Cho, S. Chatterjee, and R. Brayton, "Combinational and sequential mapping with priority cuts", Proc. ICCAD '07, pp. 354-361.  (PDF)
      • Alan Mishchenko, Satrajit Chatterjee, Robert K. Brayton: DAG-aware AIG rewriting a fresh look at combinational logic synthesis. DAC 2006: 532-535  (PDF)
  • Lecture 12: Special Guest Lecture TBA