Homework

Homework NEW: Talk Schedules HERE.

• Reading assignment: placement papers
  • [Quad] (1/2 page summary due 1387/02/22) D. J. H. Huang and A. B. Kahng,
    " Partitioning-Based Standard-cell Global Placement with an Exact Objective ",
    International Symposium on Physical Design (ISPD), pp. 18-25, 1997.
  • [mPG] (1/2 page summary due 1387/02/29) C.-C. Chang, J. Cong and X. Yuan,
    "Multi-level Placement for Large-Scale Mixed-Size IC Designs,"
    Proc. Asia South Pacific Design Automation Conference, pp 325-330, January 2003.
  • [FastPlace] (1/2 page summary due 1387/03/05) N. Viswanathan, C. Chu,
    " FastPlace: efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model ",
    International Symposium on Physical Design (ISPD), pp. 26 - 33, 2004.
• Reading assignment: floorplanning papers
  • [SeqPair] (1/2 page summary due 1387/02/01) H. Murata, K. Fujiyoushi, S. Nakatake and Y. Kajitani,
    "Rectangle-Packing-Based Module Placement",
    International Conference on Computer-Aided Design (ICCAD), pp. 472-479, 1995.
  • [uArchFP] (1/2 page summary due 1387/02/15)
    Vidyasagar Nookala Ying Chen David J. Lilja Sachin S. Sapatnekar, "Microarchitecture-Aware Floorplanning Using a Statistical Design of Experiments Approach", Design Automation Conference (DAC), pp. 579 - 584, 2005.
• HW#3: placement. Assigned 1387/02/10, Phase 1 due 1387/02/17, Phase 2 due 1387/02/24.
• Reading assignment: partitioning papers (read by 1386/12/25)
  • [hMetis] George Karypis, Rajat Aggarwal, Vipin Kumar and Shashi Shekhar,
    "Multilevel hypergraph partitioning: application in VLSI domain",
    Design Automation Conference, pp. 526-529, 1997.
  • [pathPart] C. Aabei, N. Selva, K. Bazargan and G. Karypis, http://www.ece.umn.edu/users/kia/Papers/2002/iccad02.pdf Multi-objective Circuit Partitioning for Cutsize and Path-Based Delay Minimization , International Conference on Computer-Aided Design (ICCAD), pp. 181-185, 2002.
• HW#2: algorithms, partitioning. Assigned 86/12/20, due 87/1/18.
• PA#3: partitioning. Assigned 86/12/20, due 87/1/18.
• PA#2: static timing analysis. Assigned 86/11/27, due 86/12/07.
• HW#1: time complexity. Assigned 1386/11/14, Due 1386/11/23.
• Programming assignment #1: Reading Netlists. Assigned 1386/11/14, Due 1386/11/28.

Paper Presentations

In general, you can find slides for the ICCAD and DAC papers on these conferences web pages. Feel free to use these slides in your presentations. http://www.iccad.com/archive.html and http://www2.dac.com/42nd/parchives.html.

• Power / Ground analysis
  • [RandomWalk] {MohsenNassaji 1387/03/14} Haifeng Qian, Sani R. Nassif, Sachin S. Sapatnekar,
    "Random walks in a supply network",
    Design Automation Conference (DAC), pp. 93-98, 2003.
• FPGA
  • [OnlineFP]{MAliFarmahini 1387/03/14} Manish Handa and Ranga Vemuri,
    "An Efficient Algorithm for Finding Empty Space for Online FPGA Placement",
    Design Automation Conference (DAC), pp. 960-965, 2004.
  • [HLS_FPGA] {MohammadRezaYousefizadeh 1387/03/12}  K. Bazargan, S. Ogrenci and M. Sarrafzadeh,
    "Integrating Scheduling and Physical Design into a Coherent Compilation Cycle for Reconfigurable Computing Architectures",
    Design Automation Conference (DAC), pp. 635-640 , 2001 {kia has the slides}
  • [FPGA-FP]{MohsenPaknejad 1387/03/07}  Lei Cheng, Martin DF Wong,
    "Floorplan Design for Multi-Million Gate FPGAs",
    ICCAD, 2004. 
  • [PPFF]{HajarFalahati 1387/03/07} P. Maidee, C. Ababei and K. Bazargan,
    "Fast Timing-driven Partitioning-based Placement for Island Style FPGAs",
    Design Automation Conference (DAC), pp. 598-603, 2003. (slides (zipped ppt))
  • [Clustering]{SMAliZeinolAbedin 1387/03/07}  A. Singh and M. Marek-Sadowska,
    "Efficient Circuit Clustering for Area and Power Reduction in FPGAs",
    International Symposium on Field Programmable Gate Arrays (FPGA), pp. 59-66, 2002
  • [IncPlcFPGA]{MohsenPaknejad 1387/03/05} Singh, D. P. and Brown, S. D. " Incremental placement for layout driven optimizations on FPGAs". In Proceedings of the 2002 IEEE/ACM international Conference on Computer-Aided Design (San Jose, California, November 10 - 14, 2002). ICCAD '02. ACM Press, New York, NY, 752-759. DOI= http://doi.acm.org/10.1145/774572.774683
• Routing / Congestion
  • [fGREP] {MohammadRezaYousefizadeh RECORD 1387/02/31} Parivallal Kannan , Shankar Balachandran , Dinesh Bhatia,
    "On metrics for comparing routability estimation methods for FPGAs",
    Design Automation Conference, pp 639-646 , 2002.
  • [xtalk] {MohsenMahmoodi 1387/02/31} Tsung-Yi Ho, Yao-Wen Chang, Sao-Jie Chen and Der-Tsai Lee,
    "A Fast Crosstalk- and Performance-Driven Multilevel Routing System",
    ICCAD, 2003.
  • [VanGinneken]{SMAliZeinolAbedin 1387/02/31}L. P. P. P. van Ginneken,
    "Buffer placement in distributed RC-tree network for minimal Elmore delay,"
    in Proc. IEEE Int. Symp. Circuits Syst. 1990, pp. 865-868
• Placement
  • [Dragon] {VajihehSabeti 1387/02/29} M. Wang, X. Yang and M. Sarrafzadeh,"Dragon2000: Standard-cell Placement Tool for Large Industry Circuits".International Conference on Computer-Aided Design, 2000. (download from: http://er.cs.ucla.edu/Dragon/ )
  • [Capo] {} A. E. Caldwell, A. B. Kahng and I. L. Markov,
    "Can Recursive Bisection Produce Routable Placements?"slides Design Automation Conf. (DAC), Los Angeles, pp. 477-482, June 2000.
  • [PEKO] {HosseinYounesi 1387/02/17} C.-C. Chang, J. Cong, M. Xie,
    "Optimality and Scalability Study of Existing Placement Algorithms",
    Proc. Asia South Pacific Design Automation Conference, pp 621-627, January 2003.
  • [3DPlc] {EhsanAerabi 1387/02/29} C. Ababei, H. Mogal, and K. Bazargan, " Three-dimensional Place and Route for FPGAs ", Asia South-Pacific Design Automation Conference (ASPDAC) , pp. 773 - 778, 2005.
  • [DensityPlc] {MohsenMahmoodi 1387/03/12} Tung-Chieh Chen, Zhe-Wei Jiang, Tien-Chang Hsu, Hsin-Chen Chen, Yao-Wen Chang, "A High Quality Analytical Placer Considering Preplaced Blocks and Density Constraint ", ICCAD 2006.
  • [GridWarp]{MohsenNassaji 1387/02/29} Zhong Xiu, Rob A. Rutenbar, "Timing-Driven Placement by Grid-Warping", DAC 2005.
  • [Mongrel] { } S.-W. Hur, J. Lillis, " ``Mongrel: Hybrid Techniques for Standard Cell Placement,'' , IEEE International Conference on Computer-Aided Design ; November 5-9, 2000, San Jose, CA; pp. 165-170.
• Floorplanning
  • [BusFP] {MAliFarmahini 1387/02/24} H. Xiang, X. Tang, M. D. F. Wong,
    "Bus-Driven Floorplanning",
    International Conference on Computer Aided Design (ICCAD), pp. 66-73, 2003.
  • [FastFP] {MohammadrezaHaghshenas 1387/02/24 } A. Ranjan, K. Bazargan and M. Sarrafzadeh,
    "Floorplanner 1000 Times Faster: A Good Predictor and Constructor",
    in System-Level Interconnection Prediction (SLIP), pp. 115-120, 1999.
  • [PowerFP]{HajarFalahati 1387/02/22} Wan-Ping Lee, Hung-Yi Liu, Yao-Wen Chang, "Voltage Island Aware Floorplanning for Power and Timing Optimization", ICCAD 2006.
  • [FPOptimality] {EhsanAerabi 1387/02/22} J. Cong, G. Nataneli, M. Romesis, and J. Shinnerl, " An Area-Optimality Study of Floorplanning, " Proceedings of the International Symposium on Physical Design , pp. 78 - 83, April 2004.
• Partitioning:
  • [BEKU] {HosseinYounesi 1387/02/17} J. Cong, M. Romesis, and M. Xie "Optimality, Scalability and Stability Study of Partitioning and Placement Algorithms", International Symposium on Physical Design, 2003.
  • [MLPart] { } A. Caldwell, A. Kahng, and I. Markov, "Improved Algorithms for Hypergraph Bipartitioning", Proc. Asia and South Pacific Design Automation Conf., Jan. 2000, pp. 661-666.
  • [fixedPart] {MohammadrezaHaghshenas 1387/02/17} A. E. Caldwell, A. B. Kahng and I. L. Markov, "Hypergraph Partitioning With Fixed Vertices", Design Automation Conference (DAC), pp. 355-359, 1999.
  • [MultiPart] {VajihehSabeti 1387/02/17} Navaratnasothie Selvakkumaran, Abhishek Ranjan, Salil Raje, and George Karypis, " Multi-Resource Aware Partitioning Algorithms for FPGAs with Heterogeneous Resources", 41st Design Automation Conference, pp. 741-746, 2004.
• Misc.:
  • [SSTA] {} CHOOSE A SIMPLE PAPER ON STATISTICAL TIMING ANAL BASICS
  • [Genetic] {} CHOOSE A PAPER ON GENETIC ALGORITHMS

Homework Policies

Refer to "Policies" section of the course page for homework policies.

Exams & Solutions

Fall 2006: midterm2 and solutions to midterm 2.

Archive

Fall 2005: Howework, midterm.

Fall 2004: Homework,  Final and solutions, midterm and solutions.

Fall 2003: homework,  Final and solutions, Midterm., and solution to problem 4-1.

Fall 2002: Homework , final exam,  midterm exam, and solutions.

Fall 2001: Homework,  midterm exam, and solutions.

• Fall 2001 final exam version A, and solutions (page 1, page 2, page 3)
• Fall 2001 final exam version B, and solutions (page 1, page 2, page 3, page 4)

Homework Policies

Refer to "Policies" section of the course page for homework policies.

Exams & Solutions

Fall 2006: midterm2 and solutions to midterm 2.

Archive

Fall 2005: Howework, midterm.

Fall 2004: Homework,  Final and solutions, midterm and solutions.

Fall 2003: homework,  Final and solutions, Midterm., and solution to problem 4-1.

Fall 2002: Homework , final exam,  midterm exam, and solutions.

Fall 2001: Homework,  midterm exam, and solutions.

• Fall 2001 final exam version A, and solutions (page 1, page 2, page 3)
• Fall 2001 final exam version B, and solutions (page 1, page 2, page 3, page 4)