Un programma Transpose Matrix efficiente per la cache?

Quindi il modo ovvio per trasporre una matrice è usare:

for( int i = 0; i < n; i++ ) for( int j = 0; j < n; j++ ) destination[j+i*n] = source[i+j*n]; 

ma voglio qualcosa che sfrutti la localizzazione e il blocco della cache. Stavo cercando e non ho trovato il codice che avrebbe fatto questo, ma mi è stato detto che dovrebbe essere una modifica molto semplice all’originale. Qualche idea?

Edit: ho una matrice 2000×2000, e voglio sapere come posso cambiare il codice usando due loop for , in pratica suddividendo la matrice in blocchi che ho trasposto individualmente, diciamo 2×2 blocchi o 40×40 blocchi, e vediamo quale dimensione del blocco è più efficiente.

Edit2: Le matrici sono memorizzate in ordine di colonna principale, vale a dire per una matrice

 a1 a2 a3 a4 

è memorizzato come a1 a3 a2 a4 .

Probabilmente vorrai quattro loop: due per scorrere i blocchi, e poi altri due per eseguire la trasposizione-copia di un singolo blocco. Supponendo, per semplicità, una dimensione del blocco che divide la dimensione della matrice, credo che qualcosa del genere, anche se mi piacerebbe disegnare alcune immagini sul retro delle buste per essere sicuro:

 for (int i = 0; i < n; i += blocksize) { for (int j = 0; j < n; j += blocksize) { // transpose the block beginning at [i,j] for (int k = i; k < i + blocksize; ++k) { for (int l = j; l < j + blocksize; ++l) { dst[k + l*n] = src[l + k*n]; } } } } 

Un'ulteriore importante intuizione è che in realtà c'è un algoritmo cache-oblivious per questo (vedi http://en.wikipedia.org/wiki/Cache-oblivious_algorithm , che usa questo esatto problema come esempio). La definizione informale di "cache-oblivious" è che non è necessario sperimentare il tweaking di alcun parametro (in questo caso il blocco) per ottenere prestazioni cache buone / ottimali. La soluzione in questo caso è di trasporre dividendo ricorsivamente la matrice a metà e trasporre le metà nella loro posizione corretta nella destinazione.

Qualunque sia la dimensione della cache, questa ricorsione ne approfitta. Prevedo che ci sia un po 'di overhead di gestione extra rispetto alla vostra strategia, che consiste nell'usare esperimenti di performance per, in effetti, saltare direttamente al punto della ricorsione in cui la cache entra davvero in gioco e non andare oltre. D'altra parte, i tuoi esperimenti sulle prestazioni potrebbero darti una risposta che funziona sulla tua macchina ma non sulle macchine dei tuoi clienti.

Ho avuto lo stesso identico problema di ieri. Ho finito con questa soluzione:

 void transpose(double *dst, const double *src, size_t n, size_t p) noexcept { THROWS(); size_t block = 32; for (size_t i = 0; i < n; i += block) { for(size_t j = 0; j < p; ++j) { for(size_t b = 0; b < block && i + b < n; ++b) { dst[j*n + i + b] = src[(i + b)*p + j]; } } } } 

Questa è 4 volte più veloce della soluzione ovvia sulla mia macchina.

Questa soluzione si prende cura di una matrice rettangular con dimensioni che non sono un multiplo della dimensione del blocco.

se dst e src sono la stessa matrice quadrata, in realtà dovrebbe essere usata una funzione sul posto:

 void transpose(double*m,size_t n)noexcept{ size_t block=0,size=8; for(block=0;block+size-1 

Ho usato C ++ 11 ma questo potrebbe essere facilmente tradotto in altre lingue.

Invece di trasporre la matrice in memoria, perché non comprimere l’operazione di trasposizione nella prossima operazione che farai sulla matrice?

Steve Jessop ha menzionato un algoritmo di trasposizione della matrice ignota nella cache. Per la cronaca, voglio condividere una ansible implementazione di una trasposizione di matrici cache ignari.

 public class Matrix { protected double data[]; protected int rows, columns; public Matrix(int rows, int columns) { this.rows = rows; this.columns = columns; this.data = new double[rows * columns]; } public Matrix transpose() { Matrix C = new Matrix(columns, rows); cachetranspose(0, rows, 0, columns, C); return C; } public void cachetranspose(int rb, int re, int cb, int ce, Matrix T) { int r = re - rb, c = ce - cb; if (r <= 16 && c <= 16) { for (int i = rb; i < re; i++) { for (int j = cb; j < ce; j++) { T.data[j * rows + i] = data[i * columns + j]; } } } else if (r >= c) { cachetranspose(rb, rb + (r / 2), cb, ce, T); cachetranspose(rb + (r / 2), re, cb, ce, T); } else { cachetranspose(rb, re, cb, cb + (c / 2), T); cachetranspose(rb, re, cb + (c / 2), ce, T); } } } 

Maggiori dettagli sugli algoritmi cache ignari possono essere trovati qui .

Viene in mente la moltiplicazione delle matrici , ma il problema della cache è molto più pronunciato, perché ogni elemento viene letto N volte.

Con la trasposizione della matrice, stai leggendo in un singolo passaggio lineare e non c’è modo di ottimizzarlo. Ma è ansible elaborare contemporaneamente più righe in modo da scrivere diverse colonne e quindi riempire le linee complete della cache. Avrai solo bisogno di tre anelli.

Oppure fai il contrario e leggi le colonne mentre scrivi in ​​modo lineare.

Con una matrice grande, possibilmente una matrice sparsa di grandi dimensioni, potrebbe essere un’idea scomporla in blocchi più piccoli della cache (Supponiamo, matrici sub 4×4). Puoi anche contrassegnare le matrici secondarie come id quadro che ti aiuteranno nella creazione di percorsi di codice ottimizzati.