Algorismes per a VLSI

Crèdits
6
Tipus
  • MIRI: Complementària d'especialitat (Computació Avançada)
  • MEI: Optativa
Requisits
Aquesta assignatura no té requisits , però té capacitats prèvies
Departament
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.

Professorat

Responsable

Hores setmanals

Teoria
2
Problemes
2
Laboratori
0
Aprenentatge dirigit
0
Aprenentatge autònom
7.11

Competències

Competències Tècniques de cada especialitat

Computació avançada

  • CEE3.1 - Capacitat per a identificar barreres computacionals i analitzar la complexitat de problemes computacionals en diversos àmbits de la ciència i la tecnologia; així com per representar problemes d'alta complexitat en estructures matemàtiques que puguin ser tractades eficientment amb esquemes algorítmics.
  • CEE3.2 - Capacitat per utilitzar un espectre ampli i variat de recursos algorítmics per resoldre problemes d'alta dificultat algorísmica.
  • CEE3.3 - Capacitat per entendre les necessitats computacionals de problemes de disciplines diferents de la informàtica i efectuar contribucions significatives en equips multidisciplinaris que facin servir la computació.

    • Competències Tècniques Generals

    Genèriques

  • CG1 - Capacitat per aplicar el mètode científic en l'estudi i anàlisi de fenòmens i sistemes en qualsevol àmbit de la Informàtica, així com en la concepció, disseny i implantació de solucions informàtiques innovadores i originals.
  • CG3 - Capacitat per al modelatge matemàtic, càlcul i disseny experimental en centres tecnològics i d'enginyeria d'empresa, particularment en tasques de recerca i innovació en tots els àmbits de la Informàtica.

    • Competències Transversals

    Raonament

  • CTR6 - Capacitat de raonament crític, lògic i matemàtic. Capacitat de resoldre problemes en la seva àrea d'estudi. Capacitat d'abstracció: capacitat de crear i utilitzar models que reflecteixin situacions reals. Capacitat de dissenyar i realitzar experiments senzills, i analitzar-ne i interpretar-ne els resultats. Capacitat d'anàlisi, de síntesi i d'avaluació.

    • Bàsiques

  • CB6 - Que els estudiants sàpiguen aplicar els coneixements adquirits y la seva capacitat de resolució de problemes en entorns nous o poc coneguts dins de contexts més amplis (o multidisciplinaris) relacionats amb la seva àrea d'estudi.
  • CB8 - Que els estudiants sàpiguen comunicar les seves conclusions i els coneixements i raons darreres que les sustenten- a públics especialitzats i no especialitzats d'una manera clara i sense ambigüitats.
  • CB9 - Que els estudiants posseeixin les habilitats d'aprenentatge que els permetin continuar estudiant d'una manera que haurà de ser en gran mesura autodirigida o autònoma.

    • Objectius

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

    Continguts

    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.

    Activitats

    Activitat Acte avaluatiu


    Aprenentage del fluxe de disseny d'un circuit VLSI


    Objectius: 1
    Teoria
    1h
    Problemes
    1h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    1h

    Aprenentage d'algorismes de síntesi lògica


    Objectius: 1 2
    Teoria
    7h
    Problemes
    8h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    16h

    Aprenentage de tècniques de verificació formal de circuits


    Objectius: 1 2
    Teoria
    4h
    Problemes
    5h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    10h

    Aprenentatge de tècniques per a la planificació i posicionament de components d'un circuit


    Objectius: 1 3
    Teoria
    6h
    Problemes
    7h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    15h

    Aprenentatge d'algorismes d'enrutat de senyals



    Teoria
    6h
    Problemes
    6h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    14h

    Exercicis de síntesi física


    Objectius: 3 4
    Setmana: 8 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Exercicis sobre síntesi lògica


    Objectius: 1 2 4
    Setmana: 12 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Projecte d'Automatització de Disseny Electrònic

    The student will have to implement an algorithm to solve a specific Electronic Design Automation (EDA) problem
    Objectius: 1 4 5
    Setmana: 2 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Examen final



    Setmana: 18 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Metodologia docent

    Els continguts teòrics de l'assignatura s'imparteixen a les classes de teoria. A les classes de problemes es resolen exemples pràctics i es proposen problemes que els estudiants han de resoldre en les hores d'Aprenentatge Autònom. Durant el curs també es plantejarà un projecte algorísmic que els estudiants haurà de resoldre i implementar durant les seves hores d'Aprenentatge Autònom.

    Mètode d'avaluació

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

    Bibliografia

    Bàsic

    Capacitats prèvies

    Experiència en estructures de dades i algorismes, amb èmfasi especial en algorismes de grafs.