Quali sono alcuni suggerimenti che un algoritmo dovrebbe parallelizzare?

Question

La mia esperienza fino ad ora mi ha dimostrato che anche con processori multi-core, parallelizzare un algoritmo non sempre lo accelera in modo notevole. In effetti, a volte può rallentare le cose. Quali sono alcuni buoni suggerimenti per accelerare significativamente un algoritmo parallelizzando?

(Naturalmente dato i caveat con ottimizzazione prematura e la loro correlazione con il male)

Answer 1

Per ottenere il massimo beneficio dalla parallelizzazione, un compito dovrebbe essere in grado di essere rotto in pezzi corso di grana similiar dimensioni che sono indipendenti (o principalmente così), e richiedono poca comunicazione di dati o sincronizzazione tra i blocchi.

La parallelizzazione a grana fine, soffre quasi sempre di sovraccarichi, e avrà un'accelerazione finita indipendentemente dal numero di core fisici disponibili.

[L'avvertenza a questo, sono quelle architetture che hanno un no molto grande. di 'core' (come le macchine di connessione 64.000 core). Questi sono adatti per i calcoli che possono essere suddivisi in azioni relativamente semplici assegnate a una topologia particolare (come una mesh rettangolare).]

Answer 2

Beh, se hai bisogno di molte serrature per farlo funzionare, probabilmente è uno di quelli algoritmi difficili che non si adattano bene. Esiste qualche parte dell'algoritmo che può essere suddiviso in parti separate che non devono necessariamente toccarsi?

Answer 3

In primo luogo, date un'occhiata a questo articolo di tardo Jim Gray:

Distributed Computing Economics

In realtà, questo sarà chiarire un equivoco in base a quello che hai scritto nella domanda. Ovviamente, se meno il problema che si pone è quello di essere discretizzati, tanto più difficile sarà.

Answer 4

Se è possibile dividere il lavoro in parti indipendenti, è possibile procedere parallelamente.

Ricorda anche Amdahl's Law che è un promemoria che fa riflettere su quanto poco possiamo aspettarci in termini di guadagni di prestazioni aggiungendo più core alla maggior parte dei programmi.

Answer 5

Ogni volta che si dispone di calcoli che dipendono da calcoli precedenti, non si tratta di un problema parallelo. Cose come l'elaborazione lineare delle immagini, i metodi di forza bruta e gli algoritmi genetici sono tutti facilmente paralleli.

Una buona analogia è ciò su cui potresti lavorare per far sì che un gruppo di amici possa fare diverse parti contemporaneamente? Ad esempio, mettere insieme i mobili ikea potrebbe parallelizzare bene se diverse persone possono lavorare su sezioni diverse, ma lo sfondo potrebbe non farlo perché è necessario eseguire i muri in sequenza.

Answer 6

Se si eseguono calcoli a matrice di grandi dimensioni, come le simulazioni che coinvolgono modelli ad elementi finiti, questi possono spesso essere suddivisi in pezzi più piccoli in modo diretto. I moltiplicatori del vettore di matrice possono trarre beneficio dalla parallelizzazione, assumendo che si tratti di matrici molto grandi. A meno che non ci sia un vero collo di bottiglia nelle prestazioni che sta causando l'esecuzione del codice lentamente, probabilmente non è necessario complicare l'elaborazione parallela.