Come implementare un algoritmo out-of-core?

1

Voglio implementare un algoritmo di clustering parallelo "out-of-core" in CUDA. La mia CPU ha 12 GB di RAM e GPU ha 4 GB di esso. Quello che voglio è che l'intero set di dati dovrebbe essere sul disco, e posso prelevare blocchi di dati da esso, mettere i blocchi nella memoria della CPU, passarli alla GPU, elaborarli lì e archiviare i risultati su disco. La complessità del passo dell'algoritmo originale (in memoria) è O (logN) , N- > no. di punti dati. Per l'algoritmo di memoria esterna, supponiamo che i punti M possano essere contenuti nella memoria in una sola volta, quindi secondo me, la corsa dovrebbe essere

(N/M)*(logM)

(N / M) - > è uguale al numero di tali serie di punti che dovranno essere messi in memoria e durante ogni passaggio, tempo logM per elaborarlo.

In che modo questo tempo di esecuzione si riferisce al tempo di I / O tra il disco e la memoria, cioè ho già preso in considerazione il tempo di I / O usando (N / M) o sto lasciando qualcosa fuori? Questa analisi è corretta o devo sapere di più su Input / Output per implementare un algoritmo usando la memoria esterna?

    
posta pymd 21.04.2014 - 19:58
fonte

1 risposta

1

Il costo del tempo di I / O sarà un numero basato su N, dal momento che alla fine leggerete N oggetti dal disco. Quindi potrebbe essere incluso nella stima della complessità, supponendo che il tuo metodo di "picking blocks" sia costante.

Ricorda, questo ti dice solo l'ordine generale di complessità dell'algoritmo, e i fattori che giocano il ruolo più importante in quella complessità per grandi valori di N.

    
risposta data 21.04.2014 - 20:30
fonte

Leggi altre domande sui tag