• ECE 1387: CAD For Digital Circuit
    Synthesis and Layout

  • J. Anderson
  • Fall 2015
  • Reading List

  • Lecture 1: Introduction and Overview
    • Background literature:
      • Gordon E. Moore, “Cramming More Components onto Integrated Circuits,” Electronics, pp. 114–117, April 19, 1965.  (PDF)
  • 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:
      • Ravi Nair, "A simple yet effective technique for global wiring," IEEE Transactions on CAD, Vol. 6, No. 2, pp. 165-172, 1987. (PDF)
      • 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)
      • 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)
      • M. Gort, and J. Anderson, "Combined Architecture/Algorithm Approach to Fast FPGA Routing," IEEE Trans. on VLSI, Vol. 21, No. 6, pp. 1067-1079, June 2013 (PDF)
  • Lecture 4: Routing/Placement
    • Background literature:
      • N. Viswanathan, C. Chu, "FastPlace: Efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model," IEEE TCAD, vol 24, no. 5, 2005 (PDF).
      • M. Kim, D. Lee, I. Markov, "SimPL: An algorithm for placing VLSI circuits," Communications of the ACM, Vol 56, no 6., June 2013 (PDF). 
      • M. Kim, D. Lee, I. Markov, "SimPL: AN effective placement algorithm," IEEE TCAD, Vol 11, No 1, 2012, pp. 50-60.  (PDF)
      • M. Gort, J. Anderson, "Analytical placement for heterogeneous FPGAs," IEEE FPL, 2012, pp. 143-150,  (PDF).
  • Lecture 5: Placement (cont'd)
    • 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)
  • Lecture 6: Placement (cont'd)
    • Background literature:
      •  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)
      • Paper on the Bound2Bound net model (PDF)
      • A. Ludwin and V. Betz, "Efficient and Deterministic Parallel Placement for FPGAs," ACM Trans. on Design Automation of Electronic Systems, Vol. 16, No. 3, June 2011, pp. 22:1 - 22:23.  (PDF)
  • Lecture 7: Partitioning (branch and bound)
    • Background literature:
  • Lecture 8: Partitioning (FM + multi-level)
    • 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. HagenDennis 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:
    • 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)
Lecture 11: High-Level Synthesis (Linear Programming)
  • Philippe Coussy, Daniel D. Gajski, Michael Meredith, Andrés Takach: An Introduction to High-Level Synthesis. IEEE Design & Test of Computers 26(4): 8-17 (2009) (PDF)
  • Jason Cong, Zhiru Zhang: An efficient and versatile scheduling algorithm based on SDC formulation. DAC 2006: 433-438 (PDF)
  • Andrew Canis, Jongsok Choi, Mark Aldham, Victor Zhang, Ahmed Kammoona, Tomasz S. Czajkowski, Stephen Dean Brown, Jason Helge Anderson: LegUp: An open-source high-level synthesis tool for FPGA-based processor/accelerator systems. ACM Trans. Embedded Comput. Syst. 13(2): 24 (2013) (PDF)
  • Jae-Gon Kim; Yeong-Dae Kim, "A linear programming-based algorithm for floorplanning in VLSI design," Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on , vol.22, no.5, pp.584,592, May 2003 (PDF)