Algorithms for VLSI

Credits
6
Types
  • MIRI: Specialization complementary (Advanced Computing)
  • MEI: Elective
Requirements
This subject has not requirements , but it has got previous capacities
Department
CS
Most of the design flow of an integrated circuit is automated, starting from the specifications using Hardware Description Languages until reaching the physical layout. The flow goes through different synthesis and analysis phases: behavioral synthesis, logic synthesis, floorplanning, placement, routing, timing analysis, formal verification, etc. This course will review the most important algorithmic aspects in design automation of electronic circuits. A significant part of the course will be devoted to algorithms for minimization of Boolean functions and representation with logic gates. The algorithms for physical design (floorplanning, placement and routing) will be mostly based on solving problems with graph models.

Course Syllabus (summary). Circuit design flow: from specification to layout. Minimization of logic circuits: algorithms for two-level and multi-level logic synthesis.
Technology mapping. Algorithms for physical synthesis: floorplanning, placement and routing. Formal verification: equivalence and model checking.

Teachers

Person in charge

Weekly hours

Theory
2
Problems
2
Laboratory
0
Guided learning
0
Autonomous learning
7.11

Competences

Technical Competences of each Specialization

Advanced computing

  • CEE3.1 - Capability to identify computational barriers and to analyze the complexity of computational problems in different areas of science and technology as well as to represent high complexity problems in mathematical structures which can be treated effectively with algorithmic schemes.
  • CEE3.2 - Capability to use a wide and varied spectrum of algorithmic resources to solve high difficulty algorithmic problems.
  • CEE3.3 - Capability to understand the computational requirements of problems from non-informatics disciplines and to make significant contributions in multidisciplinary teams that use computing.

    • Generic Technical Competences

    Generic

  • CG1 - Capability to apply the scientific method to study and analyse of phenomena and systems in any area of Computer Science, and in the conception, design and implementation of innovative and original solutions.
  • CG3 - Capacity for mathematical modeling, calculation and experimental designing in technology and companies engineering centers, particularly in research and innovation in all areas of Computer Science.

    • Transversal Competences

    Reasoning

  • CTR6 - Capacity for critical, logical and mathematical reasoning. Capability to solve problems in their area of study. Capacity for abstraction: the capability to create and use models that reflect real situations. Capability to design and implement simple experiments, and analyze and interpret their results. Capacity for analysis, synthesis and evaluation.

    • Basic

  • CB6 - Ability to apply the acquired knowledge and capacity for solving problems in new or unknown environments within broader (or multidisciplinary) contexts related to their area of study.
  • CB8 - Capability to communicate their conclusions, and the knowledge and rationale underpinning these, to both skilled and unskilled public in a clear and unambiguous way.
  • CB9 - Possession of the learning skills that enable the students to continue studying in a way that will be mainly self-directed or autonomous.

    • Objectives

    1. Understanding the design flow of a VLSI circuit
      Related competences: CG1, CEE3.2,
    2. Learning new algorithmic techniques for logic synthesis and formal verification
      Related competences: CG3, CEE3.1, CEE3.2, CEE3.3, CTR6,
    3. Learning new algorithmic technique for physical synthesis
      Related competences: CG3, CEE3.1, CEE3.2, CEE3.3, CTR6,
    4. Modelling and solving problems on Electronic Design Automation
      Related competences: CG1, CB6, CB9,
    5. Developing an EDA project and doing a public presentation of the solution
      Related competences: CG1, CEE3.1, CB8,

    Contents

    1. Introduction.
      Integrated circuit fabrication. Layout layers and design rules. VLSI design flow. VLSI design styles.
    2. Partitioning and Floorplanning
      Partitioning algorithms. Representation of floorplans. Slicing floorplans. Floorplanning algorithms.
    3. Placement
      Optimization objectives. Algorithms for global placement. Algorithms for legalization and detailed placement.
    4. Global routing
      Representation of routing regions. Algorithms for single-net and full-net routing.
    5. Detailed routing
      Horizontal and vertical constraint graphs. Channel routing. Switchbox routing. Over-the-cell routing.
    6. Two-level logic synthesis
      Boolean Algebras. Representation of Boolean functions. Quine-McCluskey algorithm. Heuristic logic minimization: Espresso.
    7. Multi-level logic synthesis.
      Kernel-based algebraic decomposition. AIG-based decomposition. Technology mapping for standard cells and FPGAs.
    8. Formal verification
      Binary Decision Diagrams. Combinational equivalence checking. Sequential equivalence checking. Model checking with temporal logic.

    Activities

    Activity Evaluation act


    Learning the design flow of a VLSI circuit


    Objectives: 1
    Theory
    1h
    Problems
    1h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    1h

    Learning of algorithms for logic synthesis


    Objectives: 1 2
    Theory
    7h
    Problems
    8h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    16h

    Learning of techniques for formal verification of circuits


    Objectives: 1 2
    Theory
    4h
    Problems
    5h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    10h

    Learning of techniques for circuit floorplanning and placement


    Objectives: 1 3
    Theory
    6h
    Problems
    7h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    15h

    Learning of routing algorithms



    Theory
    6h
    Problems
    6h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    14h

    Assignment on physical synthesis


    Objectives: 3 4
    Week: 8 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Assignment on logic synthesis


    Objectives: 1 2 4
    Week: 12 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    EDA project

    The student will have to implement an algorithm to solve a specific Electronic Design Automation (EDA) problem
    Objectives: 1 4 5
    Week: 2 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Final exam



    Week: 18 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Teaching methodology

    The theoretical content of the course is taught in the theory lectures. During the practical classes, practical examples are solved and different types of problems are proposed. These problems will have to be solved during the time of autonomous learning. An algorithmic project will also be proposed during the course. Students will have to solve and implement it during their time of autonomous learning.

    Evaluation methodology

    Grade = 35% FP + 35% FT + 30% EX

    FP = Final Project (graded from 0 to 10) in which each participant is required to develop a project on some algorithmic problem related to Electronic Design Automation, either proposed by the professor or by the student. The results of the project will have to be presented in class. The source code of the software will have to be delivered in some form such that the results of the project can be easily generated by executing the application.

    FT = Final Test graded from (0 to 10) covering the contents of the course.

    EX = Exercises assigned to the student and solved during the Autonomous Learning time. Two assignments will be delivered during the course (15% of the grade each one).

    Bibliography

    Basic

    Previous capacities

    Expertise in data structures and algorithms, with special emphasis on graph algorithms.