Dove potrebbe essere utilizzata la programmazione parallela SPMD in un compilatore?

Question

Dove potrebbe essere utilizzata la programmazione parallela SPMD in un compilatore?

#1 da (1 voti)
#2 da (1 voti)
#3 da (1 voti)
#4 da (1 voti)
#5 da (1 voti)

2

Ho poche conoscenze sui temi della costruzione del compilatore e della programmazione parallela, quindi per favore portami dietro. Questo è un corso sulla costruzione del compilatore e ci viene chiesto di imparare CUDA durante il corso perché il professore vorrebbe che scrivessimo un compilatore per una lingua semplificata. Questo compilatore dovrebbe svolgere il lavoro in parallelo in alcune fasi specifiche. La mia comprensione è che lo scanner, il parser, l'analizzatore semantico, il generatore di codice e l'ottimizzatore sono intrinsecamente sequenziali. Ho scritto alcuni parser per compiti molto semplici, quindi la mia comprensione si basa su un po 'di teoria e un po' di esperienza. Vorrei capire come incorporare lo stato condiviso ad un certo punto nella costruzione del compilatore per fare multiprocessing, ma non SPMD.

Quali componenti di un compilatore possono essere parallelizzati (ad esempio usando CUDA come nel mio caso, il modello SPMD in generale)?

SPMD : Dati multipli per singolo programma

programming-languages parallelism compiler

posta AraK 19.09.2011 - 22:17

fonte

5 risposte

Leggi altre domande sui tag programming-languages parallelism compiler

Esistono buone librerie Java / JVM per la mia architettura di Expression Tree? [chiuso] Come scegliere un formato di pacchetto per la distribuzione del software Linux?

score 1 · Answer 1

Ci sono tutti i tipi di opportunità per gestire il lavoro in parallelo. Le singole linee in un file di codice sorgente possono essere scansionate e tokenizzate indipendentemente l'una dall'altra, ad esempio. I blocchi di codice possono essere analizzati in modo indipendente l'uno dall'altro e possono essere targetizzati per il parallelismo lì.

Alcune tecniche di ottimizzazione si prestano ad essere parallelizzate. Le strutture intermedie contenenti informazioni sull'assegnazione del registro possono, ad esempio, essere generate indipendentemente da diversi blocchi di codice e quindi essere unite insieme in un lungo passaggio alla fine. Molto lavoro intermedio e alcuni lavori di generazione del codice possono essere eseguiti in parallelo: è possibile avere una rappresentazione intermedia completa in cui la generazione del codice può avvenire in parallelo, iniziando contemporaneamente a più punti di partenza.

Naturalmente, tutto ciò suona piuttosto strano. È insolito provare a scrivere un compilatore che usi CUDA (i compilatori al giorno d'oggi sono per lo più abbastanza veloci per la maggior parte degli scopi per cui sono usati, senza parallelizzazione). È molto più comune provare e scrivere un compilatore che compila il codice CUDA e che tenta di introdurre la potenza di elaborazione parallela in codice scritto originariamente per essere eseguito linearmente.

score 1 · Answer 2

...compiler is supposed to be doing the work in parallel at some specific stages.

Il tuo professore sembra avere il contrario, ho paura. O forse l'hai frainteso.

Preferirei che un compilatore producesse il codice di destinazione ottimizzato SPMD (CUDA) generato dalla tua lingua semplificata . In questo modo, ad esempio, la semplice aggiunta di vettori, indipendentemente dal modo in cui viene espressa nella lingua di origine, viene tradotta in un insieme di chiamate API CUDA corrette e ad alte prestazioni.

In questo senso, direi che il compilatore dovrebbe produrre codice di destinazione che esegue il lavoro in parallelo in alcune fasi specifiche . Non importa se lo fa in sequenza - purché il suo codice di uscita sfrutti SPMD.

score 1 · Answer 3

1

Un possibile utilizzo dell'accelerazione SPMD può essere qualcosa di simile ad un'allocazione del registro più aggressiva e alla programmazione delle istruzioni. Vedi questo articolo per l'ispirazione.

risposta data 20.09.2011 - 12:51

fonte

score 1 · Answer 4

La parte interessante sarebbe la fase del linker. La compilazione regolare è comunque in parallelo imbarazzante; basta usare un thread per unità di traduzione. L'unione dei risultati non lo è. Questa è essenzialmente la teoria dei grafi; stai risolvendo riferimenti esterni (archi) ed eliminando le funzioni inutilizzate (sottografi disgiunti).

score 1 · Answer 5

My understanding was that the scanner, parser, semantic analyzer, code generator and the optimizer are inherently sequential

Questo non è completamente vero. Ho avuto alcune idee su come eseguire parser contemporaneamente. Che un parser sia o meno concorrente o meno dipende dal fatto che la struttura della lingua sia atomica.

Per un esempio davvero semplice:

namespace_scope_definition := x | y | z | a | b | c;
namespace := 'namespace' '{' namespace_scope_definition+ '}';
program := namespace+;

Ogni spazio dei nomi, in questo caso, e ogni definizione al suo interno, ha il proprio albero di analisi indipendente. Se dovessi separarli in "atomi", potresti analizzare ogni "atomo" in modo indipendente.

Probabilmente, un analizzatore semantico potrebbe avere la stessa idea di base, e forse anche un ottimizzatore: diverse sezioni della fonte possono essere analizzate / ottimizzate contemporaneamente. Inoltre, puoi lessare ogni file del codice sorgente in modo indipendente.