Instructor: Lei He
Department of Electrical Engineering
Office: 62037 Engineering IV
Phone: 206 2037
E-Mail: lhe@ee.ucla.edu

Course Outline and Schedule

• Paritioning, floorplanning and placement
• Power and thermal modeling
• Algorithms: divided and conquer, simulated annealing, genetic algorithm

• Interconnect extraction and modeling
• Interconnect synthesis
• Noise modeling and avoidance
• Clock and power supply design
• Algorithms: dynamic programming, linear programming
• Project report due the last day of the quarter

Grading Policy:
15% homework, 20% midterm, 15% presentation, and 50% project.

• 2~3 student a team
• Survey an area (topics and resources specified by me on a continual basis)
• Prepare slides and do a 30-35 minute presentation in the class
  • slides prepared jointly
  • either all students share the presentation or I will select the speaker randomly at the presentation time
• Prepare a web site that should contain a report based on your survey, a bibliography, and links to resources and of course your slides
• Topics and Schedule

• One of the following two:
  • One-person survey and critic of selected topic (at most 35%)
  • Individual programming project for a team of 2 to 3 persons
    • Project proposal due on May 9th (Sample Proposal)
    • List of Topics
• Up to 20 minute presentation during the final week, like a conference talk
• Up to 12 page report in the style of a technical conference paper
  • ACM style
• SIS: Tutorial, source code, test bench
• Schedule of Final Presentation
• Evaluation Form for Final Presentation

• specification, test case 1, test case 2
• due: May 2nd mid-night

• B. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning of Electrical Circuits", Bell System Technical Journal", pp291-307, 1970. (pdf)
• C. M. Fiduccia and R. M. Mattheyses. "A linear-time heuristic for improving network partitions". Proceedings of the Design Automation Conference, pp 174-181, 1982. (pdf)
• J. W. Greene and K. J. Supowit. "Simulated Annealing Without Rejected Moves". IEEE Transactions on Computer-Aided Design, Vol. CAD-5, NO. 1, 1986. (pdf)
• J. Cong and Y. Ding, "On area/depth trade-off in LUT-based FPGA technology mapping", Very Large Scale Integration (VLSI) Systems, IEEE Transactions on , Volume: 2 , Issue: 2 , June 1994, Pages:137 - 148. (pdf)

• G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, "Multilevel Hypergraph Partitioning: Application in VLSI Domain", Proceedings of the Design Automation Conference, pp 526-529, 1997 (pdf). (ppt).

• L. Stockmeyer, "Optimal Orientation of Cells in Slicing Floorplan Designs", Information and Control, pp 91-101, 1983. (pdf).
• D. F. Wong and C. L. Liu, "A New Algorithm for Floorplan Design", Proc. Design Automation Conference, pp 101-107, 1986. (pdf).
• C. Long, L. Simonson, W. Liao and L. He, "Floorplanning Optimization with Trajectory Piecewise-Linear Model for Pipelined Interconnects", IEEE/ACM Design Automation Conference, June 2004. (pdf), (ppt).

• H. Murata, K. Fujiyoshi, S. Nakatake and Y. Kajitani, "VLSI module placement based on rectangle-packing by the sequence-pair", IEEE Trans. on Computer-Aided Design, pp 1518-1524, 1996. (pdf).
• P.N. Guo, C.K. Cheng, and T. Yoshimura, " An O-Tree Representation of Nonslicing Floorplan and Its Applications, " ACM/IEEE Design Automation Conf., pp. 268-273, June 1999. (pdf).
• C.T. Lin, D.S. Chen and Y.W. Wang, "GPE: A New Representation for VLSI Floorplann Problem", ICCD'02. (pdf).

• W. J. Sun and C. Sechen, "Efficient and Effective Placement for Very Large Circuits", IEEE Trans. on Computer-Aided Design, pp 349-359, 1995. (pdf).

• Kleinhaus, G. Sigl, F. Johannes, K. Antreich, "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization", IEEE Trans. on CAD, pp 356-365, 1991. (pdf).
• G. Sigl, K. Doll and F.M. Johannes, "Analytical placement: A Linear or Quadratic Objective Function?", Proc. DAC, pp 427-432, 1991. (pdf) (pdf).

• thermal modeling and calculation
• power modeling and leakage reduction.

• Temperature Aware Microarchitecture(pdf).
• Wei Huang, Mircea R. Stan, Kevin Skadron, Karthik Sankaranarayanan, Shougata Ghosh, Sivakumar Velusamy, "Compact Thermal Modeling for Temperature-Aware Design", DAC'04 (pdf).
• Lei He, Weiping Liao and Mircea R. Stan, "System Level Leakage Reduction Considering the Interdependency between Temperature and Leakage", DAC'04 (pdf).
• Kaushik Roy and Saibal Mukhopadhyay, "Leakage Estimation and Leakage Control for Nano-Scale CMOS Circuits", DAC'04 (doc).

• J. Cong, L. He, A. B. Kahng, D. Noice, N. Shirali and S. H.-C. Yen, "Analysis and Justification of a Simple, Practical 2 1/2-D Capacitance Extraction Methodology", ACM/IEEE Design Automation Conference, June 1997, pp.627-632.
• L. He, N. Chang, S. Lin, and O. S. Nakagawa, "An Efficient Inductance Modeling for On-chip Interconnects," IEEE Custom Integrated Circuits Conference, May 1999.
• M. Xu and L. He, "An efficient model for frequency-based on-chip inductance," IEEE/ACM International Great Lakes Symposium on VLSI, March 2001. (pdf)

• Cong-et al, Integration'96, Section 2.1-2.2.
• Elmore delay model (Elmore, Journal of Applied Physics, 1948, pdf),
• Elmore delay for RC tree (Rubinsteun-Penfield-Horowitz,TCAD'83, pdf),
• Ceff model (pdf)

• Structured ASIC: ppt
  Reading:
  • Structured ASICs: Opportunities and Chanllenges (pdf)
  • Structured ASICs, Evolution or Revolution? (pdf)
  • Design Methodology and Tools (pdf)
• 3D integrated circuits: ppt
  Reading:
  • Overview (pdf)
  • Fabrication (pdf)
  • Modeling (pdf)
  • Design Methodology and Tools (pdf)
• Process variations: ppt
  Reading:
  • GIT paper (pdf)
  • Intel paper (pdf)

• Overview: Cong-et al, Integration'96, Section 4.1.2
• sensitivity-based transistor sizing: TILOS(pdf);
• Convex Programming based transistor sizing: pdf.
• Transistor sizing for dynamic and short-circuit power reduction: pdf.

• Cong-et al, Integration'96, Section 4.1.1, 4.1.3,
• Buffer insertion: Van Ginneken(ISCAS'90, pdf);
• Wiresized-and-buffered A-tree.
• buffer block planning .

• L. He and K. M. Lepak, "Simultaneous shield insertion and net ordering for capacitive and inductive coupling minimization", IEEE/ACM International Symposium on Physical Design, April 2000 (pdf)
• J. Xiong, L. He, "Full-chip Routing Optimization with RLC Crosstalk Budgeting", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2004 (pdf).

• J. Cong, J. Fang and Y. Zhang "Multilevel Approach to Full-Chip Gridless Routing," Proc. IEEE International Conference on Computer Aided Design, San Jose, California, pp. 396-403, November 2001 (pdf)
• J. Xiong and L. He, "Full-chip Multilevel Routing for Power and Signal Integrity", Design Automation and Test in Europe, March 2004. (pdf)

• Anirudh Devgan, "Efficient Coupled Noise Estimation for On-chip Interconnects", ICCAD, 1997. (pdf)
• J. Cong, Z. Pan and P. V. Srinivas, "Improved Crosstalk Modeling for Noise Constrained Interconnect Optimization", Proc. Asia South Pacific Design Automation Conference (ASPDAC), Jan. 30 - Feb. 2, 2001, Pacifico Yokohama, Japan (pdf)