Che cos'è la "vettorializzazione"?

Question

Diverse volte, ho incontrato questo termine in matlab, fortran ... qualche altro ... ma non ho mai trovato una spiegazione che cosa significhi e cosa faccia? Quindi sto chiedendo qui, che cos'è la vettorializzazione e cosa significa ad esempio che "un ciclo è vettorializzato" ?

Answer 1

Molte CPU hanno " vector " o " SIMD " set di istruzioni che applicano la stessa operazione contemporaneamente a due, quattro o più parti di dati. I moderni chip x86 hanno le istruzioni SSE, molti chip PPC hanno il "Altivec" istruzioni e persino alcuni chip ARM hanno un set di istruzioni vettoriali, chiamato NEON.

" vettorizzazione " (semplificato) è il processo di riscrittura di un ciclo in modo che invece di elaborare un singolo elemento di una matrice N volte, elabori (diciamo) 4 elementi della matrice contemporaneamente N / 4 volte.

(Ho scelto 4 perché è quello che l'hardware moderno ha più probabilità di supportare direttamente; il termine "vettorializzazione" è anche usato per descrivere una trasformazione del software di livello superiore in cui potresti semplicemente astrarre completamente il loop e descrivere semplicemente operando su array anziché gli elementi che li compongono)

---

La differenza tra vettorializzazione e srotolamento del ciclo: Considera il seguente ciclo molto semplice che aggiunge gli elementi di due array e memorizza i risultati in un terzo array.

for (int i=0; i<16; ++i)
    C[i] = A[i] + B[i];

Srotolare questo ciclo lo trasformerebbe in qualcosa del genere:

for (int i=0; i<16; i+=4) {
    C[i]   = A[i]   + B[i];
    C[i+1] = A[i+1] + B[i+1];
    C[i+2] = A[i+2] + B[i+2];
    C[i+3] = A[i+3] + B[i+3];
}

La vettorializzazione, d'altra parte, produce qualcosa del genere:

for (int i=0; i<16; i+=4)
    addFourThingsAtOnceAndStoreResult(&C[i], &A[i], &B[i]);

Where " addFourThingsAtOnceAndStoreResult " è un segnaposto per qualsiasi intrinseco / i utilizzato dal compilatore per specificare istruzioni vettoriali. Nota che alcuni compilatori sono in grado di vettorializzare automaticamente loop molto semplici come questo, che spesso possono essere abilitati tramite un'opzione di compilazione. Algoritmi più complessi richiedono ancora l'aiuto del programmatore per generare un buon codice vettoriale.

Answer 2

Vettorizzazione è il termine per convertire un programma scalare in un programma vettoriale. I programmi vettorizzati possono eseguire più operazioni da un'unica istruzione, mentre lo scalare può operare solo su coppie di operandi contemporaneamente.

Da wikipedia :

Approccio scalare:

for (i = 0; i < 1024; i++)
{
   C[i] = A[i]*B[i];
}

Approccio vettorializzato:

for (i = 0; i < 1024; i+=4)
{
   C[i:i+3] = A[i:i+3]*B[i:i+3];
}

Answer 3

Si riferisce alla capacità di eseguire singole operazioni matematiche su un elenco - o "vettore". - di numeri in un solo passaggio. Lo vedi spesso con Fortran perché è associato al calcolo scientifico, che è associato al supercalcolo, dove è apparsa per la prima volta l'aritmetica vettoriale. Oggi quasi tutte le CPU desktop offrono una qualche forma di aritmetica vettoriale, attraverso tecnologie come SSE di Intel. Le GPU offrono anche una forma di aritmetica vettoriale.

Answer 4

Vettorizzazione è ampiamente utilizzato nell'informatica scientifica in cui enormi blocchi di dati devono essere elaborati in modo efficiente.

Nella vera applicazione di programmazione, so che è usato in NUMPY (non sono sicuro di altro).

Numpy (pacchetto per il calcolo scientifico in python), utilizza vettorializzazione per una rapida manipolazione dell'array n-dimensionale, che generalmente è più lento se fatto con opzioni Python integrate per la gestione degli array.

sebbene ci siano tonnellate di spiegazioni là fuori, QUI È CHE COSA VETTORIZZAZIONE È DEFINITA COME IN NUMPY PAGINA DI DOCUMENTAZIONE

La vettorializzazione descrive l'assenza di cicli espliciti, indicizzazione, ecc. nel codice: queste cose stanno avvenendo, ovviamente, solo "dietro le quinte" in un codice C ottimizzato e precompilato. Il codice vettoriale ha molti vantaggi, tra cui:

1. il codice vettoriale è più conciso e più facile da leggere

2. un numero minore di righe di codice generalmente indica un minor numero di bug

3. il codice assomiglia più da vicino alla notazione matematica standard (rendendo più semplice, in genere, codificare correttamente la matematica costrutti)

4. la vettorializzazione produce più codice “Pythonic”. Senza vettorializzazione, il nostro codice sarebbe disseminato di inefficiente e difficile da leggere per i loop.

Answer 5

La vettorializzazione, in parole semplici, significa ottimizzare l'algoritmo in modo che possa utilizzare le istruzioni SIMD nei processori.

AVX, AVX2 e AVX512 sono i set di istruzioni (intel) che eseguono la stessa operazione su più dati in un'unica istruzione. per es. AVX512 significa che è possibile operare su 16 valori interi (4 byte) alla volta. Ciò significa che se hai un vettore di 16 numeri interi e vuoi raddoppiare quel valore in ciascun numero intero e quindi aggiungere 10 ad esso. Puoi caricare i valori sul registro generale [a, b, c] 16 volte ed eseguire la stessa operazione oppure puoi eseguire la stessa operazione caricando tutti i 16 valori sui registri SIMD [xmm, ymm] ed eseguire l'operazione una volta. Ciò consente di accelerare il calcolo dei dati vettoriali.

Nella vettorializzazione utilizziamo questo a nostro vantaggio, rimodellando i nostri dati in modo da poter eseguire operazioni SIMD su di esso e accelerare il programma.

L'unico problema con la vettorializzazione sono le condizioni di gestione. Perché le condizioni ramificano il flusso di esecuzione. Questo può essere gestito mascherando. Modellando la condizione in un'operazione aritmetica. per esempio. se vogliamo aggiungere 10 al valore se è maggiore di 100. possiamo farlo entrambi.

if(x[i] > 100) x[i] += 10; // this will branch execution flow.

oppure possiamo modellare la condizione in un'operazione aritmetica creando un vettore condizione c,

c[i] = x[i] > 100; // storing the condition on masking vector
x[i] = x[i] + (c[i] & 10) // using mask

questo è un esempio molto banale ... quindi, c è il nostro vettore di mascheramento che usiamo per eseguire operazioni binarie basate sul suo valore. Ciò evita la ramificazione del flusso di esecuzione e consente la vettorializzazione.

La vettorializzazione è importante quanto la parallelizzazione. Pertanto, dovremmo utilizzarlo il più possibile. Tutti i processori moderni hanno istruzioni SIMD per carichi di lavoro di calcolo pesanti. Possiamo ottimizzare il nostro codice per utilizzare queste istruzioni SIMD usando la vettorializzazione, questo è simile alla parallelizzazione del nostro codice per l'esecuzione su più core disponibili su processori moderni.

Vorrei partire con la menzione di OpenMP, che consente di vettorializzare il codice usando pragmas. Lo considero un buon punto di partenza. Lo stesso si può dire per OpenACC.

Answer 6

Vedi le due risposte sopra. Volevo solo aggiungere che la ragione per voler fare la vettorializzazione è che queste operazioni possono essere facilmente eseguite in parallelo da supercomputer e multi-processori, ottenendo un grande guadagno in termini di prestazioni. Sui computer con processore singolo non ci sarà alcun miglioramento delle prestazioni.