Programació Conscient de l'Arquitectura

Esteu aquí

Crèdits
6
Tipus
Complementària d'especialitat (Enginyeria de Computadors)
Requisits
  • Prerequisit: AC
Departament
AC
Assignatura molt pràctica que té com objectiu principal l'aprenentatge de técniques de programació per "l'optimització" (reducció del temps d'execució) d'aplicacions; considerant l'arquitectura del computador i el que pot fer el compilador, utilitzant eines de mesura i anàlisi i eines d'alt nivell de desenvolupament de hardware específic des de codi C.

Professors

Responsable

  • Daniel Jimenez Gonzalez ( )

Hores setmanals

Teoria
1
Problemes
1
Laboratori
2
Aprenentatge dirigit
0.4
Aprenentatge autònom
5.6

Competències

Competències Transversals

Emprenedoria i innovació

  • G1 - Conèixer i comprendre l'organització d'una empresa i les ciències que regeixen la seva activitat; capacitat de comprendre les regles laborals i les relacions entre la planificació, les estratègies industrials i comercials, la qualitat i el benefici. Desenvolupar la creativitat, l'esperit emprenedor i la tendència a la innovació.
    • G1.3 - Ser resolutiu. Utilitzar coneixements i habilitats estratègiques per a la creació i la gestió de projectes, aplicar solucions sistèmiques a problemes complexos, i dissenyar i gestionar la innovació en la organització. Demostrar flexibilitat i professionalitat en el desenvolupament de la seva feina.

Competències Tècniques de cada especialitat

Especialitat enginyeria de computadors

  • CEC2 - Analitzar i avaluar arquitectures de computadors incloent plataformes paral·leles i distribuïdes, i desenvolupar i optimitzar software per a aquestes plataformes.
    • CEC2.2 - Programar considerant l'arquitectura hardware, tant en assemblador com en alt nivell.
    • CEC2.3 - Desenvolupar i analitzar software per a sistemes basats en microprocessadors i les seves interfícies amb usuaris i altres dispositius.
  • CEC3 - Desenvolupar i analitzar hardware i software per a sistemes encastats i/o de molt baix consum.
    • CEC3.1 - Analitzar, avaluar i seleccionar les plataformes hardware i software més adients per al suport d'aplicacions encastades i de temps real.
    • CEC3.2 - Desenvolupar processadors específics i sistemes encastats; desenvolupar i optimitzar el software d'aquests sistemes. 

Objectius

  1. Seguir una metodologia d'optimització per a reduir el temps d'execució d'una aplicació en un processador determinat; primerament identificant les parts més costoses, després evaluant si val la pena o no (llei d'Amdahl) la seva optimizació, i finalment realitzant l'optimització i evaluar si s'ha tret prou rendiment com per incorporar-la a l'aplicació.
    Related competences: CEC2.3, CEC2.2,
  2. Identificar i reconèixer les optimitzacions que el compilador pot fer, ja sigui pel coneixement bàsic que es tingui del compilador com el gcc, de l'analisi del codi assemblador generat, o perque es fa "profiling" o instrumentació.
    Related competences: CEC2.3, CEC3.2, CEC3.1,
  3. Escollir les eines i les seves opcions més adients per a generar el codi binari, analitzar el codi binari generat i analitzar l'execució de l'aplicació ("profiling", instrumentació, "trace"), a més d'escollir les mètriques per fer aquest analisi i l'entorn més adient per fer l'avaluació.
    Related competences: G1.3, CEC2.3, CEC3.1,
  4. Definir latència, latència de repetició i "throughput" d'una instrucció, i aplicar aquest coneixement en l'optimització dels seus codis per escollir l'operació més adient en cada cas.
    Related competences: CEC3.2, CEC2.2,
  5. Aplicar correctament tècniques d'optimització per reduir i/o evitar operacions de llarga latència, reduint el temps d'execució de l'aplicació.
    Related competences: G1.3, CEC3.2, CEC2.2,
    Subcompetences:
    • Aplicar la tècnica de "bithacks" per a reduir/evitar operacions de llarga latència
    • Especialitzar el codi de les aplicacions per a reduir/evitar operacions de llarga latència.
    • Aplicar la tècnica de "memoization" per a reduir/evitar operacions de llarga latència
    • Reduir el "overhead" total de les crides al sistema operatiu i llibreries.
  6. Reduir el temps destinat als salts en un codi, aplicant tècniques que redueixen el nombre de salts.
    Related competences: G1.3, CEC3.2, CEC2.2, CEC3.1,
    Subcompetences:
    • Aplicar la tècnica de "inlining".
    • Canviar l'ordre d'avaluació de les condicions per a reduir, en mitja, el temps d'execució d'una aplicació.
    • Aplicar la tècnica de "code hoisting".
    • Aplicar les tècniques de "loop unrolling", "loop fusion" and "loop collapsing".
    • Aplicar altres tècniques com "memoization", "bithacks", etc. per reduir el nombre de salts.
  7. Caracteritzar la jerarquia de memòria del computador amb el que treballa ja sigui documentant-se amb manuals o ja sigui estudiant-lo empíricament amb codis i eines de profiling i tracing.
    Related competences: CEC2.3,
  8. Aplicar correctament tècniques d'optimització per fer un ús més eficient de la jerarquia de memòria del processador, reduint el temps d'execució de l'aplicació.
    Related competences: G1.3, CEC3.2, CEC2.2,
    Subcompetences:
    • Detectar i evitar posibles "data aliasing" per ajudar la tasca del compilador.
    • Aplicar optimitzacions per aprofitar l'amplada de banda de memòria.
    • Aplicar correctament tècniques d'optimització per millorar l'explotació de la localitat de dades.
  9. Identificar si un codi és vectoritzable i vectoritzar-lo si això significa una reducció del temps d'execució de l'aplicació.
    Related competences: CEC3.2, CEC2.2, CEC3.1,
    Subcompetences:
    • Aplicar correctament les tècniques d'optimització de codis escalars també sobre codis vectorials.
  10. Analitzar i indentifcar si un codi pot ser accelerat amb un "hardware" específic i utilitzar les eines d'alt nivell disponibles a l'assignatura per definir aquest hardware específic des de codi C amb pragmes molt senzilles.
    Related competences: G1.3, CEC3.2,
  11. Analitzar i optimitzar una aplicació de mida mitjana durant tot el curs, aplicant la metodologia d'optimització i les tècniques d'optimitzacions seguides a l'assignatura, en coordinació amb el reste de membres del seu equip.
    Related competences: G1.3, CEC2.2,
  12. Liderar un grup d'estudiants per a obtenir la solució més adient a un problema d'optimització o d'anàlisi donat, considerant les solucions del reste de membres del seu equip de treball i després d'una discusió entre tots els membres de l'equip.
    Related competences: G1.3,

Continguts

  1. Introducció: Programació conscient de l'arquitectura
    Que entenem per programació consicent de l'arquitectura i en quins casos val la pena fer-ho. Estratègies d'optimització. Avaluació del rendiment.
  2. Eines de programació i optimització
    Mesura del rendiment dels programes. Opcions de compilació. Estudi del comportament dinàmic dels programes. Ús d'eines d'alt nivell per accelerar (optimitzar) amb hardware algunes parts del programa a partir de codi C.
  3. Operacions de llarga latència
    Alternatives a algunes operacions de cost d'execució elevat i/o llarga latència. Substitució d'operacions complexes per operacions més senzilles. Memorització de resultats. Detecció de casos trivials. Us dels recursos sistema operatiu.
  4. Optimització del control de fluxe
    Detecció i eliminació de salts crítics. Inlining. Desenrollat de bucles, etc.
  5. Optimitzacions conscient de la memòria
    Tamany i alineació de dades. Divisió de les dades en blocs de tamany proporcional a la memoria cache. Desambiguació de memòria. Definició de les estructures de dades i pragmas per millorar el rendiment de l'aplicación tant en hardware específic com en el processador de caràcter general.
  6. Extensions vectorials i ús de hardware específic per "vectoritzar".
    Instruccions del llenguatge màquina. Identificació de codis que es poden vectoritzar. Inserció de codi vectorial en codi C.
    Use d'eines d'alt nivell per accelerar (optimitzar) amb hardware les parts del programa amb un % de temps molt elevat de consum de temps, dintre de sistemes SoC amb processadors ARM, utilitzant la mateixa idea de la vectorització.

Activitats

Activitat Acte avaluatiu


Introducció a la programació conscient de l'arquitectura

Participar activament en una sessió de classe expositiva-participativa de 2 hores de teoria i problemes. (2 hores). Estudiar a casa el tema assignat i realitzar els exercicis que s'hagin proposat com a treball autònom.
Objectius: 1
Continguts:
Teoria
1h
Problemes
0h
Laboratori
2h
Aprenentatge dirigit
0h
Aprenentatge autònom
1h

Eines de programació i optimització

Participar activament en una sessió de classe expositiva-participativa de 2 hores de teoria i problemes. (2 hores). Estudiar a casa el tema assignat i realitzar els exercicis que s'hagin proposat com a treball autònom.
Objectius: 2 3 10
Continguts:
Teoria
2h
Problemes
2h
Laboratori
6h
Aprenentatge dirigit
0h
Aprenentatge autònom
10h

Operacions de llarga latència

Participar activament en una sessió de classe expositiva-participativa de 2 hores de teoria i problemes. (2 hores). Estudiar a casa el tema assignat i realitzar els exercicis que s'hagin proposat com a treball autònom.
Objectius: 1 2 4 5 12
Continguts:
Teoria
2h
Problemes
2h
Laboratori
4h
Aprenentatge dirigit
0h
Aprenentatge autònom
9h

Optimització del control de fluxe

Participar activament en una sessió de classe expositiva-participativa de 2 hores de teoria i problemes. (2 hores). Estudiar a casa el tema assignat i realitzar els exercicis que s'hagin proposat com a treball autònom.
Objectius: 1 2 3 6 12 10
Continguts:
Teoria
3h
Problemes
2h
Laboratori
6h
Aprenentatge dirigit
0h
Aprenentatge autònom
18h

Control 1-T

Temes 1-3.
Objectius: 1 2 3 4 5 7 10
Setmana: 7
Tipus: examen de teoria
Teoria
1h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
2h

Control-1-P

Temes 1-3
Objectius: 1 2 3 4 5 7 10
Setmana: 7
Tipus: examen de problemes
Teoria
0h
Problemes
1h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
2h

Optimitzacions conscient de la memòria

Participar activament en una sessió de classe expositiva-participativa de 2 hores de teoria i problemes. (2 hores). Estudiar a casa el tema assignat i realitzar els exercicis que s'hagin proposat com a treball autònom.
Objectius: 1 2 3 8 7 12 10
Continguts:
Teoria
2h
Problemes
3h
Laboratori
6h
Aprenentatge dirigit
0h
Aprenentatge autònom
14h

Extensions vectorials i ús de hardware específic

Participar activament en una sessió de classe expositiva-participativa de 2 hores de teoria i problemes. (2 hores). Estudiar a casa el tema assignat i realitzar els exercicis que s'hagin proposat com a treball autònom.
Objectius: 1 2 3 9 12 10
Continguts:
Teoria
3h
Problemes
4h
Laboratori
6h
Aprenentatge dirigit
0h
Aprenentatge autònom
22h

Control 2-T

Tots els temes. Més centrat en temes 5-6, però pot sortir qualsevol concepte previ.
Objectius: 1 2 3 4 5 6 8 7 9 11 12 10
Setmana: 14
Tipus: examen de teoria
Teoria
1h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
2h

Control-2-P

Tots els temes. Més centrat en temes 4-6 però pot sortir qualsevol concepte previ.
Objectius: 1 2 3 4 5 6 8 7 9 11 12 10
Setmana: 14
Tipus: examen de problemes
Teoria
0h
Problemes
1h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
2h

Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
3h
Aprenentatge autònom
2h

Examen Final

Examen Final. Fora d'horari de classe.
Objectius: 1 2 3 4 5 6 8 7 9 11 12 10
Setmana: 15 (Fora d'horari lectiu)
Tipus: examen final
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
3h
Aprenentatge autònom
0h

Metodologia docent

Classes de teoria orientades a exposar conceptes bàsics d'arquitectura de processadors i metodologia d'optimització i eines; intercalant petits problemes a resoldre a classe.

Per a cada tema, una série d'exercicis teòrico-pràctics es proposaran per a que els alumnes el resolguin i ho pengin en foros creats pel professor a Atenea. El problemes a resoldre en els foros serán d'una dificultat mitjana i orientats a facilitar l'activitat a laboratori, és a dir, que serviran de treball previ també.
Es crearan equips de treball d'aproximadament 5 alumnes. S'intentara que el número de persones per equip sigui igual al número de problemes assignats per tema, i serà fixe per a tot el curs. En un principi, s'assignaran un mínim de 5 problemes per equip i tema.


La metodologia per a resoldre aquests problemes consta d'un treball personal i un treball en equip. Bàsicament consistirà en: (1) resoldre individualment els problemes demanats per aquell tema i penjar el problema resolt a un foro que el professor crea per a cada equip, (2) discutir al foro del equip de les solucions individuals (primer feedback que obtindran els alumnes) i acordar una solució per a cada problema i (3) penjar la solució final acordada a cada problema en un equip a un foro de solucions finals comú a tots els equips. A cada equip, cada estudiant serà responsable d'un problema, i és aquest alumne el que penjarà la solució final d'aquell problema al foro comú abans d'una data concreta. El professor revisarà aquestes solucions finals (segon feedback) però també pot revisar els foros de discusió de les solucions individuals.

A les classes de problemes es faran activitats en equip i es discutiran amb tots els equips les solucions obtingudes (tercer feedback).
Per facilitar que els alumnes puguin comparar les seves solucions amb les de la resta d'alumnes de l'assignatura, els foros seran oberts a tothom. A més, l'assignatura ofereix un portal web on els alumnes podran enviar la solució de determinats exercicis de l'assignatura. El portal s'encarregarà d'executar els programes, comprovar la seva correctesa i d'ordenar els programes presentats pels alumnes considerant el temps d'execució.

Les classes de laboratori serviran de suport a la teoria i de comprobació empírica dels exercicis fets a classe de problemes. Els alumnes disposaran de la informació de pràctiques abans de cada sessió. La realització d'aquestes pràctiques es farà íntegrament en les hores de laboratori assignades. Les pràctiques es dividiran en dos grups: experiments d'abast limitat per il.lustrar aplicacions i optimitzacions determinades, i altres en que caldrà aplicar tots els coneixements adquirits per optimitzar una aplicació complerta.

Al final de l'ultima sessió de laboratori de cada tema, els alumnes disposaran d'un temps per a entregar alguns del exercicis fets al laboratori.

Mètode d'avaluació

A l'avaluació de l'estudiant intervenen 5 components:

(1) Pràctiques del Laboratori: L - 40% de la nota de l'assignatura.

Hi ha una pràctica per cada tema que pot durar més d'una sessió de laboratori. Cada pràctica tindrà un pes del 20% del laboratori.

L = 0.2*L2+0.2*L3+0.2*L4+0.2*L5+0.2*L6

La solució dels exercicis del laboratori serà un informe breu (entre 1 i 5 pàgines), codis fonts i scripts que hauran de ser entregat al professor via Racó. El professor avaluarà aquest l'informe. També és possible que alguns codis s'hagin d'enviar a un servidor per comprovar que compilen i que acceleren correctament l'aplicació.

(2) Exercicis de classe de problemes: P - 10% de la nota de l'assignatura.

Aquests exercicis són demanats pel professor a classe de problemes, i s'han de treballar en equip i presentar als foros de Atenea o via Racó.

(3) Nota de Controls parcials: C - 50% de la nota de l'assignatura

Al llarg del curs els alumnes hauran de fer 2 controls: C1, C2. El seu objectiu és avaluar si l'alumne/a ha aconseguit assimilar les optimitzacions de codi explicades fins el moment.

C = 0.35*C1+0.65*C2.


(4) Nota d'Examen final: F

A l'examen final es preguntaran casos pràctics i teòrics. Aquest examen només és obligatori per aquells alumnes que no han assolit una nota d'aprovat en els controls (C>=5)

(5) Nota Extra de Challenge: cha

Challenge : Es proposarà un exercici d'optimització a entregar mitjançant un portal web d'execució o via Racó on es premiaran les solucions més ràpides. Els alumnes que presentin les 10 solucions més ràpides veuran incrementada la seva nota final en 1 punt (solució més ràpida), 0.9 punts (segona solució més ràpida),... i 0.1 punts (desena solució més ràpida) respectivament.
Aquesta puntuació adicional només s'aplicarà quan l'estudiant aprovi per C (C>=5.0).


L'assignatura es pot aprovar de dues formes:
===========================================

La nota d'examens (NEx) es pot aconseguir de dues formes, bé per avaluació continuada o bé per examen final:

Si (C >= 5)
NEx = MAX(C, F)
altrament:
NEx = MAX(0.25*C+0.75*F, F)

La Nota Final és:

Nota Final = MIN(0.50 * NEx + 0.10 *P + 0.40 * L + cha, 10)

La competència transversal s'avalua a cada estudiant considerant el seu treball en equip, lideratge en trobar solucions eficients, alternatives, creatives i innovadores als problemes a resoldre dels quals l'estudiant sigui responsable. És a dir, s'avaularà la seva capacitat de trobar una solució que sigui una combinació exitosa de les solucions trobades per un problema, o la millor solució. També formarà part d'aquesta avaluació la seva participació en trobar solucions creatives a problemes que no sigui responsable.

Bibliografia

Bàsica:

Capacitats prèvies

Les previstes pels requisits.