CSE 248, Fall 2023 Algorithmic and Optimization Foundations for VLSI CAD

University of California, San Diego

Instructor (Office hours TBA)

• CK Cheng, room CSE2130, email: ckcheng+248@ucsd.edu, tel: 858 534-6184

Teaching Assistant (NA)

Class Platform

• Canvas
• Gradescope
• Piazza

Schedule

• Lectures: 3:30-4:50PM TTH, EBU3B 2154

References

• IEEE IRDS Roadmap
• Interconnect Analysis and Synthesis, Cheng, Lillis, Lin, and Chang, John Wiley & Sons, 2000.
• Electronic Design Automation: Synthesis, Verfication, and Test, Wang, Chang, and Cheng, Morgan Kaufmann, 2009
• VLSI Physical Design: From Graph Partitioning to Timing Closure, Kahng, Lienig, Markov, and Hu, Springer, 2022.

Prerequisite

Basic circuit theory, discrete math, or intention of conducting projects related to scientific computation.

Content

We discuss the topics including IEEE IRDS Roadmap and implications, hypergraph partitioning, 2D/3D floorplanning, discrete and analytical placement, interconnect routing, standard-cell library layout generation and formulations for other applications.

Lectures

• Lecture 1 Introduction, let1.pdf. let1.pptx.
• Lecture 2 Moore's Law, let2.pdf. let2.pptx.
• IEEE IRDS Roadmap 2022 IRDS ES.pdf, 2022_IRDS_BC_Tables.xlsx, and 2022_IRDS_Litho_Tables.xlsx.
• Floorplan Representations, Floorplan_Representations.pdf.
• Lecture 3 Floorplan Representations, Lecture 3.ppt.
• Partitioning Papers, Ancestor-tree.pdf, BDDPart.pdf, max-flow-min-ratio-cut.pdf, A_replication_cut_for_two-way_partitioning.pdf,
• Retiming Paper by Leiserson, Leiserson.pdf; Retiming Example, Performance-driven_partitioning_using_retiming_and_replication.pdf; Cost to Time Ratio by Hartmann and Orlin, CostToTimeRatio.pdf; Retiming algorithm by Maji and Koh, Minimum_Cycle.pdf.
• Lecture 4 Partitioning, Partition.ppt, Partition.pdf.
• Lecture 5 Partitioning II: Replication and Retiming, PartitionII.pptx, PartitionII.pdf.
• Placement Papers, Spectral-Partitioning-Hall.pdf, ePlaceACM.pdf, ePlace-MS.pdf, ePlace-3D.pdf, dreamplace.pdf, dreamplace4.pdf, AutoDMPdreamplace.pdf, PCBPlacement.pdf, PlacementInitial.pdf,
• Lecture 6 Placement: outlines, Placement Intro.pptx, ePlace, placement.pptx, placement.pdf. PCB placement aspdac22nsplaceslides.pdf.
• Routing Papers, Global Routing GlobalRouting.pdf, FPGA Routing FPGArouting.pdf, Tree Routing TreeRouting.pdf,
• Standard Cell Layout, Slides LectureonStandardCells.pptx, Slides2 Framework_Cell_Generation.pptx,
• Standard cell layout papers CMOS Layout LayoutCMOS.pdf, SMT-Based Layout SMT-Based.pdf,
• Logic synthesis, Slides logic.pptx, Muti-level logic synthesis by P. Zhou 07-Multi-Level-Logic-Synthesis.pdf, Lecture notes by R. Jiang lec04Jiang.pdf, lec05Jiang.pdf, lec06_2pJiang.pdf, lec07_2pJiang.pdf.
• Logic synthesis papers
• Logic Circuit Complexity by Wegener, cobf.pdf,
• Logic Synthesis by Jiang and Devadas, ls-handout.pdf,
• Graph Based Transistor Network by Possani et al, Graph-Based_Transistor_Network.pdf, Topological Characteristics by Cardoso et al, Topological_characteristics.pdf, Threshold Logic by Neutzling et al, Threshold_Logic.pdf, Memristiv Logic by Marranghello et al, Memristive_Logic.pdf.
• Quantum Computing Circuits and Devices by Humble et al, Quantum_Computing_Circuits_and_Devices.pdf. Reversible Logic Gates Coomputing Circuits and Devices by Garipelly et al, A_Review_on_Reversible_Logic_Gates_and_t.pdf.

Slides from the Book by LT Wang, et al.

• Chapter 1 Introduction, Chapter 1.ppt.
• Chapter 2 CMOS, Chapter 2.ppt.
• Chapter 3 DFT, Chapter 3.ppt.
• Chapter 4 Algorithms, Chapter 4.ppt.
• Chapter 5 ESL HLS, Chapter 5.ppt.
• Chapter 6 Logic Synthesis, Chapter 6.ppt.
• Chapter 7 Test, Chapter 7.ppt.
• Chapter 8 Simulation, Chapter 8.ppt.
• Chapter 9 Verification, Chapter 9.ppt.
• Chapter 10 Floorplanning, Chapter 10.ppt.
• Chapter 11 Placement, Chapter 11.ppt.
• Chapter 12 Routing, Chapter 12.ppt.
• Chapter 13 CLK PG, Chapter 13.ppt.
• Chapter 14 FSIM ATPG, Chapter 14.ppt.

Homework: gradescope submission

• Homework 1: Introduction and Floorplanning, HW1.pdf, and latex file.
• Homework 2: Partitioning and Ancestor Tree, HW2.pdf, and latex file.
• Homework 3: Placement, HW3.pdf, and latex file.

Project

• Project outlines due the fourth week, outline format pdf,
• Report due the week of final 6PM Mon 12/11/2023. outlines and rubrics, pdf, pptx (W11)