Algoritmos para VLSI

Créditos
6
Tipos
  • MIRI: Complementaria de especialidad (Computación Avanzada)
  • MEI: Optativa
Requisitos
Esta asignatura no tiene requisitos , pero tiene capacidades previas
Departamento
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.

Profesorado

Responsable

Horas semanales

Teoría
2
Problemas
2
Laboratorio
0
Aprendizaje dirigido
0
Aprendizaje autónomo
7.11

Competencias

Competencias Técnicas de cada especialidad

Advanced computing

  • CEE3.1 - Capacidad para identificar barreras computacionales y analizar la complejidad de problemas computacionales en diversos ámbitos de la ciencia y la tecnología; así como para representar problemas de alta complejidad en estructuras matemáticas que puedan ser tratadas eficientemente con esquemas algorítmicos.
  • CEE3.2 - Capacidad para utilizar un espectro amplio y variado de recursos algorítmicos para resolver problemas de alta dificultad algorítmica.
  • CEE3.3 - Capacidad para entender las necesidades computacionales de problemas de disciplinas distintas de la informática y efectuar contribuciones significativas en equipos multidisciplinares que usen la computación.

    • Competencias Técnicas Genéricas

    Genéricas

  • CG1 - Capacidad para aplicar el método científico en el estudio y análisis de fenómenos y sistemas en cualquier ámbito de la Informática, así como en la concepción, diseño e implantación de soluciones informáticas innovadoras y originales.
  • CG3 - Capacidad para el modelado matemático, cálculo y diseño experimental en centros tecnológicos y de ingeniería de empresa, particularmente en tareas de investigación e innovación en todos los ámbitos de la Informática.

    • Competencias Transversales

    Razonamiento

  • CTR6 - Capacidad de razonamiento crítico, lógico y matemático. Capacidad para resolver problemas dentro de su área de estudio. Capacidad de abstracción: capacidad de crear y utilizar modelos que reflejen situaciones reales. Capacidad de diseñar y realizar experimentos sencillos, y analizar e interpretar sus resultados. Capacidad de análisis, síntesis y evaluación.

    • Básicas

  • CB6 - Que los estudiantes sepan aplicar los conocimientos adquiridos y su capacidad de resolución de problemas en entornos nuevos o poco conocidos dentro de contextos más amplios (o multidisciplinares) relacionados con su área de estudio.
  • CB8 - Que los estudiantes sepan comunicar sus conclusiones y los conocimientos y razones últimas que las sustentan a públicos especializados y no especializados de un modo claro y sin ambigüedades.
  • CB9 - Que los estudiantes posean las habilidades de aprendizaje que les permitan continuar estudiando de un modo que habrá de ser en gran medida autodirigido o autónomo.

    • Objetivos

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

    Contenidos

    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.

    Actividades

    Actividad Acto evaluativo


    Learning the design flow of a VLSI circuit


    Objetivos: 1
    Teoría
    1h
    Problemas
    1h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    1h

    Learning of algorithms for logic synthesis


    Objetivos: 1 2
    Teoría
    7h
    Problemas
    8h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    16h

    Learning of techniques for formal verification of circuits


    Objetivos: 1 2
    Teoría
    4h
    Problemas
    5h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    10h

    Learning of techniques for circuit floorplanning and placement


    Objetivos: 1 3
    Teoría
    6h
    Problemas
    7h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    15h

    Learning of routing algorithms



    Teoría
    6h
    Problemas
    6h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    14h

    Assignment on physical synthesis


    Objetivos: 3 4
    Semana: 8 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Assignment on logic synthesis


    Objetivos: 1 2 4
    Semana: 12 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    EDA project

    The student will have to implement an algorithm to solve a specific Electronic Design Automation (EDA) problem
    Objetivos: 1 4 5
    Semana: 2 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Final exam



    Semana: 18 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Metodología docente

    Los contenidos teóricos de la asignatura se imparten en las clases de teoría. En las clases de problemas se resuelven ejemplos prácticos y se proponen problemas que los estudiantes deben resolver en las horas de aprendizaje autónomo. Durante el curso también se planteará un proyecto algorítmico que los estudiantes tendrán que resolver e implementar durante sus horas de Aprendizaje Autónomo.

    Método de evaluación

    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).

    Bibliografía

    Básico

    Capacidades previas

    Experiencia en estructuras de datos y algoritmos, con especial énfasis en algoritmos de grafos.