Deprecated: Function ereg() is deprecated in /home/demetres/public_html/didattica/ae/libs/Wakka.class.php on line 648 Ingegneria degli Algoritmi: Diario delle lezioni ed esercizi del giorno

Most recent edit on 2015-09-03 13:45:59 by CamilDemetrescu

Additions:
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/safehtml.php on line 308 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 159 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 161 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 162 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 163 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 165 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 166 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 167 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 243 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 250 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 259 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 266 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 273 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 280 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 467 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 469 Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae/3rdparty/core/safehtml/classes/HTMLSax.php on line 471 ~- Programmazione OpenCL

Programmazione OpenCL
Programmazione OpenCL ed esercizi riepilogativi

Deletions:
~- Programmazione OpenCL
Programmazione OpenCL
Programmazione OpenCL ed esercizi riepilogativi

Edited on 2015-09-03 13:45:47 by CamilDemetrescu

Additions:
~- Programmazione OpenCL
Programmazione OpenCL
Programmazione OpenCL ed esercizi riepilogativi

Edited on 2015-09-03 13:37:55 by CamilDemetrescu

Additions:

Lunedì 3 marzo 2015 (180 min)

Giovedì 5 marzo 2015 (90 min)

Deletions:

Lunedì 3 marzo 2014 (180 min)

Giovedì 5 marzo 2014 (90 min)

Edited on 2015-05-20 12:34:37 by CamilDemetrescu

Additions:

Mercoledì 13 maggio 2015 (90 min)

Lunedì 18 maggio 2015 (180 min)

Mercoledì 20 maggio 2015 (90 min)

Edited on 2015-05-11 17:56:22 by CamilDemetrescu

Additions:
~- [Esercizi su Makefile (37-39)]

[Nozioni di base su Makefile]
[Tutorial su makefile∞]

Deletions:
~- Esercizi su Makefile (37-39)
Nozioni di base su Makefile
Tutorial su makefile∞

Edited on 2015-05-11 17:55:32 by CamilDemetrescu

Additions:
~- Esercizi su Makefile (37-39)

Deletions:
~- Esercizi su Makefile (37-39)]

Edited on 2015-05-11 17:55:20 by CamilDemetrescu

Additions:
~- Esercizi su Makefile (37-39)]

Edited on 2015-05-11 17:52:24 by CamilDemetrescu

Additions:
~- Tutorial su makefile∞

Edited on 2015-05-11 17:51:41 by CamilDemetrescu

Additions:
~- Nozioni di base su Makefile

Edited on 2015-05-11 17:49:22 by CamilDemetrescu

No differences.

Edited on 2015-05-11 17:46:13 by CamilDemetrescu

Additions:
~- Splitting e coalescing negli allocatori di memoria: lookup table, boundary tag
Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles: Dynamic Storage Allocation: A Survey and Critical Review. In Proceedings of the 2nd International Workshop on Memory Management (IWMM 95), Kinross, Scotland, LNCS 986, 1995 [scarica pdf, 740 KB∞]:
- paragrafo 3.1: splitting e coalescing
- paragrafo 3.2: header, allineamento, liste di blocchi, bit stealing, brk, sbrk, boundary tag, lookup table
- paragrafo 3.3: politiche di gestione dei blocchi liberi
Doug Lea: A Memory Allocator. unix/Mail December, 1996. Hanser Verlag [pagina web∞]

Deletions:
~- Splitting e coalescing negli allocatori di memoria: boundary tag

Edited on 2015-05-11 17:44:58 by CamilDemetrescu

Additions:
~- Sistemi di calcolo paralleli [ref∞]:
Ryoji Tsuchiyama, Takashi Nakamura, Takuro Iizuka, Akihiro Asahara, Jeongdo Son, Satoshi Miki. The OpenCL Programming Book. Fixstars, 2012 [Versione OpenCL 1.0 disponibile gratuitamente online∞]

Deletions:
~- Sistemi di calcolo paralleli [T8∞]:
[T8] Ryoji Tsuchiyama, Takashi Nakamura, Takuro Iizuka, Akihiro Asahara, Jeongdo Son, Satoshi Miki. The OpenCL Programming Book. Fixstars, 2012 [Versione OpenCL 1.0 disponibile gratuitamente online∞]

Edited on 2015-05-11 17:44:00 by CamilDemetrescu

Additions:
~- Liste di blocchi liberi con classi dimensionali (segregated free lists):
- Liste con classi dimensionali lineari esatte
- Liste con classi dimensionali esponenziali esatte
- Liste con classi dimensionali esponenziali con range
Splitting e coalescing negli allocatori di memoria: boundary tag
Sistemi di calcolo paralleli [T8∞]:
- Grid, MPP (Massively Parallel Processor), cluster server, SMP (Symmetric Multiprocessing), multi-core
- Tassonomia di Flynn: SISD, SIMD, MISD, MIMD
- Sistemi a memoria distribuita, sistemi a memoria condivisa (SMP, NUMA)
- Sistemi eterogenei e acceleratori (GPU)
[T8] Ryoji Tsuchiyama, Takashi Nakamura, Takuro Iizuka, Akihiro Asahara, Jeongdo Son, Satoshi Miki. The OpenCL Programming Book. Fixstars, 2012 [Versione OpenCL 1.0 disponibile gratuitamente online∞]

Deletions:
~- TBA

Edited on 2015-05-11 09:25:02 by CamilDemetrescu

Additions:

Lunedì 11 maggio 2015 (180 min)
TBA

Edited on 2015-05-06 11:56:17 by CamilDemetrescu

Additions:
~- Makefile
Allocazione dinamica della memoria

Mercoledì 6 maggio 2015 (90 min)

Allineamento dei blocchi allocati dinamicamente
Fattore di carico di una struttura dati
Uso del tool massif per il profiling dell'heap
[Manuale massif∞]

Deletions:
~- TBA

Edited on 2015-05-04 10:06:13 by CamilDemetrescu

Additions:

Lunedì 27 aprile 2015 (180 min)

Mercoledì 29 aprile 2015 (90 min)

Lunedì 4 maggio 2015 (180 min)

TBA

Deletions:

Lunedì 27 Aprile 2015 (180 min)

Mercoledì 29 Aprile 2015 (90 min)

Edited on 2015-05-04 10:05:24 by CamilDemetrescu

Additions:
~- [Codice C esempio moltiplicazione matrici per x86 con supporto SSE4.1 e pthread (file .zip, 8109 byte)∞]

Deletions:
~- [Codice C esempio moltiplicazione matrici per x86 con supporto SSE4.1 e pthread (file .zip)∞]

Edited on 2015-05-04 10:04:00 by CamilDemetrescu

Additions:
~- Legge di Amdahl per programmi sequenziali

Deletions:
~- Amdahl's law for sequential programs

Edited on 2015-04-29 12:09:28 by CamilDemetrescu

Additions:
~- Performance profiling tools: gprof

Amdahl's law for sequential programs

Deletions:
~- TBA

Oldest known version of this page was edited on 2015-04-29 09:47:38 by CamilDemetrescu []

Page view:
Diario delle lezioni ed esercizi del giorno

Questa pagina riporta l'elenco delle lezioni svolte in aula.

Lunedì 3 marzo 2014 (180 min)

Modalità di esame.
Panoramica preliminare degli argomenti che verranno trattati nel corso:
- Introduzione al linguaggio C
- Mapping costrutti di alto livello del C su codice x86
- Analisi e ottimizzazione delle prestazioni dei programmi
- Gestione efficiente della memoria
- Programmazione di schede grafiche GPU
Esempio motivazionale: somma degli elementi di una matrice
Hello world in C -- differenze con Java
Nozione di oggetto C∞ come regione di memoria contenente un valore.
Variabile come esempio tipico di oggetto.
Anatomia dello spazio logico di un processo: TEXT, DATA, HEAP, STACK
Tipi primitivi: void, char, short, int, long, long long, float, double, long double.
Tipi interi con e senza segno.
Tipi come interpretazione dei byte di un oggetto.
Introduzione alle funzioni di output: funzione printf∞. Stringhe di formato e specificatori %c, %d, %u, %ld, %lu %f.

Materiale didattico: [Appunti sul linguaggio C | Anatomia di un programma in memoria∞]

Giovedì 5 marzo 2014 (90 min)

Espressioni in C:
- espressioni LValue∞ per denotare oggetti
- espressioni RValue∞ per denotare valori.
Conversione di LValue a RValue∞.
Operatore sizeof per determinare la dimensione in byte di tipi, valori, oppure oggetti di un certo tipo.
Tipi puntatore: variabili puntatore e indirizzi
Operatori * ("all'indirizzo")∞ e & ("indirizzo di")∞.

Materiale didattico: [Appunti sul linguaggio C | Esercizi sul linguaggio C (1-4)]

Lunedì 9 marzo 2015 (180 min)

Aritmetica dei puntatori∞: somma puntatore-intero e differenza di puntatori.
Uso di v[i] come espressione equivalente a *(v+i).
Puntatori generici void* e conversioni fra puntatori∞.
Regole di compatibilità tra puntatori∞
Tipi array∞:
- LValue che denotano oggetti array sono non modificabili
- Parametri formali di tipo array interpretati come puntatori
- Conversione automatica di una variabile array a un RValue di tipo puntatore
Esempi: ricerca binaria su array

Materiale didattico: [Appunti sul linguaggio C | Esercizi sul linguaggio C (5-16)]

Giovedì 12 marzo 2015 (90 min)

Panoramica su materiale utile online sul linguaggio C:
- [T3] ISO/IEC 9899:1999 Stardard Rationale - The C Programming Language∞
- [T5] C/C++ Language Reference∞ - IBM
- [P0] Portale Questions & Answers StackOverflow dedicato alla programmazione in C∞
- [P1] Tabella precedenze operatori C∞
- [P7] Opzioni riga di comando gcc∞
- [P8] Standard POSIX (IEEE Std 1003.1, 2004 Edition)∞, include tutte le librerie standard C: si veda la sezione System Interfaces volume (XSH).
Precedenze e associatività degli operatori
Stringhe C:
- Rappresentazione in memoria
- Letterali carattere∞ '.' e letterali stringa∞ "..."
- Specificatori di formato %s e %c per la printf
- Esempi:
  - definizione funzione per calcolare la lunghezza di una stringa

Materiale didattico: [Appunti sul linguaggio C | Esercizi sul linguaggio C (17-24)]

Lunedì 16 marzo 2015 (180 min)

Array multidimensionali (ISO C90): matrici con ordine row-major∞ e matrici allocate dinamicamente
Strutture in C:
- costrutto struct: dichiarazione e tag
- accesso ai campi di una struttura:
  - operatore .
  - operatore ->
- assegnazione e passaggio di parametri di oggetti di tipo struct
- esempio: lista collegata
Dichiarazioni di identificatori di tipo mediante typedef
Espressioni che denotano tipi
- Regole generali di interpretazione∞
- Esempio della system call signal
Puntatori a funzione
- Esempi di funzioni generiche mediante uso di puntatori a funzione

Materiale didattico: [Appunti sul linguaggio C | Esercizi sul linguaggio C (25-29)]

Giovedì 19 marzo 2015 (90 min)

Debugging dell'uso della memoria: il tool valgrind
Macro e compilazione condizionale in C:
- Definizione di macro senza e con parametri: direttiva #define
- Tranelli nell'uso delle macro: precedenze degli operatori
- Compilazione condizionale: direttive #ifdef, #ifndef, #if, #endif, defined()
- Problema delle inclusioni multiple e soluzione mediante uso di macro
Modularizzazione di programmi C
Realizzazione di tipi di dato astratti in C

Materiale didattico: [Appunti sul linguaggio C | Esercizi sul linguaggio C]

Lunedì 23 marzo 2015 (180 min)

Esercizi sul linguaggio C
Compilazione di programmi in linguaggio assembly:
- Nozione di Instruction Set Architecture (ISA) e Application Binary Interface (ABI)
- Concetti base dell'ISA IA32 (x86):
  - tipi di dato primitivi Byte, Word, Double Word, Single Precision, Double Precision, Extende Precision
  - registri dati: A, B, C, D, DI, SI, BP, SP
  - registri EIP e EFLAGS

Materiale didattico: [Dispensa didattica corso di Sistemi di Calcolo - Capitolo 4∞]

Mercoledì 25 marzo 2015 (90 min)

Modi di indirizzamento IA32 (immediato, registro, memoria)
Sintassi AT&T (GAS)
Traduzione istruzioni di assegnazione da C a IA32
Conversione interi con estensione del numero di bit, istruzione MOVS

Materiale didattico: [Dispensa didattica corso di Sistemi di Calcolo - Capitolo 4∞]

Lunedì 30 marzo 2015 (180 min)

Traduzione espressioni aritmetico-logiche da C a IA32
Azzeramento di registri con XOR
Istruzione LEA (Load Effective Address)
Registro EFLAGS e codici di condizione ZF, SF, CF, OF
Suffissi di condizione (e, ne, g, ge, l, le, a, ae, b, be, ecc.)
Istruzione di confronto CMP
Traduzione costrutti di selezione da C a IA32
Esempi: somma di due interi, massimo di due interi

Materiale didattico: [Dispensa didattica corso di Sistemi di Calcolo - Capitolo 4∞]

Mercoledì 1 aprile 2015 (90 min)

Traduzione costrutti di iterazione da C a IA32
Accesso ai parametri passati a una funzione: convenzione System V ABI
Esempi: somma degli elementi di un array di interi

Materiale didattico: [Dispensa didattica corso di Sistemi di Calcolo - Capitolo 4∞]

Mercoledì 8 aprile 2015 (90 min)

Assegnamento condizionale: istruzione CMOV
Altre istruzioni utili: TEST, MOVZ
Analisi della documentazione ufficiale Intel per l'ISA IA32 e x86-64

Materiale didattico:

[Dispensa didattica corso di Sistemi di Calcolo - Capitolo 4∞]
Intel® 64 and IA-32 Architectures Software Developer's Manual∞
- Volume 1: Basic Architecture∞: descrive l'architettura e l'ambiente di programmazione dei microprocessori IA-32 e Intel 64
- Volume 2A: Instruction Set Reference, A-M∞: descrive il formato delle istruzioni e fornisce documentazione sulle istruzioni da A a M (sintassi Intel). Il volume contiene anche l'indice dei volumi 2A e 2B.
- Volume 2B: Instruction Set Reference, N-Z∞: fornisce documentazione sulle istruzioni da L a Z (tranne le istruzioni VMX, sintassi Intel). Il volume contiene anche le appendici e l'indice analitico dei volumi 2A e 2B.

Lunedì 13 aprile 2015 (180 min)

Esercizi sulla compilazione di programmi da C a IA32
Tecniche di ottimizzazione dei programmi: logica di calcolo
- Constant propagation
- Constant folding
- Copy propagation
- Common subexpression elimination
- Cortocircuitazione
- Identità algebriche
- Ottimizzazione dimensione struct in C

Materiale didattico: [Slide lezione 2 corso MIT 6.172∞]

Mercoledì 15 aprile 2015 (90 min)

Tecniche di ottimizzazione dei programmi: cicli
- Loop-invariant code motion
- Loop fusion
- Loop unrolling
- Sentinelle

Materiale didattico: [Slide lezione 2 corso MIT 6.172∞]

Lunedì 20 aprile 2015 (180 min)

Tecniche di ottimizzazione basate su strutture dati:
- Matrici sparse
- Lookup table e metaprogrammazione
Bit tricks:
- Scambio variabili senza variabile di appoggio mediante xor
- Calcolo del minimo/massimo senza alterare il flusso del controllo (branchless) mediante xor e and
- Calcolo della potenza di due superiore più vicina mediante shift e or con doubling
Tecniche di ottimizzazione delle funzioni:
- Function inlining
- Tail call
- Tail recursion
Esempi al calcolatore di ottimizzazioni effettuate dal compilatore gcc

Materiale didattico:

[Slide lezione 2 corso MIT 6.172∞]
[Slide lezione 4 corso MIT 6.172∞]

Lunedì 27 Aprile 2015 (180 min)

Packing di bit (stealing)
Tecniche per sfruttare il parallelismo
- Instruction-level parallelism: pipeline, vettorizzazione
- Task-level parallelism: thread
Caso di studio: prodotto di matrici

Materiale didattico:

Mercoledì 29 Aprile 2015 (90 min)

[ A.A. 2008-2009 | A.A. 2009-2010 | A.A. 2010-2011 | A.A. 2012-2013 | A.A. 2013-2014 ]

Ingegneria degli Algoritmi

Corso di Laurea in Ingegneria Informatica e Automatica - A.A. 2014-2015

Lunedì 3 marzo 2015 (180 min)

Giovedì 5 marzo 2015 (90 min)

Lunedì 3 marzo 2014 (180 min)

Giovedì 5 marzo 2014 (90 min)

Mercoledì 13 maggio 2015 (90 min)

Lunedì 18 maggio 2015 (180 min)

Mercoledì 20 maggio 2015 (90 min)

Lunedì 11 maggio 2015 (180 min)

Mercoledì 6 maggio 2015 (90 min)

Lunedì 27 aprile 2015 (180 min)

Mercoledì 29 aprile 2015 (90 min)

Lunedì 4 maggio 2015 (180 min)

Lunedì 27 Aprile 2015 (180 min)

Mercoledì 29 Aprile 2015 (90 min)

Diario delle lezioni ed esercizi del giorno

Lunedì 3 marzo 2014 (180 min)

Giovedì 5 marzo 2014 (90 min)

Lunedì 9 marzo 2015 (180 min)

Giovedì 12 marzo 2015 (90 min)

Lunedì 16 marzo 2015 (180 min)

Giovedì 19 marzo 2015 (90 min)

Lunedì 23 marzo 2015 (180 min)

Mercoledì 25 marzo 2015 (90 min)

Lunedì 30 marzo 2015 (180 min)

Mercoledì 1 aprile 2015 (90 min)

Mercoledì 8 aprile 2015 (90 min)

Lunedì 13 aprile 2015 (180 min)

Mercoledì 15 aprile 2015 (90 min)

Lunedì 20 aprile 2015 (180 min)

Lunedì 27 Aprile 2015 (180 min)

Mercoledì 29 Aprile 2015 (90 min)