Matrix benchmark di implementazione, dovrei frustare me stesso?

Question

Sto cercando di scoprire alcuni benchmark moltiplicazione di matrici / inversione on-line. Mio C ++ attuazione attualmente può invertire una matrice 100 x 100 a 38 secondi, ma rispetto a questo benchmark ho trovato, le performance di mia implementazione veramente schifo. Non so se si tratta di un super-ottimizzato qualcosa o se davvero si può facilmente invertire una matrice di 200 x 200 in circa 0,11 secondi, quindi non vedo per maggiori benchmark per confrontare i risultati. Avete qualche dio buon collegamento?

Aggiorna Ho notato un bug nel mio codice moltiplicazione, che non influisce sul risultato, ma è stato causando spreco inutile ciclo. Ora il mio inversione eseguito in 20 secondi. E 'ancora un sacco di tempo, e ogni idea è il benvenuto.

Grazie ragazzi

Answer 1

Questo tipo di operazione è estremamente sensibile della cache. Si vuole fare la maggior parte del vostro lavoro su variabili che sono nella cache L1 e L2. Scopri la sezione 6 di questo documento:

http://people.redhat.com/drepper/cpumemory.pdf

Si ti guida attraverso l'ottimizzazione di una matrice di moltiplicare in modo cache-ottimizzato e ottiene alcuni grandi miglioramenti perf.

Answer 2

Controlla se si passa enormi oggetti di matrice per valore (come questo potrebbe essere costoso se copiare l'intera matrice).
Se passaggio possable per riferimento.

La cosa da matrici e C ++ è che si vuole evitare di copiare quanto possable.
Così il vostro obiettivo principale dovrebbe probabilmente non conatain la "Data Matrix", ma piuttosto contengono meta-dati sulla matrice e un puntatore (avvolto in da somthing intelligente) alla porzione di dati. Così, quando la copia di un oggetto si copia solo una piccola porzione di dati non del tutto (vedi implementazione stringa per un esempio).

Answer 3

Perché è necessario implementare la propria libreria di matrice in primo luogo? Come hai già scoperto, ci sono già le librerie estremamente efficienti disponibili facendo la stessa cosa. E per quanto la gente piace pensare di C ++ come linguaggio prestazioni, questo è vero solo se sei davvero bravo in lingua. E 'estremamente facile scrivere il codice terribilmente lento in C ++.

Answer 4

  

Non so se si tratta di un super-ottimizzato   qualcosa o se davvero si può facilmente   invertire una matrice 200 x 200 in merito   0.11 secondi

MATLAB fa che, senza una goccia di sudore neanche. Stai Attuazione del LAPACK routine per inversione di matrice (ad esempio decomposizione LU)?

Answer 5

Hai provato profiling vero?

A seguito di tale (pdf), il calcolo per una matrice 100x100 con decomposizione LU dovranno 1348250 (operazioni in virgola mobile). Un nucleo 2 può fare circa 20 Gigaflop (metriche processore ) . Quindi, teoricamente parlando si può fare un'inversione a 1 ms.

Senza il codice è piuttosto difficile far valere ciò che è la causa del grande divario. Dalla mia esperienza cercando di micro-ottimizzazione come il ciclo di svolgimento, i valori di caching, vedere, filettatura, ecc, è solo otterrà una velocità massima, che nel migliore dei casi è solo un fattore costante di voi corrente (che forse abbastanza per voi).

Ma se volete un ordine di grandezza la velocità aumenta si dovrebbe dare un'occhiata al vostro algoritmo, forse l'implementazione di decomposizione LU hanno un bug. Un altro posto per dare un'occhiata è l'organizzazione dei dati, provare diversa organizzazione, mettere riga / colonne elementi insieme.

Answer 6

Il LINPACK parametri di riferimento si basano sulla soluzione dei problemi di algebra lineare. Sono disponibili per le diverse macchine e lingue . Forse ti può aiutare, anche.

LINPACK C ++ librerie disponibili qui , anche.

Answer 7

In realtà ho guadagnato circa 7 secondi utilizzando ** double ** S invece di ** long double ** s, ma questo non è un grande affare da quando ho perso la metà del mio precisione.