Algoritmo parallelo: calcoli sul grafico

Question

Algoritmo parallelo: calcoli sul grafico

#1 da (1 voti)
#2 da (0 voti)

1

Ho una domanda di programmazione parallela generale.

Supponiamo che ci sia un grafico diretto con cicli. Supponiamo che ogni nodo abbia una piccola quantità di bordi in entrata ~ da 0 a 20 e una quantità potenzialmente abbastanza grande di bordi in uscita ~ da 0 a 500. Diciamo che ogni nodo è una funzione che ottiene tutti i bordi in entrata come parametri di input, calcola i risultati e se il risultato calcolato differisce dal risultato precedente di questa funzione, sarà necessario richiamare il ricalcolo di tutte le funzioni sui bordi in uscita.

Ho bisogno che le funzioni siano calcolate praticamente in onde dalla funzione modificata a tutto ciò che è collegato ad essa nella prima onda e quindi tutte le funzioni connesse alle funzioni della prima ondata e così via. Attualmente l'ho fatto in sequenza, con due liste: l'onda corrente con tutte le funzioni che sta calcolando ora e l'onda successiva che verrà calcolata nella prossima ondata. Tutto funziona correttamente, ma voglio farlo parallelo - per essere calcolato su tutti i core disponibili.

Il problema che sto affrontando è in realtà ogni funzione è molto semplice e quindi viene calcolata molto velocemente e quindi il tempo di calcolo è paragonabile con il tempo all'aggiunta alla prossima ondata. Di conseguenza, l'esecuzione su 4 core è più lenta di quel codice sequenziale.

Esiste un algoritmo parallelo in grado di gestire tali grafici?

parallelism parallel-programming

posta EugeneL 22.03.2017 - 23:52

fonte

2 risposte

Leggi altre domande sui tag parallelism parallel-programming

Riepilogo automatico: intero testo o paragrafi Domanda di modellazione del database

score 1 · Answer 1

Supponendo che il tuo grafico sia sufficientemente grande, vuoi eseguire contrazione del bordo fino a quando ciascun nodo rappresenta un'unità sufficientemente grande di lavorare per ammortizzare il sovraccarico parallelo. Quindi elaborare il grafico normalmente, ma assegnando gruppi di vertici a un thread da elaborare piuttosto che uno solo alla volta.

Il motivo per cui è necessario che il grafico sia grande è che la contrazione dei margini è un tempo lineare e sembra che il tuo problema sia anche il tempo lineare (con un fattore costante simile). Ma dal momento che la contrazione del bordo si bilancia bene, dovresti essere in grado di usarlo per fare in modo che il tuo programma raggiunga l'accelerazione lineare, quindi essere più veloce su grafici sufficientemente grandi.

Questo diventa abbastanza simile al problema del partizionamento del grafico (di cui la contrazione del bordo è spesso un passo). Esistono diversi pacchetti di partizionamento grafico parallelo che si adattano relativamente bene:

link
link

score 0 · Answer 2

Per prima cosa vorrei profilare il codice parallelo, per vedere dove perde tempo. Quindi inizia a ottimizzare:

Potresti dividere l'algoritmo in due fasi: 1. Fase: calcola le funzioni su ciascun nodo, dove qualcosa è cambiato. 2. Fase: propagazione dei valori, recuperando da ogni nodo, dove gli input sono cambiati. Quindi continua. Ogni fase viene elaborata da più thread, sincronizzati dopo ogni fase.

La tua soluzione basata sulla coda potrebbe essere elaborata da più thread. Il problema consiste nell'ordinare o assegnare la priorità ai nodi in modo tale che è possibile iniziare a calcolare l'onda successiva mentre è ancora necessario elaborare alcuni nodi della prima ondata.

Etc.