Algorismes per a VLSI

• Hores setmanals
• Competències
• Objectius
• Continguts
• Activitats
• Metodologia docent
• Mètode d'avaluació
• Bibliografia
• Capacitats prèvies

Professorat

Responsable

• Jordi Cortadella Fortuny ( )

Hores setmanals

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

Metodologia docent

Mètode d'avaluació

Bibliografia

Bàsica:

• VLSI Physical Design: From Graph Partitioning to Timing Closure - Kahng , A.B.; Lienig, J.; Markov , I.L.; Hu, jin, Springer, 2022. ISBN: 9783030964153
  https://link-springer-com.recursos.biblioteca.upc.edu/book/10.1007/978-3-030-96415-3
• Synthesis and optimization of digital circuits - De Micheli, G, McGraw-Hill, cop. 1994. ISBN: 9780070163331
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991001096099706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Handbook of algorithms for physical design automation - Alpert, C.J.; Metha, D.P.; Sapatnekar, S.S. (eds.), CRC : Taylor & Francis, 2009. ISBN: 9780849372421
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004001299706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Electronic design automation: synthesis, verification, and test - Wang, L.-T.; Chang, Y.-W.; Cheng, K.-T. (eds.), Morgan Kaufmann Publishers/Elsevier, 2009. ISBN: 9780123743640
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003874749706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Logic synthesis and verification algorithms - Hachtel, G.D.; Somenzi, F, Kluwer Academic Publishers, 1996. ISBN: 0792397460
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991002312709706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Capacitats prèvies