Avanzare nella parallelizzazione con il machine learning
Un nuovo metodo utilizza AST aumentati per migliorare il rilevamento del codice parallelo.
― 7 leggere min
Indice
Negli ultimi anni, c'è stato un crescente interesse a far girare i programmi al computer più velocemente usando più core dei processori. Questo processo si chiama Parallelizzazione. Tuttavia, trovare parti di un programma che possono essere eseguite in parallelo non è facile, nemmeno per i programmatori esperti. I metodi tradizionali possono perdere opportunità di accelerare l'esecuzione del codice trascurando certi cicli dove le attività possono essere svolte contemporaneamente.
Molti studi si sono rivolti all'Apprendimento Automatico, dove i computer apprendono dai dati, per aiutare a identificare queste sezioni parallellizzabili nel codice. Anche se l'apprendimento automatico mostra promesse, ci sono alcune sfide. Un problema principale è la disponibilità di buoni dati per addestrare i modelli di apprendimento automatico. Inoltre, rappresentare il codice in un modo che catturi tutte le sue caratteristiche importanti è fondamentale per un'analisi di successo. Questo articolo presenta un nuovo metodo che utilizza un tipo speciale di rappresentazione del codice chiamato albero di sintassi astratta aumentata (AST) per aiutare a rilevare il parallelismo nei programmi.
Rilevare Codice Parallellizzabile
Rilevare cicli nel codice che possono girare in parallelo è complesso. La maggior parte degli strumenti esistenti si basa o sull'analisi del codice prima che giri (Analisi Statica) o sull'osservazione di come gira il codice (Analisi Dinamica) per identificare il parallelismo.
Gli strumenti di analisi statica guardano al codice sorgente senza eseguirlo, ma possono perdere il parallelismo perché adottano un approccio cauto per garantire la correttezza. Gli strumenti dinamici raccolgono informazioni mentre il codice è in esecuzione, ma possono essere lenti e richiedere molte risorse. Gli sviluppatori devono anche avere una buona comprensione sia del modello di programmazione con cui stanno lavorando sia del codice stesso per ottenere buone prestazioni, il che può essere un onere.
Questo articolo introduce un approccio di apprendimento automatico che combina questi metodi usando una forma arricchita di AST. Questo permette al modello di capire meglio la struttura e le relazioni all'interno del codice.
Metodologia Proposta
Raccolta e Generazione Dati
Gli autori hanno costruito un dataset chiamato dataset OMP Serial, che include esempi di cicli da varie fonti. Hanno raccolto codice reale da GitHub e generato codice sintetico per creare un dataset bilanciato. Questo dataset include cicli etichettati che sono sia parallellizzabili che non parallellizzabili.
Elaborazione Dati
Per preparare i dati, gli autori hanno intrapreso vari passaggi. Hanno estratto i cicli dal codice sorgente, rimosso commenti e spazi bianchi non necessari e etichettato il codice secondo specifici schemi di parallelizzazione. Questa lavorazione attenta assicura che il dataset sia di alta qualità e pronto per l'analisi.
Rappresentazione del Codice
Il nuovo approccio utilizza una struttura grafica speciale che cattura sia il testo che la struttura del codice. Questa rappresentazione aiuta il modello di apprendimento automatico a identificare schemi e relazioni all'interno del codice meglio dei metodi tradizionali.
Background
Importanza della Programmazione Parallela
Con i sistemi computerizzati a più core che diventano comuni, creare programmi che sfruttano questo hardware è cruciale per migliorare le prestazioni. I programmatori spesso affrontano sfide quando cercano di parallelizzare il loro codice, specialmente per cicli complessi.
Strumenti per l'Auto-Parallelizzazione
Esistono vari strumenti per aiutare ad automatizzare il processo di parallelizzazione. Alcuni di questi strumenti usano analisi statica, mentre altri si basano su informazioni dinamiche raccolte durante l'esecuzione del programma. Ogni tipo ha i suoi punti di forza e debolezza. Ad esempio, gli strumenti statici possono trascurare potenziali parallelismi, mentre gli strumenti dinamici possono richiedere risorse significative per analizzare il codice in modo efficace.
Apprendimento Automatico nella Parallelizzazione
Le tecniche di apprendimento automatico hanno iniziato a farsi strada nel campo dell'analisi dei programmi. Rethinking problemi tradizionali nell'ingegneria del software, i ricercatori possono usare l'apprendimento automatico per identificare sezioni di codice parallellizzabili. Questi metodi possono classificare il codice basandosi su schemi appresi piuttosto che su regole rigide.
Studi recenti hanno applicato diverse tecniche di apprendimento automatico all'analisi dei programmi, mostrando vari gradi di successo. Tuttavia, molti affrontano ancora sfide nella qualità del dataset e nella rappresentazione del codice.
Rappresentazione del Codice
Rappresentazioni Basate su Token
Un metodo comune per rappresentare il codice è tramite token, che sono i mattoni fondamentali del codice sorgente. La tokenizzazione può essere utile, ma spesso manca delle informazioni strutturali necessarie per fare previsioni precise sul parallelismo.
Albero di Sintassi Astratta (AST)
Un AST rappresenta la struttura del codice in modo più efficace rispetto ai metodi basati su token. Cattura le relazioni tra i diversi componenti del codice, permettendo una migliore comprensione del suo comportamento.
Grafico del Flusso di Controllo (CFG)
Il Grafico del Flusso di Controllo offre intuizioni sull'ordine di esecuzione del codice, mostrando come diverse istruzioni si connettono. Sebbene utile, il CFG da solo non fornisce informazioni sufficienti sulle dipendenze dei dati che possono influenzare le decisioni di parallelizzazione.
Rappresentazione Grafica Eterogenea
Combinare AST e CFG in una sola struttura grafica fornisce una rappresentazione più ricca del codice. La nuova rappresentazione aumentata cattura sia elementi strutturali che testuali, abilitando un'analisi migliore e previsioni più accurate sul parallelismo.
Reti Neurali Grafiche Eterogenee (HGNN)
Le Reti Neurali Grafiche (GNN) hanno avuto successo in vari settori come la biologia e l'elaborazione delle immagini. HGNN estende l'idea di GNN permettendo vari tipi di nodi e bordi, il che aiuta a modellare le relazioni in modo più significativo. Questo approccio rende possibile estrarre informazioni più ricche dal grafo durante l'addestramento.
Esperimenti
Valutazione delle Prestazioni
Gli autori hanno condotto vari esperimenti per testare il loro nuovo metodo rispetto agli strumenti esistenti. Hanno confrontato le prestazioni del loro approccio con strumenti tradizionali e altre tecniche di apprendimento automatico.
Risultati
I risultati hanno mostrato che la nuova rappresentazione ha superato i metodi esistenti nell'identificazione del parallelismo nel codice. L'approccio Graph2Par è riuscito a rilevare più cicli paralleli rispetto agli strumenti tradizionali.
Classificazione dei Pragma OpenMP
Oltre a rilevare il parallelismo, gli autori hanno valutato quanto bene il loro modello può prevedere specifici pragma OpenMP, inclusi "private" e "reduction". Anche se il modello ha mostrato buone prestazioni in alcune aree, ha faticato in altre, indicando che c'è ancora spazio per miglioramenti.
Casi Studio
Gli autori hanno evidenziato esempi specifici in cui il loro approccio ha rilevato con successo cicli paralleli che sono stati trascurati dagli strumenti tradizionali. Questo suggerisce che il loro metodo può offrire intuizioni e opportunità di ottimizzazione preziose che altrimenti potrebbero passare inosservate.
Conclusione
In sintesi, il metodo proposto presenta un approccio promettente all'auto-parallelizzazione attraverso una nuova rappresentazione del codice e tecniche di apprendimento automatico. Affrontando sfide come la carenza di dati e la rappresentazione del codice, questa ricerca contribuisce a far progredire il campo dell'analisi dei programmi e dell'auto-parallelizzazione. I lavori futuri potrebbero coinvolgere il perfezionamento del modello ulteriormente ed esplorare funzionalità aggiuntive per migliorare le sue prestazioni su una gamma più ampia di costrutti di programmazione.
Direzioni Future
Anche se questo studio fa progressi significativi, ci sono ancora opportunità per ulteriori ricerche. Esplorare schemi più complessi e migliorare la capacità del modello di gestire scenari diversi sarebbe prezioso. Inoltre, integrare il modello con ambienti di sviluppo esistenti potrebbe aiutare a rendere il processo di parallelizzazione più accessibile per gli sviluppatori.
Implicazioni per gli Sviluppatori
In definitiva, il successo di nuove tecniche come questa può aiutare i programmatori a creare codice più efficiente che possa sfruttare le capacità hardware moderne. Semplificando il processo di identificazione del parallelismo nel loro codice, gli sviluppatori possono migliorare le prestazioni e ridurre il carico di lavoro richiesto per l'ottimizzazione manuale.
Titolo: Learning to Parallelize with OpenMP by Augmented Heterogeneous AST Representation
Estratto: Detecting parallelizable code regions is a challenging task, even for experienced developers. Numerous recent studies have explored the use of machine learning for code analysis and program synthesis, including parallelization, in light of the success of machine learning in natural language processing. However, applying machine learning techniques to parallelism detection presents several challenges, such as the lack of an adequate dataset for training, an effective code representation with rich information, and a suitable machine learning model to learn the latent features of code for diverse analyses. To address these challenges, we propose a novel graph-based learning approach called Graph2Par that utilizes a heterogeneous augmented abstract syntax tree (Augmented-AST) representation for code. The proposed approach primarily focused on loop-level parallelization with OpenMP. Moreover, we create an OMP\_Serial dataset with 18598 parallelizable and 13972 non-parallelizable loops to train the machine learning models. Our results show that our proposed approach achieves the accuracy of parallelizable code region detection with 85\% accuracy and outperforms the state-of-the-art token-based machine learning approach. These results indicate that our approach is competitive with state-of-the-art tools and capable of handling loops with complex structures that other tools may overlook.
Autori: Le Chen, Quazi Ishtiaque Mahmud, Hung Phan, Nesreen K. Ahmed, Ali Jannesari
Ultimo aggiornamento: 2023-05-09 00:00:00
Lingua: English
URL di origine: https://arxiv.org/abs/2305.05779
Fonte PDF: https://arxiv.org/pdf/2305.05779
Licenza: https://creativecommons.org/licenses/by/4.0/
Modifiche: Questa sintesi è stata creata con l'assistenza di AI e potrebbe presentare delle imprecisioni. Per informazioni accurate, consultare i documenti originali collegati qui.
Si ringrazia arxiv per l'utilizzo della sua interoperabilità ad accesso aperto.