Perché esprimere calcoli come moltiplicazioni di matrice li rende più veloci?

Question

Perché esprimere calcoli come moltiplicazioni di matrice li rende più veloci?

#1 da (16 voti)
#2 da (3 voti)
#3 da (-1 voti)

14

Nel tutorial MNist di TensorFlow di Google, viene mostrato un calcolo in cui un passo equivale a moltiplicare una matrice per un vettore. Google mostra per prima cosa un'immagine in cui ogni moltiplicazione e aggiunta numerica che andrebbero ad eseguire il calcolo è scritta per esteso. Successivamente, mostrano un'immagine in cui viene invece espressa come una moltiplicazione di matrice, sostenendo che questa versione del calcolo è, o almeno potrebbe essere, più veloce:

If we write that out as equations, we get:

We can "vectorize" this procedure, turning it into a matrix multiplication and vector addition. This is helpful for computational efficiency. (It's also a useful way to think.)

So che equazioni come questa sono solitamente scritte nel formato di moltiplicazione della matrice da operatori di apprendimento automatico e possono ovviamente vedere dei vantaggi nel fare ciò dal punto di vista della precisione del codice o della comprensione della matematica. Quello che non capisco è l'affermazione di Google che la conversione dalla forma lunga alla forma matrice "è utile per l'efficienza computazionale"

Quando, perché e in che modo sarebbe possibile ottenere miglioramenti delle prestazioni nel software esprimendo i calcoli come moltiplicazioni di matrice? Se dovessi calcolare la moltiplicazione della matrice nella seconda immagine (basata su matrice) io stesso, come un essere umano, lo farei facendo in sequenza ciascuno dei calcoli distinti mostrati nella prima immagine (scalare). Per me, non sono altro che due notazioni per la stessa sequenza di calcoli. Perché è diverso per il mio computer? Perché un computer è in grado di eseguire il calcolo della matrice più rapidamente di uno scalare?

performance matrices

posta Mark Amery 11.03.2016 - 12:45

fonte

3 risposte

3

(sparse) La moltiplicazione del vettore matrice è altamente parallelizzabile. Il che è molto utile se i tuoi dati sono grandi e hai una server farm a tua disposizione.

Questo significa che puoi dividere la matrice e il vettore in blocchi e lasciare che macchine separate facciano un po 'del lavoro. Quindi condividi alcuni dei loro risultati e poi ottieni il risultato finale.

Nel tuo esempio le operazioni sarebbero le seguenti

imposta una griglia di processori ognuno con un Wx, y secondo la loro coordinata nella griglia
trasmette il vettore sorgente lungo ogni colonna (costo O(log height) )
hanno ciascun processore per la moltiplicazione localmente (costo O(width of submatrix * heightof submatrix) )
comprime il risultato lungo ogni riga utilizzando una somma (costo O(log width) )

Quest'ultima operazione è valida perché la somma è associativa.

Ciò consente anche di costruire ridondanza e di evitare di dover inserire tutte le informazioni in una singola macchina.

Per le piccole matrici 4x4 come quelle che vedi nella grafica è perché la cpu ha istruzioni speciali e registri per gestire tali operazioni.

risposta data 11.03.2016 - 13:08

fonte

-1

La cosa più istruttiva sarebbe confrontare le prestazioni del tuo codice con le prestazioni della moltiplicazione della matrice implementata con Alredy.

C'è sempre qualche ottimizzazione di livello inferiore a cui non hai pensato, qui puoi trovare un esempio:

link

risposta data 31.05.2018 - 11:40

fonte

Leggi altre domande sui tag performance matrices

Licenza Open Source che impedisce la rivendita Collection.stream (). filter (). forEach () è inefficiente rispetto a uno standard per ogni ciclo?

score 16 · Accepted Answer

Può sembrare ovvio, ma i computer non eseguono formule , eseguono code e quanto tempo impiega l'esecuzione dipende direttamente dal codice che eseguono e solo indirettamente su qualunque concetto venga implementato dal codice. Due pezzi di codice logicamente identici possono avere caratteristiche prestazionali molto diverse. Alcuni motivi che potrebbero verificarsi in particolare nella moltiplicazione della matrice:

Uso di più thread. Non c'è quasi nessuna CPU moderna che non abbia core multipli, molti ne hanno fino a 8, e macchine specializzate per l'elaborazione ad alte prestazioni possono facilmente avere 64 su più socket. Scrivere codice in modo ovvio, in un normale linguaggio di programmazione, usa solo uno di quelli. In altre parole, può utilizzare meno del 2% delle risorse di calcolo disponibili della macchina su cui è in esecuzione.
Usando le istruzioni SIMD (in modo confuso, questo è anche chiamato "vettorizzazione" ma in un senso diverso rispetto alle virgolette di testo nella domanda). In sostanza, invece di 4 o 8 o più istruzioni aritmetiche scalari, dare l'istruzione one della CPU che esegue l'aritmetica su 4 o 8 o più registri in parallelo. Questo può letteralmente fare alcuni calcoli (quando sono perfettamente indipendenti e adatti al set di istruzioni) 4 o 8 volte più veloci.
Rendere più intelligente l'uso della cache . L'accesso alla memoria è più veloce se sono temporalmente e spazialmente coerenti , cioè gli accessi consecutivi sono agli indirizzi vicini e quando si accede a un indirizzo due volte lo si accede due volte in rapida successione piuttosto che con una lunga pausa.
Utilizzo di acceleratori come GPU. Questi dispositivi sono animali molto diversi dalle CPU e programmarli in modo efficiente è una forma d'arte tutta sua. Ad esempio, hanno centinaia di core, raggruppati in gruppi di poche decine di core, e questi gruppi condividono le risorse - condividono alcuni KiB di memoria che sono molto più veloci della memoria normale e quando un qualsiasi core del gruppo esegue un if dichiarazione tutti gli altri in quel gruppo devono attendere.
Distribuisci il lavoro su più macchine (molto importante nei supercomputer!) che introduce un enorme insieme di nuovi mal di testa ma, naturalmente, può , dare accesso a risorse informatiche di gran lunga maggiori.
Algoritmi più intelligenti. Per la moltiplicazione della matrice, l'algoritmo semplice O (n ^ 3), opportunamente ottimizzato con i trucchi sopra, è spesso più veloce di il sub -cubic per dimensioni ragionevoli della matrice, ma a volte vince. Per casi speciali come le matrici sparse, puoi scrivere algoritmi specializzati.

Un sacco di persone intelligenti hanno scritto molto codice efficiente per le operazioni di algebra lineare comune , usando i trucchi sopra e molti altri e di solito anche con stupidi trucchi specifici per piattaforma. Pertanto, la trasformazione della formula in una moltiplicazione di matrice e quindi l'implementazione di tale calcolo chiamando in una libreria di algebra lineare matura beneficia di tale sforzo di ottimizzazione. Al contrario, se si scrive semplicemente la formula in modo ovvio in un linguaggio di alto livello, il codice macchina generato alla fine non utilizzerà tutti questi trucchi e non sarà altrettanto veloce. Questo è anche vero se prendi la formulazione della matrice e la implementa chiamando una routine di moltiplicazione della matrice naif che tu stesso hai scritto (di nuovo, in modo ovvio).

Rendere il codice veloce richiede lavoro , e spesso un bel po 'di lavoro se vuoi quell'ultima oncia di prestazioni. Poiché così tanti calcoli importanti possono essere espressi come combinazione di un paio di operazioni di algebra lineare, è economico creare codice altamente ottimizzato per queste operazioni. Il tuo caso d'uso specializzato, una tantum, però? A nessuno importa di questo, tranne te, quindi ottimizzarlo non è economico.