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

Martedì 4 ottobre 2016 (90 min)

• Filesystem, virtual filesystem (Linux VFS e cenni a Windows IFS)
• Ambiente Linux:
  • Struttura di base del filesystem (Appendice B): Filesystem Hierarchy Standard, path assoluti e relativi
  • Classi di utenti e permessi: chmod rwx/ugo o in codifica ottale
  • Link simbolici
  • Shell: CLI vs. GUI
  • Variabili di ambiente: es. PATH, PWD
  • Comandi di base (Appendice C): pwd, type, ls

Giovedì 6 ottobre 2016 (180 min)

• Ambiente Linux
  • Shell bash: .bashrc
  • Comandi di base (Appendice C): cd, mkdir, rmdir, rm, cp, mv, ln, touch, 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 (kill, CTRL+c) e visualizzazione (jobs, ps, top) processsi
• Compilazione di programmi in ambiente Linux: gcc
• Programmi C con parametri di input: argc/argv
• Riepilogo su allocazione memoria dinamica: malloc/free
• Errori comuni nell'accesso alla memoria: puntatore non inizializzato, offset by 1, corruzione memoria
• 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 (120 min) - Coppa/D'Elia

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

Lunedì 10 ottobre 2016 (90 min)

• 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, clock e frequenza
• Instruction Set Architecture (ISA), linguaggio macchina e linguaggio assembly
• Linguaggi di alto e basso livello
• Pipeline di compilazione C: cpp, cc1, as, ld e opzioni corrispondenti in gcc
• Disassembler: objdump

Giovedì 13 ottobre 2016 (180 min)

• Compilazione vs. interpretazione, approcci ibridi (compilazione JIT, interpretazione di bytecode)
• Astrazioni nei sistemi di calcolo: ruolo dell'ISA e visione della memoria
• 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 (~)
  • Esempi di traduzione di assegnamenti e calcolo di espressioni aritmetiche

Lunedì 17 ottobre 2016 (90 min)

• 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
• Convenzione su stack crescente verso il basso e indirizzi crescenti verso l'altro
• Stack frame e chiamate a funzione: return address, calling convention del C per passaggio parametri in stack
• Indirizzamento indiretto con registro (base) e spiazzamento
• Istruzioni CMP e Jcc per salti condizionati: je (jz), jne (jnz), jg (jnle), jge (jnl), jl (jnge), jle (jng)
• Scrittura di file .s: direttiva .globl, etichette, commenti
• Traduzione C -> Assembly IA32
  • Lettura dei parametri dallo stack frame del chiamante
  • Costrutto if: trasformazione basata su goto e traduzione IA32 mediante CMP e Jcc

Giovedì 20 ottobre 2016 (180 min)

• • CMP S, D + Jcc L come salto condizionato se D cc S è verificata
• Traduzione programmi C -> Assembly IA32
  • iterazione, costrutto while, cenni al costrutto for
  • esempio di iterazione: calcolo della somma dei primi n numeri
  • dereferenziare un puntatore -> indirizzamento a memoria indiretto con registro
  • array e aritmetica dei puntatori -> indirizzamento a memoria con base, indice e scala (es. (%eax, %ecx, 4))
  • esercizi svolti su passaggio parametri, istruzioni di confronto e cicli, accesso all'i-esimo elemento di una array con i noto oppure non noto a tempo di compilazione
  • promozione intera nel passaggio dei parametri in C -> accesso a 32 bit ai parametri formali di tipo char e short in IA32
  • uso del debugger gdb per l'analisi di programmi misti C/assembly IA32

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

• Esercitazione in laboratorio: traduzione da C ad assembly IA-32 | soluzioni

Lunedì 24 ottobre 2016 (90 min)

• Traduzione programmi C -> Assembly IA32
  • C calling convention: registri callee-save e caller-save, istruzioni PUSH, POP (semantica e uso, formulazione equivalente in termini di ADD/SUB e MOV)
  • chiamata e ritorno da funzione -> istruzioni CALL e RET (semantica e uso, formulazione equivalente in termini di ADD/SUB, MOV e JMP)
  • esercizi svolti: funzione che verifica l'uguaglianza di due stringhe C, funzione per lo swap di due interi (con e senza uso di registri callee-save)
  • introduzione al passaggio dei parametri alla funzione chiamata

Giovedì 27 ottobre 2016 (180 min)

• Traduzione programmi C -> Assembly IA32
  • passaggio dei parametri -> allocazione della memoria nello stack frame, interazione con salvataggio registri caller-save
  • variabili locali ed operatore address-of &
  • conversioni di tipo intero (type cast) -> istruzioni MOVZ e MOVS
  • operazioni logiche: differenza tra istruzione bitwise AND (& in C) ed operatore logico AND (&& in C)
  • istruzione SETcc e cenni sui flag del registro EFLAGS (es. Zero Flag, Overflow Flag, Sign Flag)
  • istruzione di confronto TEST
  • esercizi svolti: azzeramento di un array di char senza usare un indice, calcolo lunghezza di una stringa utilizzando TEST

Giovedì 3 novembre 2016 (180 min)

• Complementi sull'istruction set IA32:
  • Assegnamento condizionato con istruzione CMOV: esempio del calcolo del massimo tra due numeri
  • Shift logico SHL/SHR ed aritmetico SAL/SAR: applicazione su rappresentazioni con e senza segno, moltiplicazione e divisione intera per 2^S
  • Istruzione LEA per il calcolo di indirizzi: esempio del calcolo di indirizzi di variabili locali in stack e della cella i-esima di un array
• Introduzione all'ottimizzazione dei programmi
  • risorse da ottimizzare (CPU time, uso della memoria)
  • dimensioni del problema (algoritmo vs sua codifica in un linguaggio di programmazione)
  • agenti (programmatore vs compilatore)
• Misurazione dei tempi
  • hardware timer e frequenza, granularità/risoluzione di un timer, RTC (Real Time Clock) vs HPET (High Precision Event Timer)
  • esecuzione di un programma: real, user e system time; comando time (shell builtin vs /usr/bin/time)
  • esecuzione di una porzione di codice: funzione clock_getttime
• Profilazione di un programma
  • introduzione a gprof: confronto del costo delle operazioni /2 vs >>1, ovvero divisione vs shift destro
  • introduzione a valgrind --tool=massif: opzione --time-unit=B, analisi di un report
• Esercizi svolti C -> Assembly IA32
  • calcolo del numero di spazi presenti in una stringa
  • creazione di una nuova stringa priva di spazi - cosa manca nel codice mostrato? :-)

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

• Esercitazione in laboratorio: traduzione da C ad assembly IA-32 | soluzioni ottimizzate

Lunedì 7 novembre 2016 (90 min)

• Presentazione soluzioni non ottimizzate per l'esercitazione del 4 ottobre
• Calcolo della differenza tra due struct timespec impostate con clock_gettime
• Uso della funzione clock in ottica cross-platform
• Legge di Amdahl, speedup e speedup teorico massimo

Giovedì 10 novembre 2016 (180 min)

• Principio di Pareto, bottleneck e hot spots, ulteriori esempi sulla legge di Amdahl
• 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
• 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, calcolo della somma degli elementi di un array e confronto con una threshold, ordinamento di test in cascata partendo dal più frequente (esempio: calcolo dei whitespaces in una stringa)
  • Identità algebriche per semplificare espressioni logiche complesse: verifica della collisione tra due cerchi senza fare ricorso a sqrt
• Importanza dei side-effects quando si rimuove/ottimizza, e.g., una chiamata a funzione e rispetto della semantica originaria del programma
• Ottimizzazione dei loop
  • Loop hoisting (a.k.a. loop-invariant code motion)
  • Uso delle sentinelle: ricerca di un elemento in un array con confronto prestazionale con/senza sentinella
• Ottimizzazione delle funzioni
  • Inlining: tecnica base e trade-off sul numero di istruzioni nel chiamato, inlining come enabler di altre ottimizzazioni, rispetto della semantica pass-by-value per il passaggio dei parametri in C
  • Tail call optimization: overhead di una chiamata a funzione, tail recursion elimination, calcolo del fattoriale con ricorsione/ricorsione coda/iterazione
• Modifiche alle strutture dati per ottimizzare operazioni frequenti costose
  • Principio dell'augmentation: inserimento in coda in una lista, puntatore all'elemento centrale di una lista
  • Precomputation: lookup su tabella per il fattoriale dei primi 100 numeri, generazione della tabella con un metodo init vs compile-time initialization (cenni di meta-programming)

Lunedì 14 novembre 2016 (90 min)

• Sistema operativo come:
  • ambiente per consentire l'utilizzo del calcolatore da parte degli utenti
  • ambiente di esecuzione per i programmi, fornendo risorse e servizi
• Tipologie di OS: batch, time-sharing, real time, altro
• Funzioni del sistema operativo
  • Management (CPU, memoria, dispositivi, filesystem)
  • Coordinazione tra software e tra utenti
  • Gestione dei job
  • Aspetti legati alla sicurezza
• Panoramica su servizi più comuni offerti da un OS: esecuzione di programmi, operazioni di I/O, manipolazione del filesystem, comunicazione tra processi, gestione risorse, protezione e gestione errori
• Servizi OS dal punto di vista dell'utente
  • utility per navigazione e manipolazione del filesystem
  • esecuzione comandi: CLI (command line interface) vs GUI (graphical user interface) -> shell vs ambiente grafico
  • utenze e permessi
  • canali I/O
  • variabili d'ambiente
• Servizi OS dal punto di vista del programmatore
  • passaggio degli argomenti con argc e argv
  • exit status: exit() vs return
  • kernel e servizi forniti: system calls (POSIX standard)
  • differenza tra librerie e system calls
  • accesso e manipolazione variabili d'ambiente: getenv() e setenv()
  • file descriptor, descrittori standard, apertura di un file descriptor con open() e possibili flags, differenze tra int fd e FILE* da <stdio.h>

Giovedì 17 novembre 2016 (180 min)

• Lettura da descrittore con read(), scheletro ciclo per lettura fino ad EOF
• Scrittura su descrittore con write(), scheletro ciclo per scrittura con gestione scritture parziali
• Chiusura di un descrittore con close()
• Definizione di processo, concetto di PID (Process ID) e di PCB (Process Control Block)
• Elementi di un PCB: PID, PID del genitore, fotografia del processore, informazioni di memory management, accounting (es. tempo di CPU consumato), priorità nello scheduling, risorse I/O (es. tabella dei descrittori)
• Ruolo del loader e task svolti dal loader Linux: validazione, copia dell'immagine in memoria, copia di argomenti/variabili d'ambiente e impostazione registri, trasferimento controllo a _start()
• Struttura di memoria di un processo
  • Sezioni base: text, data, heap, stack
  • Boundaries di stack e heap (cenno a sbrk e uso negli allocatori)
  • Ulteriori sezioni: rodata, bss
  • Storage delle variabili: static variables in data o bss, letterali stringa in rodata, variabili locali in stack, memoria allocata dinamicamente in heap
• Esecuzione di un processo (parte I)
  • Fetch-decode-execute e definizione di ciclo macchina (o instruction cycle)
  • Ciclo di clock e relazione con ciclo macchina
  • Aspetti prestazionali
    • Approccio di ottimizzazione: riduzione del numero di cicli di clock richiesti per eseguire il codice
    • Metriche IPC (instructions per cycle), IPS (instructions per second), CPI (cycles per instruction)
    • Time Stamp Counter (TSC) ed istruzione RDTSC con memorizzazione del risultato usando due registri
    • Hardware counters, possibili impieghi, tool di profilazione perf
  • Ottimizzazione: strength reduction ed operator strength reduction, uso di LEA per operazioni matematiche
• Esempi ed esercizi svolti
  • Ricerca utilizando una lookup table (calcolo del numero di vocali in una stringa)
  • Differenze prestazionali tra implementazione ricorsiva e tail-recursive/iterativa nel calcolo del fattoriale
  • Analisi delle cause degli errori per le system calls: variabile globale errno, funzione perror()
  • Implementazione del comando cat utilizzando read() e write()
  • Redirezione di stdin/stdout/stderr manipolando la tabella dei descrittore
  • Svolgimento esercizio tipologia esame su ottimizzazione: analisi con gprof e time dei tempi di esecuzione, creazione di una copia static di un metodo definito altrove (ovvero in un altro file) per automatizzare l'inlining

Lunedì 21 novembre 2016 (90 min)

• Esecuzione di un processo (parte II):
  • architetture superscalari, pipelining, hazard (strutturali, dati, controllo) e stalli (bubbles)
  • cenni ad architetture CISC e RISC, pipeline RISC a 5 stadi, concetto di branch prediction
  • ottimizzazioni del codice sfruttando la pipeline: istruzioni branchless, instruction scheduling
    • esempi svolti: massimo tra due interi con CMOV, valore assoluto di un intero con CMOV e in variante senza uso di condition code
  • cenni ad esecuzione parallela: CPU multicore e instruction-level parallelism (SIMD ed estensioni MMX/3DNow!/SSE/AVX)
  • esecuzione in modalità utente (user) e in modalità supervisore (kernel): concetto di ring ed operazioni privilegiate

Giovedì 24 novembre 2016 (180 min)

• Esecuzione di un processo (parte III): [ref1, ref2]
  • flusso del controllo normale ed eccezionale, stato del programma vs. stato del sistema
  • eccezioni sincrone (interne):
    • distinzione concettuale: eccezioni intenzionali e non, recuperabili e non
    • trap: istruzione IA32 INT, invocazione di system call (INT 0x80, passaggio dei parametri, esempio con write) [ref3]
    • fault: es. divisione per zero, accesso a memoria
    • abort: es. parity error
  • eccezioni asincrone (esterne):
    • interrupt: dispositivi I/O, timer, ecc
    • ruolo del PIC (Programmable Interrupt Controller)
    • differenza con interrupt software/trap
  • OS e tabella delle eccezioni (interrupt vector), ruolo degli interrupt handler
  • eccezioni in IA32: Interrupt Descriptor Table (IDT)
  • cenni alla semantica di basso livello di INT ed ai suoi usi (es. programmi MS-DOS, software breakpoint nei debugger)

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

• Prova intermedia di esonero

Lunedì 28 novembre 2016 (90 min)

• Esecuzione di un processo (parte IV):
  • stati di un processo: running user, running kernel, blocked (detto anche waiting o sleeping)
• Esecuzione simultanea di più processi (parte I):
  • nozione di esecuzione concorrente
  • astrazioni offerte da un processo: control flow logico, spazio di indirizzamento privato
  • multiprogrammazione e scheduling dei processi: [ref]
    • context switch: salvataggio dello stato della CPU nel PCB
    • ulteriori stati di un processo: started, ready, zombie (diagramma degli stati in Linux)
    • principi di fairness e di balance per uno scheduler
    • esempio del time sharing round-robin mediante timer e interrupt
    • cenni allo scheduling con priorità
  • comandi ps e top per analizzare i processi
  • processo init, albero dei processi e comando pstree

Giovedì 1 dicembre 2016 (180 min)

• Esecuzione simultanea di più processi (parte II):
  • approcci alternativi per I/O: busy waiting, polling tra più dispositivi
  • system call per il controllo dei processi:
    • creazione (fork) ed effetti su immagine del processo e descrittori
    • terminazione, differenze tra libc exit(3) e system call _exit(2)
    • attesa terminazione (wait), macro per manipolazione exit status (WEXITSTATUS, WIFEXITED)
    • sostituzione immagine di un processo con exec (versioni execv ed execvp)
  • meccanismo dei segnali
    • principi, signali sincroni ed asincroni, segnali POSIX più comuni
    • signal handler, blocco di un segnale
    • system calls sigaction(2) e kill(2), campi di struct sigaction e prototipo di un signal handler, funzione di libreria raise(3)
    • esempio: cattura di SIGCHLD per attesa asincrona della terminazione di un processo figlio

Lunedì 5 dicembre 2016 (90 min)

• 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
    • gestione delle scritture: strategie write-back e write-through
    • livelli di caching multipli
  • altri usi delle cache in un sistema di calcolo (es. disco, browser)

Lunedì 12 dicembre 2016 (90 min)

• Come è strutturata la memoria? (parte II) [ref1, ref2]
  • gestione dei write miss: strategie fetch-on-write (write-allocate) e write-no-allocate
  • rappresentazione piramidale di una gerarchia di memoria
    • registri, cache L1, L2, L3, memoria, storage primario (disco) e secondario (cloud, etc.)
    • problema del memory wall e rilevanza del caching multi-livello
    • 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 (L1-I, L1-D, L2, L3)
  • ottimizzazioni del codice nell'uso della memoria:
    • tempo di esecuzione
      • register allocation per sfruttare la velocità dei registri e ridurre il ricorso al register spilling
      • scrittura di codice cache-friendly
        • ordinamenti row-major e column-major per array multidimensionali (es. matrici)
        • casi di studio: inizializzazione di una matrice, prodotto tra matrici (varianti del ciclo ijk)
      • accessi a memoria allineati
        • cenni a problemi prestazionali da accessi non allineati, ruolo del padding
        • allineamento dei campi delle struct C
        • stack pointer a 16 byte prima di una call
    • 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)

[ Canale AO (Demetrescu/Coppa) ]