Eines
Laboratori
24 eines per jugar amb els conceptes: canvia els números i mira què passa. També les trobaràs dins dels capítols on toquen.
Paral·lelisme
Llei d’Amdahl
Prova amb un 95% de codi paral·lel: amb 256 processadors, quant guanyes?
Surt a: PAR 2.2 Fracció paral·lelitzable i llei d'Amdahl
Sp = 1 / ((1 − φ) + φ/p). La part que no es pot paral·lelitzar posa un sostre: encara que tinguis infinits processadors, no passaràs mai de 1/(1 − φ).
real ideal (Sp = p) sostre
Graf de dependències (TDG)
Canvia el cost de les tasques i mira com es mou el camí crític i quants processadors calen.
Surt a: PAR 2.1 Construcció d'un Task Dependence Graph (TDG)
Clica una tasca per canviar-ne el cost. En corall, el camí crític.
Execució ASAP: cada tasca comença quan han acabat totes les que necessita.
Descomposició de dades
Compara el cyclic amb els blocs alineats a línia de cache: quantes línies tenen false sharing?
Surt a: PAR 5.2 Estratègies geomètriques · PAR 5.3 Padding contra el false sharing
línia de cache escrita per més d'un fil
Coherència de cache
Fes que P0 llegeixi i després escrigui, amb MSI i amb MESI, i compara quantes transaccions surten al bus.
Surt a: PAR 4.3 UMA/SMP amb snooping
M modificada · E exclusiva (només MESI) · S compartida · I invàlida
Condició de carrera
Fes que els dos fils llegeixin x abans que cap l’escrigui. Després prova-ho amb critical i atomic.
Surt a: PAR 1.5 Problemes del paral·lelisme · PAR 3.6 Protegir problemes de concurrència
Descomposició recursiva
Compara quantes tasques creen leaf i tree, i mira què fa el cut-off.
Surt a: PAR 3.8 Descomposició recursiva
crida que és una tasca crida dins d'una tasca (seqüencial) crida que fa el fil que crea les tasques
Test-and-set i test-and-test-and-set
Puja el nombre de processadors i mira com creix el trànsit al bus amb cada versió.
Surt a: PAR 4.7 Sincronització de baix nivell
// test-and-set
while (test_and_set(&lock) == 1) ;
// test-and-test-and-set
do {
while (lock == 1) ; // espera llegint la còpia de la cache
} while (test_and_set(&lock) == 1);Granularitat
Puja el cost de crear una tasca i mira com es desplaça la millor mida de tasca.
Surt a: PAR 2.5 Granularitat · PAR 3.7 Descomposició iterativa de bucles
Eix horitzontal: mida de tasca (escala logarítmica). Corall: el temps; ratllada: el temps ideal n/p; punt fosc: la millor mida.
Tp = (n/b)·tcreació + ⌈(n/b)/p⌉·b.
First touch en NUMA
Inicialitza en seqüencial i calcula en paral·lel. Després inicialitza en paral·lel: on van les pàgines?
Surt a: PAR 4.5 La política first touch
Cada quadre és una pàgina de memòria, al node on l'ha posada el first touch. Plena: la fa servir un fil del mateix node. Ratllada: la fa servir un fil de l'altre node (accés remot).
Escalabilitat forta i feble
Amb un 95% de codi paral·lel, compara el speed-up fort i el feble amb 256 processadors.
Surt a: PAR 2.3 Escalabilitat
feble (Gustafson): S = (1 − φ) + φ·p forta (Amdahl): S = 1 / ((1 − φ) + φ/p)
Amb escalabilitat forta, la part seqüencial pesa cada vegada més i el speed-up es planta. Amb escalabilitat feble, fas un problema més gran en el mateix temps: la part seqüencial queda petita al costat de la feina total.
Dependències amb depend
Canvia la T4 de inout a in: quines dependències desapareixen?
Surt a: PAR 1.5 Problemes del paral·lelisme · PAR 3.4 Dependències en OpenMP
Clica una casella per anar canviant entre —, in, out i inout.
RAW: la tasca llegeix el que una altra ha escrit (dependència real). WAR: escriu el que una altra havia de llegir abans. WAW: totes dues escriuen; ha de quedar el valor de l'última.
EDA, PRO1 i PRO2
Algorismes d’ordenació
Prova el quicksort amb un vector que ja està ordenat: per què fa tantes comparacions?
Surt a: EDA 2.3 Mergesort · EDA 2.4 Quicksort · PRO1 5.3 Algorismes d'ordenació
Arbres binaris de cerca i recorreguts
Insereix 1, 2, 3… 7 en ordre amb i sense AVL, i mira el recorregut en inordre.
Surt a: EDA 3.3 Arbres binaris de cerca · EDA 3.4 Arbres AVL · PRO2 3.1 Arbres binaris · PRO2 3.2 Recorreguts d'arbres
Grafs: BFS, DFS, Dijkstra, Prim i Kruskal
Compara l’arbre de BFS amb el de Dijkstra des del mateix origen. Després mira com Prim i Kruskal arriben al mateix arbre per camins diferents.
Surt a: EDA 5.2 BFS i DFS · EDA 5.4 Dijkstra · EDA 5.5 Prim i Kruskal
Clica un vèrtex per triar l'origen (ara: A).
Ordre de visita:
Teorema mestre
Compara mergesort, Karatsuba i Strassen: quin és el cas de cadascun?
Surt a: EDA 1.4 Recurrències i teorema mestre · EDA 2.1 L'esquema de dividir i vèncer
Si k < α: domina la recursió, Θ(nα). Si k = α: hi ha un factor log n de més, Θ(nk log n). Si k > α: domina el treball de cada crida, Θ(nk).
Taules de hash
Insereix 0, 7, 14 i 21 amb m = 7. Després canvia m a 8. Què ha passat?
Surt a: EDA 3.2 Taules de hash
h(k) = k mod 7
Heaps
Insereix un 1 i mira com sura. Després treu el mínim unes quantes vegades: surten ordenats?
Surt a: EDA 4.2 Heaps · EDA 4.3 Heapsort
Al vector, els fills de la posició i són a 2i+1 i 2i+2, i el pare a ⌊(i−1)/2⌋. Cada pare és més petit que els seus fills, així que el mínim és sempre a l'arrel.
Backtracking: les n reines
Amb n = 6, compta quantes posicions prova el backtracking i compara-ho amb la força bruta.
Surt a: EDA 6.1 Backtracking
void reines(int fila) {
if (fila == n) { solucio(); return; }
for (int col = 0; col < n; col++) {
if (pot_anar(fila, col)) { // poda: no l'ataca cap reina
posa(fila, col);
reines(fila + 1);
treu(fila, col); // tornada enrere
}
}
}Piles i cues
Fes tres push i un pop amb una pila i amb una cua: quin element surt en cada cas?
Surt a: PRO2 2.1 Piles · PRO2 2.2 Cues
Aplicació: parèntesis aparellats amb una pila
Com creix el cost
Amb n = 50, quant trigaria un algorisme Θ(2ⁿ)? I un Θ(n³) amb n = 100.000?
Surt a: EDA 1.1 Cost d'un algorisme · EDA 1.2 Anàlisi asimptòtica
| Cost | Operacions | Temps (109 op/s) |
|---|
La pila de crides
Compara fib(6) amb factorial(6): quantes crides fa cadascuna, i fins on creix la pila?
Surt a: PRO2 5.1 Correctesa de programes recursius · PRO1 4.1 Funcions recursives · PRO1 4.2 Disseny recursiu
Introducció als Computadors
Bits, naturals i complement a 2
Suma 100 i 100 amb 8 bits: què passa com a naturals i què passa en Ca2?
Surt a: IC 1.2 Naturals en binari · IC 1.3 Enters en complement a 2
Clica un bit per canviar-lo. A sota de cada bit, el seu pes.
Suma
Expressions booleanes i taules de veritat
Escriu l’expressió d’un multiplexor 2 a 1 i mira’n la taula. Després prova «Per simplificar»: quant es redueix?
Surt a: IC 2.1 Portes lògiques i àlgebra de Boole · IC 2.2 Síntesi de circuits combinacionals
Minterms
Suma de productes canònica
Simplificada
NOT: a' o !a · AND: ab, a·b, a*b o a&b · OR: a + b o a|b · XOR: a ^ b · constants 0 i 1. (Per al multiplexor, la variable s fa de selecció.)
Autòmat de Moore: detector de seqüència
Amb el detector de 101, entra 1, 0, 1, 0, 1. Quantes vegades surt un 1? Per què la segona vegada només calen dos bits més?
Surt a: IC 3.3 Autòmats de Moore
Cada estat Sq vol dir «porto q bits del patró». La sortida (sota el nom de l'estat) només depèn de l'estat: això és el que fa que sigui de Moore. Les transicions marquen amb quin bit s'hi va.