Ho appena letto un articolo su una svolta nella moltiplicazione delle matrici; un algoritmo che è O (n^2.373). Ma immagino che la moltiplicazione della matrice sia qualcosa che può essere parallelizzato. Quindi, se mai iniziamo a produrre processori per il millesimo core, questo diventerà irrilevante? Come cambierebbero le cose?Gli algoritmi sono classificati nella notazione big-o interessata dal parallelismo?
Se il calcolo quantico giunge a qualcosa di pratico un giorno, allora sì, la complessità degli algoritmi cambierà.
Nel frattempo, parallelizzando un algoritmo, con un numero fisso di processori, il giustificativo divide il suo tempo di esecuzione proporzionale (e, nel migliore dei casi, quando non ci sono dipendenze tra le attività eseguite su ogni processore). Ciò significa, dividendo il tempo di esecuzione di una costante, e così la complessità rimane la stessa.
L'esecuzione parallela non modifica le basi della complessità per un particolare algoritmo: nella migliore delle ipotesi, si sta solo prendendo il tempo per una determinata dimensione e dividendo per il numero di core. Ciò può ridurre il tempo per una determinata dimensione di un fattore costante, ma non ha alcun effetto sulla complessità dell'algoritmo.
Allo stesso tempo, l'esecuzione parallela a volte cambia quale algoritmo che si desidera utilizzare per determinate attività. Alcuni algoritmi che funzionano bene con il codice seriale non si suddividono in compiti paralleli molto bene. Altri che hanno una complessitàsuperiore potrebbero essere più veloci per problemi di dimensioni pratiche perché funzionano meglio in parallelo.
Per un numero estremamente elevato di core, la complessità del calcolo stesso può diventare secondaria semplicemente ottenendo i dati necessari da/per tutti i core per eseguire il calcolo. la maggior parte dei calcoli di big-O non tiene conto di questi effetti per un calcolo seriale, ma può diventare abbastanza importante per i calcoli paralleli, specialmente per alcuni modelli di macchine parallele che non danno accesso uniforme a tutti i nodi.
Per Amdahl's law, per la stessa dimensione del problema, parallelizzazione arriva ad un punto di diminuire ritorno con l'aumento del numero di nuclei (teoricamente). In realtà, da un certo grado di parallelizzazione, il sovraccarico della parallelizzazione ridurrà effettivamente le prestazioni del programma.
Tuttavia, con Gustafson's law, l'aumento del numero di core in realtà aiuta quando la dimensione del problema aumenta. Questa è la motivazione dietro il cluster computing. Dato che abbiamo più potenza di calcolo, possiamo affrontare il problema su una scala più ampia o con una precisione migliore con l'aiuto della parallelizzazione.
Gli algoritmi che apprendiamo come è possono o non possono essere paralellabili. A volte, è necessario utilizzare un algoritmo separato per eseguire in modo efficiente la stessa attività in parallelo. In entrambi i casi, la notazione Big-O deve essere riesaminata per il caso parallelo per prendere in considerazione l'effetto della parallelizzazione sulla complessità temporale dell'algoritmo.
Questo algoritmo è solo un'innovazione teorica; per quanto ne so, anche l'algoritmo di Coppersmith-Winograd non viene utilizzato nella pratica. – sdcvvc
C'è un algoritmo n log^2 (n) per l'architettura basata su mesh, con n processore, per la moltiplicazione della matrice (teoricamente), inoltre ci sono troppi algoritmi che sono indipendenti dal loro normale 'O', quando si vuole pensare al parallelo algoritmi, dovresti pensare ad altri modi, i modi normali normalmente sono inutili. –