Diario delle lezioni - Primo modulo (SC1) - Canale AO

I video delle lezioni a partire dal 10 ottobre sono disponibili sul canale Youtube del DIAG. Il codice sviluppato in aula è disponibile al seguente link condiviso.

Martedì 4 ottobre 2016 (Preliminari A - 90 min) - Coppa

• Introduzione al corso: principali argomenti trattati ed obiettivi
• Ambiente Linux:
  • Struttura di base del filesystem (Appendice B): struttura ad albero, root, home, path assoluti e relativi, file "." e "..", "~", case-sensitivity, file nascosti
  • Shell bash
  • Variabili di ambiente e tipologia di comandi: PATH, env, .bashrc, comandi built-in, comandi esterni, type
  • Permessi rwx/ugo: chmod
  • Comandi di base (Appendice C): cd, ls, pwd, mkdir, rmdir, rm, cp, mv, touch
  • Link simbolici: ln -s

Giovedì 6 ottobre 2016 (Preliminari B, C - 180 min) - Coppa

• Ambiente Linux:
  • Permessi rwx: notazione ottale
  • Comandi di base (Appendice C): cat, less, head, tail, man, grep, whereis, which, opzione --help
  • stdin, stdout, stderr, redirezione, shell pipe (esempio: sort)
  • processi in background (&, CTRL+z) e foreground (fg), terminazione processo (jobs, ps, kill, CTRL+c), overview processi attivi (top)
• Compilazione di programmi in ambiente Linux: gcc
• Programmi C con parametri di input: argc/argv
• Riepilogo su allocazione memoria: memoria allocata in stack vs memoria allocata dinamicamente (malloc/free) in heap
• Errori comuni: puntatore non inizializzato, offset by 1, memory leak, accesso a memoria deallocata (stack o heap), double free, conditional jump depends on uninitialised value
• Debugging tools (aka "come sopravvivere al C"):
  • Informazioni di debugging nella compilazione: gcc -g
  • Valgrind: memory leaks, invalid accesses
  • GDB: inserire un breakpoint, ispezionare lo stato di esecuzione

Venerdì 7 ottobre 2016 (Esercitazione 1 - 120 min) - Coppa/D'Elia

• Esercitazione in laboratorio: debugging con Valgrind e GDB | soluzioni

Lunedì 10 ottobre 2016 (Lezione 1 - 90 min) - Demetrescu

[ Video ]:

• Architettura di Von Neumann: CPU, bus, I/O bridge, memoria, controller e adattatori
• CPU: ALU, registri, unità di controllo, ciclo fetch-decode-execute, classi di istruzioni
• Instruction Set Architecture (ISA), linguaggio macchina e linguaggio assembly
• Pipeline di compilazione C: preprocessore -> compilatore -> assemblatore -> linker, opzioni corrispondenti in gcc ed estensioni dei file intermedi (.c, .i, .s, .o)
• Comando file per ispezionare il tipo di file
• Analisi dell'output di ls -l: flag x settato sui file eseguibili
• Disassembler: objdump e opzione -d

Giovedì 13 ottobre 2016 (Lezioni 2, 3 - 180 min) - Demetrescu

[ Video parte I ]:

• Astrazioni nei sistemi di calcolo: ruolo dell'ISA
• Registri IA32 come contenitori per variabili: registri IP (index pointer/program counter), BP (base pointer), SP (stack pointer) e registri dati A, B, C, D, DI, SI
• Sintassi Assembly AT&T: operandi immediati ($10, $0xCAFE, ecc.), nomi dei registri (%eax, %ax, %al, ecc.), suffissi delle istruzioni (b, w, l, ecc.)
• Richiami sulla conversione esadecimale/binario
• Traduzione C -> Assembly IA32
  • Corrispondenza tra tipi di dato C (char, short, int, ecc.) e tipi di dato macchina (Byte, Word, Long Word, ecc.)
  • Istruzione di assegnamento: istruzione movimento dati MOV (=)
  • Operatori aritmetico-logici: istruzioni INC (++), DEC (--), ADD (+), SUB (-), IMUL (*), NEG (-), AND (&), OR (|), XOR (^), NOT (~)

[ Video parte II ]:

• Esempi di traduzione di assegnamenti e calcolo di espressioni aritmetiche
• Scrittura di file .s, direttiva .globl
• Linking di moduli .s e moduli .c mediante gcc

Lunedì 17 ottobre 2016 (Lezione 4 - 90 min) - Demetrescu

[ Video ]:

• Tipologia operandi di una istruzione: immediato (solo per operando sorgente), registro, memoria
• Vincolo IA32: al più uno degli operandi di una istruzione può essere di tipo memoria
• Scrittura di file .s: etichette, commenti #
• Traduzione C -> Assembly IA32
  • lettura dei parametri dallo stack frame del chiamante:
    • stack frame: indirizzo di ritorno, System V ABI calling convention del C per passaggio parametri in stack e valore di ritorno
    • convenzione su stack crescente verso il basso e indirizzi crescenti verso l'altro
    • indirizzamento indiretto con registro (base) e spiazzamento: imm(reg) (es. 4(%esp))
  • costrutti if e if ... else: trasformazione basata su goto e traduzione IA32 mediante CMP, Jcc, JMP, condition code (e, ne, l, le, g, ge, b, be, a, ae)

Giovedì 20 ottobre 2016 (Lezioni 5, 6 - 180 min) - Demetrescu

[ Video parte I ]:

• Traduzione programmi C -> assembly IA32 (sintassi AT&T)
  • esercizi svolti: funzione che calcola il massimo di due numeri
  • registro EFLAGS, cenni ai flag ZF, SF, OF, CF, relazione con i condition code, side-effect sui flag delle operazioni aritmetico logiche, CMP S, D come calcolo della differenza D-S
  • iterazione, costrutto while
  • esempi di iterazione: calcolo della somma dei primi n numeri
  • uso del debugger gdb per l'analisi di programmi misti C/assembly IA32

[ Video parte II ]:

• Traduzione programmi C -> assembly IA32 (sintassi AT&T)
  • promozione intera nel passaggio dei parametri in C -> accesso a 32 bit ai parametri formali di tipo char e short in IA32
  • indirizzi di memoria: modello a 32 e 64 bit, word size
  • tipi puntatore -> IA32 Double Word
  • array e aritmetica dei puntatori -> indirizzamento a memoria con base, indice e scala (es. (%eax, %ecx, 4))
  • esempi: modifica di un intero passato per indirizzo, modifica dell'i-esimo elemento di un array di int, short e char, con i costante e variabile, swap di due oggetti in memoria

Venerdì 21 ottobre 2016 (Esercitazione 2 - 120 min) - Coppa/D'Elia/Demetrescu

• Esercitazione in laboratorio: traduzione da C ad assembly IA-32 (parte I) | soluzioni

Lunedì 24 ottobre 2016 (Lezione 7 - 90 min) - Demetrescu

[ video ]

• Traduzione programmi C -> assembly IA32 (sintassi AT&T)
  • esercizi svolti: funzione che verifica l'uguaglianza di due stringhe C
  • calling convention System V: registri callee-save e caller save, istruzioni PUSH, POP (semantica e uso)
  • chiamata e ritorno da funzione -> istruzioni CALL e RET (semantica e uso)

Giovedì 27 ottobre 2016 (Lezioni 8, 9 - 180 min) - Demetrescu

[ video parte I ]

• Traduzione programmi C -> assembly IA32 (sintassi AT&T)
  • variabili locali (parte II), passaggio dei parametri -> allocazione della memoria nello stack frame
  • conversioni di tipo intero (type cast) -> istruzioni MOVZ e MOVS (parte I)

[ video parte II ]

• Traduzione programmi C -> assembly IA32 (sintassi AT&T)
  • conversioni di tipo intero (type cast), promozione intera -> istruzioni MOVZ e MOVS (parte II)
  • operatori relazionali ed espressioni booleane -> istruzioni logiche bitwise AND, OR, NOT, XOR e istruzione SETcc
  • esercizi svolti
• Consultazione del manuale Intel (ISA, Volume 2: Instruction Set Reference)

Giovedì 3 novembre 2016 (Lezioni 10, 11 - 180 min) - Demetrescu

[ video parte I ]

• Complementi sull'istruction set IA32:
  • assegnamento condizionato con istruzione CMOV: esempio del calcolo del massimo tra due numeri
  • istruzione XOR per azzerare un registro
  • istruzione TEST per confrontare un registro con zero
  • istruzione LEA per il calcolo di indirizzi ed espressioni: esempio del calcolo di indirizzi di variabili locali in stack e calcolo di espressioni aritmetiche
  • shift logico SHL/SHR ed aritmetico SAL/SAR: applicazione su rappresentazioni con e senza segno, moltiplicazione e divisione intera per 2^S (parte I)

[ video parte II ]

• Complementi sull'istruction set IA32:
  • shift logico SHL/SHR ed aritmetico SAL/SAR: applicazione su rappresentazioni con e senza segno, moltiplicazione e divisione intera per 2^S (parte II)
• Introduzione all'ottimizzazione dei programmi
  • risorse da ottimizzare (CPU time, memoria, energia, ecc.)
  • metriche prestazionali classiche:
    • tempo di esecuzione
    • spazio di memoria richiesto (byte allocati, memory footprint)
    • cenni ad altre metriche: energia
  • efficienza prestazionale come moneta per pagare altre qualità del software (affidabilità, usabilità, manutenibilità, portabilità, modularità, ecc.)
  • dimensioni del problema (algoritmo vs sua codifica in un linguaggio di programmazione)
  • ottimizzazioni del programmatore (algoritmo e codice) e del compilatore (codice)
• Misurazione dei tempi
  • esecuzione di un programma: comando time
  • esempi di misurazione dei tempi con time ed effetto delle ottimizzazioni dei compilatori (-O0 vs. -O1)

Venerdì 4 novembre 2016 (Esercitazione 3 - 120 min) - Coppa/D'Elia/Demetrescu

• Esercitazione in laboratorio: traduzione da C ad assembly IA-32 (parte II) | soluzioni

Lunedì 7 novembre 2016 (Lezione 12 - 90 min) - Demetrescu

[ video ]

• Svolgimento delle soluzioni dell'esercitazione del 4 novembre.

Giovedì 10 novembre 2016 (Lezioni 13, 14 - 180 min) - Demetrescu

[ video parte I ]

• Principio di Pareto, bottleneck prestazionali
• Legge di Amdahl
• Performance profiling con gprof
• Tipologia di ottimizzazione: riduzione del work (numero di istruzioni eseguite) di un programma
  • categorie: espressioni e logica del programma, loop, funzioni, strutture dati
  • ruolo del programmatore nel rendere possibili le ottimizzazioni di un compilatore
• Modifiche alle strutture dati per ottimizzare operazioni frequenti costose
  • principio dell'augmentation: esempio dell'inserimento in coda in una lista collegata, calcolo della lunghezza di una lista collegata
  • precomputation: esempio di lookup su tabella per verificare se un carattere è una consonante
• Ottimizzazione di espressioni e logica del programma
  • constant folding (CF), constant propagation (CP), common subexpression elimination (CSE), dead code elimination (DCE)
  • principio della cortocircuitazione: operatori || e && in C, esempio della ricerca sequenziale, ordinamento di test in cascata partendo dal più frequente (esempio: calcolo dei whitespace in una stringa)

[ video parte II ]

• Ottimizzazione di espressioni e logica del programma
  • identità algebriche per semplificare espressioni logiche complesse: verifica della collisione tra due cerchi senza fare ricorso a sqrt
• Ottimizzazione dei loop
  • loop-invariant code motion (loop hoisting)
  • uso delle sentinelle: ricerca di un elemento in un array
• Ottimizzazione delle funzioni
  • inlining: tecnica base e trade-off sul numero di istruzioni nel chiamato, inlining come enabler di altre ottimizzazioni
  • tail call optimization: overhead di una chiamata a funzione, tail recursion elimination, calcolo della somma dei primi n numeri con ricorsione/ricorsione coda/iterazione

Lunedì 14 novembre 2016 (Lezione 15 - 90 min) - interfaccia sistema operativo: comandi e system call

[ video ]

• Sistema operativo come:
  • ambiente per consentire l'utilizzo del calcolatore da parte degli utenti
  • ambiente di esecuzione per i programmi, fornendo risorse e servizi
• Interfaccia del sistema operativo:
  • verso l'utente:
    • interfaccia dei comandi (es. comandi shell di base ls, cat, ecc.)
    • desktop environment e server grafico (es. X, gnome, KDE), cenni
  • verso i programmi:
    • passaggio dei parametri a un programma C: argc/argv
    • stato di terminazione di un processo: exit(), return della funzione main, accesso allo stato di terminazione nella shell con $?
    • accesso alle variabili di ambiente: getenv, setenv, variabile environ
    • programmazione di sistema:
      • system call e standard POSIX
      • gestione degli errori: errno, perror
    • differenza tra librerie utente (es. libc, printf) e system call (es. write)

Giovedì 17 novembre 2016 (Lezioni 16, 17 - 180 min) - processi: PCB, memory layout, prestazioni esecuzione

[ video parte I ]

• Panoramica sui servizi principali forniti da un sistema operativo (discussione di alto livello):
  • gestione dei processi (creazione, esecuzione, comunicazione, sincronizzazione, controllo, eliminazione)
  • gestione della memoria (allocazione della memoria ai processi)
  • gestione dei file
  • gestione dei dispositivi di I/O
  • sicurezza e protezione
  • controllo delle prestazioni, accounting, gestione degli errori
• Esecuzione di un processo (parte I):
  • ciclo fetch-decode-execute (ricapitolazione)
  • aspetti prestazionali
    • clock e frequenza del processore
    • evoluzione negli ultimi decenni: legge di Moore, crescita esponenziale numero transistor, avvento delle architetture multicore

[ video parte II ]

• Dall'eseguibile al processo:
  • process control block e risorse associate ai processi: PID, registri, PID processo genitore, puntatori alla memoria, privilegi del processo, accounting (tempo speso dal processo, limiti, ecc.), priorità dello scheduling, risorse I/O (file aperti ecc.)
  • loader e anatomia dello spazio logico di un processo:
    • code, data, heap, librerie dinamiche, stack
    • caso di studio Linux/x86: ispezione immagine di un processo mediante /proc/pid/maps
• Esercizio di preparazione all'esonero: profilazione con gprof e applicazione di ottimizzazioni per ridurre il work

Venerdì 18 novembre 2016 (Esercitazione 4 - 120 min) - Coppa/D'Elia/Demetrescu

• Esercitazione in laboratorio: ottimizzazioni (cicli, funzioni, ecc.), profiling, misurazione tempo

Lunedì 21 novembre 2016 (Lezione 18 - 90 min) - pipeline e ottimizzazioni

[ video ]

• Esecuzione di un processo (parte II):
  • architetture superscalari, pipelining, hazard e stalli
  • ottimizzazioni del codice sfruttando la pipeline: istruzioni branchless, instruction scheduling
  • cenni ad esecuzione parallela: CPU multicore e instruction-level parallelism (es. AVX, pipelining)
  • cenni ad architetture CISC e RISC
  • esecuzione in modalità utente (user) e in modalità supervisore (kernel)

Giovedì 24 novembre 2016 (Lezione 19, 20 - 180 min) - trap, interrupt, context switch, implementazione system call

[ video parte I ]

• Esecuzione di un processo (parte III): [ref1, ref2]
  • flusso del controllo normale ed eccezionale
  • eccezioni recuperabili e non recuperabili
  • eccezioni sincrone (interne):
    • trap: istruzione IA32 INT, invocazione di system call (INT 0x80, passaggio dei parametri) [ref]
    • fault: es. divisione per zero
    • abort: es. parity error
  • eccezioni asincrone (esterne):
    • interrupt: dispositivi I/O, timer, ecc.
  • tabella delle eccezioni (interrupt vector)
  • cenni alla tabella delle eccezioni IA32

[ video parte II ]

• Svolgimento di esercizi per la preparazione all'esonero

Venerdì 25 novembre 2016 - Coppa/D'Elia/Demetrescu

• Prova intermedia di esonero:
  • prova al calcolatore:
    • programmazione IA32
    • profilazione delle prestazioni
    • tecniche di ottimizzazione dei programmi per ridurre il numero di istruzioni eseguite
    • debugging con gdb e valgrind
  • domande a quiz:
    • concetti di base sull'ambiente Linux (file system, shell, permessi, comandi, variabili di ambienti, canali, redirezione, pipe, ecc.)
    • architettura generale di un sistema di calcolo (Von Neumann)
    • pipeline di compilazione
    • tecniche di ottimizzazione per la riduzione del work, legge di Amdahl

Lunedì 28 novembre 2016 (Lezione 21 - 90 min) - stati processi e scheduling

[ video ]

• Esecuzione di un processo (parte IV):
  • stati di un processo: running user, running kernel, waiting (diagramma degli stati in Linux)
  • attesa di eventi: busy waiting/polling e interrupt
• Esecuzione simultanea di più processi (parte I):
  • nozione di esecuzione concorrente
  • multiprogrammazione e scheduling dei processi: [ref]
    • context switch: salvataggio dello stato della CPU nel PCB
    • altri stati di un processo: started, ready, zombie
    • esempio del time sharing round-robin mediante timer e interrupt
    • cenni allo scheduling con priorità
  • albero dei processi

Giovedì 1 dicembre 2016 (Lezione 22, 23 - 180 min) - system call processi

[ video parte I | video parte II ]

• Esecuzione simultanea di più processi (parte II):
  • system call per il controllo dei processi:
    • creazione (fork, exec)
    • terminazione (exit)
    • attesa terminazione (wait)
    • segnali (signal, kill, armatura dei segnali e signal handler)

Venerdì 2 dicembre 2016 (Esercitazione 5 - 120 min) - Coppa/D'Elia/Demetrescu

• Esercitazione in laboratorio: sviluppo di una shell, chiamate a sistema

Lunedì 5 dicembre 2016 (Lezione 24 - 90 min) - accesso a memoria e cache

[ Video ]

• Come è strutturata la memoria? (parte I) [ref1, ref2]
  • astrazione con modello lineare
  • transazioni di lettura e scrittura: configurazione del bus, trasferimenti da CPU a memoria e viceversa
  • divario tra velocità CPU (cycle time) e velocità accesso a memoria, evoluzione del trend
  • principio di località, località spaziale e temporale
  • caching come strategia di duplicazione della memoria oppure per memorizzare risultati di computazioni ricorrenti
  • cache come buffer per compensare divario tra velocità di processamento e velocità di accesso ai dati sfruttando il principio di località
    • partizionamento in blocchi, dimensione blocco (linea di cache), cache hit e cache miss, cenni a strategia di replacement
    • esempi di analisi: somma degli elementi di un array, scansione lineare di un array vs. lista collegata
  • altri usi delle cache in un sistema di calcolo (es. disco, browser)
• Complementi sull'uso dei segnali: system call sigaction

Lunedì 12 dicembre 2016 (Lezione 25 - 90 min) - gerarchie di memoria e ottimizzazioni

[ Video ]

• Come è strutturata la memoria? (parte II) [ref1, ref2]
  • gerarchie di memoria:
    • registri, cache L1 (D+I), L2, L3, memoria, disco
    • trasferimento dati a blocchi tra livelli successivi di una memoria gerarchica
    • analisi di costo/dimensione/velocità dei livelli di una memoria gerarchica
    • caso di studio: Intel Core i7, gerarchia di memoria (L1i, L1d, L2, L3, DDR3) [ref]
  • ottimizzazioni del codice nell'uso della memoria:
    • Tempo di esecuzione
      • sfruttare velocità dei registri: allocazione dei registri
      • scrittura di codice cache-friendly: caso di studio del prodotto di matrice
      • allineamento e padding:
        • stack frame a 16 byte prima di una call
        • allineamento dei campi delle struct
    • Spazio
      • ridurre la dimensione dei dati: riordinare le struct per ridurre il padding
      • ridurre la dimensione del codice: rimpiazzo di istruzioni con altre che richiedono meno byte (es. movl $1, D -> incl D)

Giovedì 15 dicembre 2016 (Lezione 26, 27 - 180 min) - allocazione dinamica e allocazione della memoria fisica

[ video parte I | video parte II ]

• Come è strutturata la memoria? (parte III)
  • Ordine dei byte in memoria (endianness)
    • storia e motivazioni, usi attuali (es. network byte order)
    • esempi di accesso a singoli byte/word in un dato memorizzato
• Come viene gestita la memoria? [ref1, ref2]
  • memoria fisica (gestita dal sistema operativo) e memoria virtuale (visibile ai processi)
  • allocazione dinamica della memoria
    • frammentazione interna ed esterna
    • qualità di un allocatore: tempo e spazio
    • allocazione in cascata della memoria
    • cenni ad implementazione di un allocatore: malloc/free, sbrk(2)
  • allocazione nella memoria fisica: memoria virtuale
    • mapping tra indirizzi virtuali e indirizzi fisici: MMU
    • paginazione
    • come avviene il mapping degli indirizzi logici su quelli fisici?
    • quanto spazio occupa una tabella delle pagine?
  • paginazione con bit di validità
  • page fault memoria virtuale e loro gestione, protection fault (SIGSEGV)
  • paginazione con bit di validità e swapping su disco
  • working set e thrashing

Venerdì 16 dicembre 2016 (Esercitazione 6 - 120 min) - Coppa/D'Elia/Demetrescu

• Esercitazione in laboratorio: ottimizzazioni accesso a memoria

[ Canale PZ (D'Elia) ]