IN OPEN MP 3.0
di Federico Massaioli
La diffusione dei processori multicore ha stimolato l’interesse per il parallelismo e la domanda di semplici modelli di parallelizzazione di algoritmi dinamici ed irregolari. Il modello di tasking di OpenMP 3.0, al cui sviluppo CASPUR ha partecipato attivamente, è una delle risposte disponibili.
• Abstract
The widespread adoption of multicore processors in all kind of computing devices is springing interest for parallel computing, which is the only approach to achieve the promised performance boosts. Parallel computing is not easy, and the resulting com-plexity, which is usually tolerated in the computational science field, must be strictly controlled in commercial software life cycles.
OpenMP is a widely supported industrial standard for parallel computing on multi-processors systems. Its basic principles, simplicity and incremental approach, make it an extremely productive paradigm. Up to version 2.5, OpenMP didn’t directly support par-allelization of algorithms in which more work is generated dynamically and with irregular patterns as data are processed. These algorithms are of growing relevance in the scien-tific realm, and are widespread in most commercial software.
OpenMP 3.0 introduced a new tasking model, that allows work to be dynamically generated and assigned to idle processors. CASPUR was a very active contributor to the new model development.
Dott. Federico Massaioli
CASPUR
Responsabile del Gruppo di Fisica e Fluidodinamica Computazionale
federico.massaioli@caspur.it
Il calcolo parallelo è dunque l’unico approccio possibile perché la velocità delle applicazioni più diffuse cresca di pari passo con la potenza dei computer su cui sono eseguite. Tuttavia il calcolo parallelo, ossia la distribuzione a diversi processori di parti diverse di un’unica elaborazione, è più complesso dell’elaborazione da parte di un solo processore. Basti osservare che utilizza gli stessi approcci ed in-contra le stesse complessità della distribuzione del lavoro tra esseri umani. Divi-dere un attività tra più lavoratori per velocizzarne l’esecuzione richiede innanzitutto del lavoro aggiuntivo: quello di coordinamento, per far sì che alcuni passi dell’attività avvengano nel giusto ordine e per regolare l’accesso a risorse condivise, come gli strumenti di lavoro. In più, suddivisioni diverse tra lo stesso numero di lavoratori possono portare a differenti tempi di esecuzione complessivi dell’attività. Ognuna di queste suddivisioni sarà poi caratterizzata da un numero critico di lavoratori al di sopra del quale il tempo speso nel coordinarsi è non tra-scurabile rispetto a quello dedicato al lavoro utile.
Complessità come quelle appena descritte sono quasi “ordinaria amministra-zione” nell’ambito della ricerca di frontiera, che per definizione si confronta con problemi al limite delle capacità scientifiche e tecnologiche. In questo ambito, inoltre, l’ingegnerizzazione delle applicazioni è semplificata dalla dimensione re-lativamente contenuta dei sorgenti, dal numero rere-lativamente ridotto di funzio-nalità, dall’utenza ristretta ed altamente professionale e dalla relativa lentezza con cui vengono prodotte nuove re-lease. Del tutto di-versa è la situazione nei mercati informa-tici più ampi: vaste basi di utenza non specializzata, appli-cazioni di grandi di-mensioni e molto ricche in funziona-lità, modelli di busi-ness basati sulla produzione di nuove release ogni 12-18 mesi. In un simile contesto un au-mento incontrollato della complessità di un’applicazione può portare gli svilup-patori a fallire gli obiettivi. È evidente la necessità di strumenti semplici che consentano di aumentare le prestazioni dell’applicazione senza renderne lo svi-luppo e la manutenzione ingestibili.
OpenMP è uno standard diffuso per la parallelizzazione di codici su macchine dotate di più processori che condividono l’accesso alla stessa memoria. Si basa sull’inserzione in codici scritti in linguaggi convenzionali, come Fortran, C e C++, di direttive di compilazione, ossia di indicazioni al compilatore su come distribuire, in ogni parte del programma, le istruzioni da eseguire tra differenti CPU. La filosofia
CASPUR ANNU
AL REPOR
T EDIZIONE 2009
• Un modello dinamico in due soli costrutti
Per generare dinamicamente un nuovo task da assegnare ad uno dei processori si utilizza il costrutto:
#pragma omp task {
// codice del task }
Il codice contenuto nel blocco associato alla direttiva può essere eseguito imme-diatamente o successivamente da uno dei processori assegnati al team che esegue in parallelo il codice. Quando un flusso di esecuzione incontra il costrutto:
#pragma omp taskwait
progettuale di OpenMP è basata su tre principi cardine: I) il rispetto delle regole del linguaggio di programmazione; II) la semplicità delle estensioni; III) il supporto di un processo incrementale e modularizzato di parallelizzazione di un codice se-riale preesistente. Di fatto, la maggior parte dei codici OpenMP possono produrre un’equivalente versione seriale semplicemente ignorando le direttive durante la compilazione. La maggiore produttività dei programmatori che utilizzano OpenMP è stata provata da esperimenti in laboratori governativi USA [1]. La semplicità dello standard lo rende facilmente implementabile su differenti architetture har-dware ed in diversi compilatori. In più, le restrizioni imposte in OpenMP rendono possibile l’utilizzo di strumenti di analisi automatica di errori di parallelizzazione. OpenMP è nato nel 1997 da un accordo tra aziende del settore HPC, come uni-ficazione di alcuni sistemi di programmazione parallela proprietari. Inizialmente orientato al mondo del calcolo tecnico scientifico, OpenMP si è poi diffuso anche in altri ambiti. Oggi è disponibile in numerosi compilatori, sia commerciali che gratuiti, su diversi sistemi operativi e diverse piattaforme hardware, incluse con-sole per videogiochi come la Playstation 3 e la XBox 360 e architetture per sistemi embedded come i processori multicore della ARM. L’evoluzione dello standard (le cui specifiche sono disponibili al sito www.openmp.org) è gestito dall’OpenMP Architecture Review Board (ARB), un ente no-profit, composto dalle maggiori aziende del settore, da alcuni centri di ricerca, e da cOMPunity, l’associazione degli utenti di OpenMP. Gli sviluppi tecnici e la stesura delle specifiche è affidata ad un Language Committee, di cui fanno parte esperti degli enti componenti l’ARB.
OpenMP si basa su un modello fork&join, nel quale il flusso di elaborazione di-venta parallelo al momento di distribuire lavoro a processori diversi e ritorna seriale quando le attività parallele sono terminate. Fino alla versione 2.5 delle specifiche, OpenMP ha supportato i due casi d’uso principali del parallelismo. In quello più semplice (Figura 1), un lavoro è composto da molte attività identiche, di quantità nota o stimabile in anticipo, da applicare ripetitivamente e indipendentemente a
Figura 1
dati diversi, e che è facile distribuire equamente tra diversi lavoratori (o processori, in un computer). Nel secondo (Figura 2), il lavoro è costituito da attività differenti ma indipendenti, ed è quindi possibile dividerle comunque tra più lavoratori, cu-rando che il lavoratore che finisce prima degli altri prenda in carico un’altra attività ancora da svolgere. Il vincolo, in ambedue i casi, è che il numero di attività da di-stribuire ai differenti processori sia noto al momento di distribuirle.
L’obiettivo primario fissato dall’ARB per la versione 3.0 di OpenMP era quello di supportare per la prima volta in uno standard industriale la parallelizzazione di forme di parallelismo dinamico ed irregolare, nel quale i flussi di esecuzione pa-rallelo generano ulteriori attività da svolgere, in maniera imprevedibile a priori (Figura 3). Si pensi, ad esempio, ad una simulazione di impatto tra oggetti com-plessi, in cui la geometria dei singoli elementi cambia a seconda dei fenomeni che si verificano localmente, oppure, come analogo umano, ad una ricerca biblio-grafica, nella quale una volta identificati testi pertinenti, questi ultimi possono ri-chiedere ampliamenti ed approfondimenti della ricerca stessa. Molte elaborazioni hanno queste caratteristiche, non solo nel calcolo scientifico, ma soprattutto in settori applicativi ben più ampi, come le basi dati, i videogiochi, la logistica,. Il CASPUR è stato uno dei primi centri al mondo ad adottare lo standard OpenMP ed uno dei primi ad esplorare la sua applicabilità al parallelismo irregolare, par-tecipando attivamente all’ideazione del modello di tasking dinamico di OpenMP, ed alla stesura del nuovo standard, pubblicato a maggio 2008, dopo una fase di sei mesi di commenti pubblici.
Alcuni fantasmi tormentano i lavori dei comitati di standardizzazione ed i sonni dei loro membri: si tratta degli spettri di standard che, dopo la loro promulgazione, si sono rivelati troppo complicati da usare o da implementare ed intrinsecamente inefficienti. Questi pericoli sono maggiori proprio nei casi in cui un nuovo modello di elaborazione deve essere aggiunto ad uno standard già esistente, senza rom-perne la coerenza interna. Il Language Committee ha dedicato molto lavoro a questo aspetto. Per valutare i rischi, è stata realizzata un’implementazione proto-tipale, curata dall’Universitat Politécnica de Catalunya. Il prototipo è stato utilizzato per valutare espressività, facilità d’uso e prestazioni delle estensioni, e gli studi sono stati pubblicati in alcuni lavori [2,3] che sono stati apprezzati per qualità e
CASPUR ANNU
AL REPOR
T EDIZIONE 2009
Figura 2
Attività diverse per contenuto e durata possono comunque es sere eseguite contemporanea mente da più lavoratori, con un opportuno coordinamento.
Figura 3
trasparenza del processo. Coerentemente con la filosofia progettuale di semplicità, alcune idee, per quanto allettanti, sono state prudentemente rinviate ad una pros-sima versione di OpenMP, nell’attesa di raccogliere le esperienze ed i feedback dell’utenza generale.
OpenMP 3.0 è ormai disponibile dall’autunno scorso nei principali compilatori. Il modello di tasking dinamico è già utilizzato in alcune applicazioni, con risultati positivi per la facilità d’uso, per la semplicità di parallelizzazione dei codici, per le prestazioni in esecuzione. I concetti del nuovo modello hanno un grande poten-ziale per essere utilizzati anche nelle architetture che si prospettano all’orizzonte, come i processori manycore, dotati di elevati numeri di core molto semplici, e nelle architetture eterogenee, che integrano processori con caratteristiche e fun-zionalità specializzate. È ragionevole pensare che il modello di tasking di OpenMP diventi la struttura fondamentale di prossime versioni dello standard.
• Bibliografia
[1] Hochstein, L., Carver, J., Shull, F., Asgari, S., & Basili, V. (2005). Parallel Programmer Productivity: A Case Study of Novice Parallel Programmers. ACM/IEEE SC 2005 Conference (SC 2005).
[2] Ayguadé, E., Copty, N., Duran, A., Hoeflinger, J., Lin, Y., Massaioli, F., Teruel, X., Un-nikrishnan, P., & Zhang, G. (2009). The Design of OpenMP Tasks. IEEE Transactions on Par-allel and Distributed Systems, 20, 3, 404-18.
