Utente:Giu.natale/Roofline

Il modello Roofline (in italiano letteralmente "linea del tetto") è un modello di performance visuale che consente in maniera intuitiva di stimare le performance di un dato kernel computazionale o di una applicazione che esegue su architetture di calcolo di tipo multi-core, many-core o su acceleratori, mostrando graficamente le limitazioni inerenti all'hardware usato e le potenziali ottimizzazioni da poter applicare, nonché la priorità con cui esse necessitano di essere applicate.^[1]^[2] Facendo convergere aspetti riguardanti la località dei dati, la banda, e paradigmi di parallelizazione in un'unica raffigurazione, il modello di fatto costituisce una valida alternativa al semplice utilizzo della percentuale del picco di performance per valutare la qualità delle prestazioni ottenute, dal momento che è in grado di modellare analiticamente sia dettagli implementativi che limitazioni alle prestazioni dovute a caratteristiche intrinseche dell'architettura considerata.^[1]

Il modello Roofline nella sua versione base può essere visualizzato graficando le prestazioni relative all'esecuzione di istruzioni a virgola mobile (FLOPS) come funzione del picco di performance, il picco di banda della macchina, e l'intensità operativa. La curva risultante, chiamata appunto Roofline, costituisce un limite superiore alle prestazioni ottenibili, al di sotto della quale esistono le effettive performance per il dato kernel o applicazione. Suddetta curva include due limiti massimi specifici della piattaforma: un limite derivato dalla banda di memoria e un limite derivato dal picco di performance dell'unità di computazione.

Termini e metriche di performance associate

Lavoro

Il lavoro $W$ indica il numero di operazioni eseguite da un dato kernel computazionale o applicazione.^[3] Questa metrica può riferirsi ad un qualsiasi tipo di operazione, a partire dal numero di punti di array aggiornati al secondo, al numero di operazioni intere al secondo, al numero di operazioni a virgola mobile per secondo (FLOPS), e la scelta di una o l'altra è dettata dal caso e dalle necessità. Tuttavia, nella maggior parte dei casi, $W$ è espresso in FLOPS.^[3]^[2]^[1]^[4]^[5]

Da notare che il lavoro $W$ è una proprietà del dato kernel o applicazione e pertanto dipende solo parzialmente dalle caratteristiche della piattaforma.

Traffico di memoria

Il traffico di memoria $Q$ indica il numero di bytes di memoria trasferiti durante l'esecuzione del kernel o applicazione.^[3] Contrariamente a $W$ , $Q$ è altamente dipendente dalle proprietà della piattaforma usata, come per esempio la topologia della cache.^[3]

Intensità operativa

L'intensità operativa $I$ , alle volte definita come intensità aritmetica^[2]^[6], rappresenta il rapporto tra il lavoro $W$ e il traffico di memoria $Q$ :^[3] $I={W \over Q}$ e indica il numero di operazioni effettuate per byte di traffico di memoria. Quando il lavoro $W$ è espresso in FLOPS, la risultante intensità operativa $I$ è espressa come il rapporto tra le operazioni a virgola mobile e il volume di dati trasferiti (FLOPS/byte).

Roofline naïve

Un esempio di un Roofline naïve che riporta l'analisi di due kernel. Il primo ha una Intensità operativa

O_{1}

al di sotto della linea diagonale rappresentante il limite inposto dalla banda, ed è pertanto memory-bound. Il secondo kernel ha invece una intensità operativa

O_{2}

che è al di sotto del limite orizzontale rappresentante il picco di performance, ed è di conseguenza compute-bound.

Il Roofline naïve^[2] è ottenuto tramite una semplice analisi "di limite e collo di bottiglia" (bound and bottleneck).^[7] In questa formulazione del modello Roofline sono presenti solo due parametri: picco di performance e picco di banda della specifica architettura; ed una variabile: intensità operativa. Il picco di performance, espresso in generale in GFLOPS, può essere generalmente derivato da manuali architetturali, mentre il picco di banda, che nello specifico si riferisce all picco di banda della DRAM, è invece ottenuto tramite benchmarking.^[2]^[3] Il grafico risultante, in generale avente entrambi gli assi in scala logaritmica, è quindi derivato dalla formula seguente: ^[3]

$P=\min {\begin{cases}\pi \\\beta \times I\end{cases}}$

Dove $P$ rappresenta le performance ottenibili, $\pi$ rappresenta il picco di performance, $\beta$ rappresenta il picco di banda e $I$ rappresenta l'intensità operativa. Il punto in cui le performance saturano al livello di picco di performance $\pi$ - i.e. dove il limite diagonale e quello orizzontale si incontrano - è definito come punto di cresta (ridge point).^[1] Il punto di cresta consente di effettuare utili considerazioni sulle prestazioni complessive della macchina, poichè fornisce la minima intensità operativa richiesta per poter raggiungere il picco di performance, e pertanto suggerisce la quantità di sforzo richiesto al programmatore per approcciare, almeno teoricamente, suddetto picco.^[1]

Un dato kernel o applicazione è quindi caratterizzato da un punto dato dalla sua intensità operativa $I$ (sulle ascisse). Il termine relativo alle performance ottenibili $P$ è pertanto identificato tracciando una linea verticale passante per quel punto che incroci la Roofline. Conseguentemente, il kernel o applicazione è detto essere memory bound se $I\leq \pi /\beta$ . Se invece $I\geq \pi /\beta$ , la computazione è detta essere compute bound.^[3]

Aggiungere limiti superiori al modello

Il Roofline naïve fornisce solo un limite superiore massimo (il massimo teorico) alle performance. Sebbene questa versione del modello di per sé consente di ricavare utili informazioni sulle performance ottenibili, è di fatto incompleto, in quanto non modella in maniera sufficientemente dettagliata le caratteristiche della piattaforma utilizzata e pertanto non consente una analisi esaustiva dei fattori che limitano le prestazioni. Se ad esempio il kernel computazionale o applicazione in oggetto raggiunge prestazioni che sono molto al di sotto della Roofline, potrebbe essere utile catturare altri limiti superiori delle performance, in aggiunta ai semplici picco di banda e picco di performance, al fine di guidare lo sviluppatore nel processo di scelta delle ottimizzazioni da implementare, o ancora per valuare qualitativamente l'adeguatezza dell'architettura usata rispetto al kernel o applicazione di cui si sta effettuando l'analisi.^[2] I limiti superiori aggiunti impongono pertanto un limite sulle performance ottenibili che è al di sotto della Roofline, e indicano che il kernel o applicazione non può passare oltre nessuno di questi limiti senza prima eseguire l'ottimizzazione associata.^[1]^[2]

Il grafico Roofline può essere espanso in tre aspetti differenti: comunicazione, aggiungendo i limiti di banda, computazione, aggiundendo i limiti in-core, e località dei dati, aggiungendo i muri di località.

Un esempio di modello Roofline con l'aggiunta di limiti di banda. In questo modello, i due limiti addizionali rappresentano la mancanza di software prefetching e di una organizzazione NUMA della memoria.
Un esempio di modello Roofline con l'aggiunta di limiti in-core, dove i due limiti aggiunti rappresentano la mancanza di instruction level parallelism e task level parallelism.
Un esempio di modello Roofline con aggiunti i muri di località. Il muro etichettato come 3 C's indica la presenza di tutti e tre i tipi di cache miss: compulsory, capacity e conflict miss. Il muro etichettato con 2 C's indica la presenza di compulsory e capacity miss o compulsory e conflict miss. L'ultimo muro denota la presenza dei soli compulsory miss.

Limiti di banda

I limiti di banda sono linee diagonali che limitano la banda e sono piazzate al di sotto della diagonale di picco di banda. La loro esistenza è causata dalla mancanza di specifiche ottimizzazioni architetturali relative alla memoria, come la coerenza delle cache, o di ottimizzazione software, come la mancanza di una sufficiente esposizione della concorrenza (che conseguentemente può limitare l'utilizzo di banda).^[2]^[1]

Limiti in-core

I limiti in-core sono curve situate al di sotto della reale Roofline, la cui presenza scaturisce dalla mancanza di una determinata forma di parallelismo. Questi limiti superiori impongono di fatto una riduzione su quanto elevate le performance di una data applicazione o kernel computazionale possono essere. Le performance non possono eccedere questi limiti in-core a meno che la relativa forma di parallelismo sia eistente ed effettivamente sfrutttata. Suddetti limiti possono in certi casi essere direttamente derivati dai manuali architetturali e non soltanto da benchmarking.^[2]^[1]

Muri di località

Se l'assunzione idealistica che l'intensità operativa è funzione delle sole caratteristiche del dato kernel o applicazione è rimossa, e pertanto viene considerata la topologia della cache, e di conseguenza la presenza di cache miss, l'intensità operativa risulta di conseguenza dipendente da una combinazione del kernel e dell'architettura in uso. Ciò può risultare in un degrado delle prestazioni dipendente dal bilanciamento tra l'intensità operativa risultante e il punto di cresta. Contrariamente alle due categorie di limiti precedenti, le linee risultanti da questo tipo di analisi sono linee verticali che limitano l'intensità operativa e che non possono essere superate senza la dovuta ottimizzazione. Per questa ragione, suddette linee sono chiamate muri di località o più semplicemente muri di intensità operativa.^[2]^[1]

Estensioni del modello

Successivamente alla sua introduzione,^[2]^[1] il modello è stato ulteriormente esteso per considerare un più ampio insieme di metriche e colli di bottiglia relativi all'hardware. Attualmente in letteratura si possono trovare estensioni che considerano l'impatto di una organizzazione della memoria NUMA,^[5] di esecuzione delle istruzioni fuori ordine,^[8] della latenza delle memorie,^[9]^[8] e che modellano la gerarchia della cache a un livello più dettagliato,^[4]^[8] al fine di fornire una visione più completa dei fattori che limitano le prestazioni e conseguentemente guidare il processo di ottimizzazione.

Inoltre, il modello è stato esteso anche per adattarsi ad architetture specifiche e alle relative caratteristiche, come nel caso delle FPGA.^[10]

Note

^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j Samuel Williams, Roofline: An Insightful Visual Performance Model for Multicore Architectures, in Commun. ACM, vol. 52, n. 4, 1º aprile 2009, pp. 65–76, DOI:10.1145/1498765.1498785.
^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k Samuel W. Williams, Auto-tuning Performance on Multicore Computers (tesi Ph.D.), University of California at Berkeley, 2008.
^ ^a ^b ^c ^d ^e ^f ^g ^h G. Ofenbeck, Applying the roofline model, in 2014 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), 1º marzo 2014, pp. 76–85, DOI:10.1109/ISPASS.2014.6844463.
^ ^a ^b A. Ilic, Cache-aware Roofline model: Upgrading the loft, in IEEE Computer Architecture Letters, vol. 13, n. 1, 1º gennaio 2014, pp. 21–24, DOI:10.1109/L-CA.2013.6.
^ ^a ^b (EN) Oscar G. Lorenzo, Using an extended Roofline Model to understand data and thread affinities on NUMA systems, in Annals of Multicore and GPU Programming, vol. 1, n. 1, 31 marzo 2014, pp. 56–67.
^ Roofline Performance Model, su crd.lbl.gov, Lawrence Berkeley National Laboratory.
^ Kornilios Kourtis, Optimizing Sparse Matrix-vector Multiplication Using Index and Value Compression, in Proceedings of the 5th Conference on Computing Frontiers, ACM, 1º gennaio 2008, pp. 87–96, DOI:10.1145/1366230.1366244.
^ ^a ^b ^c V. C. Cabezas, Extending the roofline model: Bottleneck analysis with microarchitectural constraints, in 2014 IEEE International Symposium on Workload Characterization (IISWC), 1º ottobre 2014, pp. 222–231, DOI:10.1109/IISWC.2014.6983061.
^ (EN) O. G. Lorenzo, 3DyRM: a dynamic roofline model including memory latency information, in The Journal of Supercomputing, vol. 70, n. 2, 26 marzo 2014, pp. 696–708, DOI:10.1007/s11227-014-1163-4.
^ Bruno da Silva, Performance Modeling for FPGAs: Extending the Roofline Model with High-level Synthesis Tools, in Int. J. Reconfig. Comput., vol. 2013, 1º gennaio 2013, pp. 7:7–7:7, DOI:10.1155/2013/428078.

Bibliografia

Samuel W. Williams, Auto-tuning Performance on Multicore Computers (tesi Ph.D.), University of California at Berkeley, 2008.
Samuel Williams, Roofline: An Insightful Visual Performance Model for Multicore Architectures, in Commun. ACM, vol. 52, n. 4, 1º aprile 2009, pp. 65–76, DOI:10.1145/1498765.1498785.

Collegamenti esterni

Tool disponibili

Roofline Model Toolkit
- Roofline Model Toolkit: A Practical Tool for Architectural and Program Analysis - pubblicazione associata al tool.
Perfplot
Extended Roofline Model
Intel Advisor - Roofline model (programma di accesso anticipato)

[[Categoria:Teorie dell'informatica]]

[:1-1] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j Samuel Williams, Roofline: An Insightful Visual Performance Model for Multicore Architectures, in Commun. ACM, vol. 52, n. 4, 1º aprile 2009, pp. 65–76, DOI:10.1145/1498765.1498785.

[WilliamsPhD-2] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k Samuel W. Williams, Auto-tuning Performance on Multicore Computers (tesi Ph.D.), University of California at Berkeley, 2008.

[:0-3] ^ ^a ^b ^c ^d ^e ^f ^g ^h G. Ofenbeck, Applying the roofline model, in 2014 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), 1º marzo 2014, pp. 76–85, DOI:10.1109/ISPASS.2014.6844463.

[:2-4] A. Ilic, Cache-aware Roofline model: Upgrading the loft, in IEEE Computer Architecture Letters, vol. 13, n. 1, 1º gennaio 2014, pp. 21–24, DOI:10.1109/L-CA.2013.6.

[:3-5] (EN) Oscar G. Lorenzo, Using an extended Roofline Model to understand data and thread affinities on NUMA systems, in Annals of Multicore and GPU Programming, vol. 1, n. 1, 31 marzo 2014, pp. 56–67.

[6] Roofline Performance Model, su crd.lbl.gov, Lawrence Berkeley National Laboratory.

[:7-7] Kornilios Kourtis, Optimizing Sparse Matrix-vector Multiplication Using Index and Value Compression, in Proceedings of the 5th Conference on Computing Frontiers, ACM, 1º gennaio 2008, pp. 87–96, DOI:10.1145/1366230.1366244.

[:4-8] V. C. Cabezas, Extending the roofline model: Bottleneck analysis with microarchitectural constraints, in 2014 IEEE International Symposium on Workload Characterization (IISWC), 1º ottobre 2014, pp. 222–231, DOI:10.1109/IISWC.2014.6983061.

[:5-9] (EN) O. G. Lorenzo, 3DyRM: a dynamic roofline model including memory latency information, in The Journal of Supercomputing, vol. 70, n. 2, 26 marzo 2014, pp. 696–708, DOI:10.1007/s11227-014-1163-4.

[:6-10] Bruno da Silva, Performance Modeling for FPGAs: Extending the Roofline Model with High-level Synthesis Tools, in Int. J. Reconfig. Comput., vol. 2013, 1º gennaio 2013, pp. 7:7–7:7, DOI:10.1155/2013/428078.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]