Ho letto da qualche parte (ho dimenticato quale libro è) che gli algoritmi sono indipendenti dalle architetture dei computer. Alcuni addirittura dicono che gli algoritmi sono essi stessi computazioni (macchine?)?
D'altra parte, i libri sulla programmazione parallela hanno capitoli su algoritmi paralleli. Sembra che gli algoritmi paralleli dipendano da architetture parallele?
Penso di essermi perso alcune grandi foto? Grazie.
Gli algoritmi sono la serie di misure adottate per risolvere un particolare problema. La ricetta per risolvere il problema, se vuoi. I "programmi" fanno le stesse cose, ovviamente; usiamo "algoritmo" per suggerire le ricette "generalizzate" o "generalmente applicabili" che sono indipendenti da specifici progetti di macchine, linguaggi di programmazione e simili.
Gli algoritmi sono generici, ma possono comunque dipendere dal fatto che alcune funzioni siano presenti. "Algoritmi concorrenti", ad esempio, potrebbe dipendere dal fatto che si dispone di un meccanismo per l'esecuzione contemporanea di programmi diversi. Gli "algoritmi distribuiti" possono dipendere dal fatto che tu abbia più di un sistema in un gruppo cooperante e una rete o un altro schema di comunicazione tra di loro. Allo stesso modo, "algoritmi paralleli" sono spesso quelli progettati per essere eseguiti quando si hanno più unità di elaborazione - potenzialmente molte, molte unità di elaborazione e il tipo di strutture di comunicazione che sono comuni quando si hanno grandi matrici di unità di elaborazione. Potresti essere in grado di eseguire un "algoritmo parallelo" anche quando hai un solo computer o una CPU - ma non è molto interessante il modo in cui avere i tecnici del traffico non è molto utile a meno che tu non abbia anche strade.
Gli algoritmi sono indipendenti dall'architettura del computer. Questo perché gli algoritmi definiscono una serie di processi che risolvono un problema. Indipendentemente dalle architetture, gli algoritmi di ordinamento verranno sempre ordinati. Non renderà improvvisamente i disegni 3D su alcune architetture.
Se ci pensi, questo è in realtà intuitivo. Google Chrome (che è semplicemente una raccolta di algoritmi) è un browser Web quando compilato per qualsiasi architettura. Non diventerebbe improvvisamente un driver di periferica su alcune architetture.
Ma la velocità di esecuzione degli algoritmi dipende dalle architetture. E alcuni algoritmi funzionano più velocemente di altri a seconda delle architetture.
Se ci pensi, anche questo è davvero intuitivo. Dato un algoritmo, è sempre possibile per il progettista hardware progettare un'architettura che acceleri specificamente tale algoritmo. Questo è uno dei motivi per cui ci sono cose come le schede grafiche accelerate 3D e gli acceleratori bitcoin miner.
Quando le persone parlano di algoritmi paralleli, stanno parlando di una famiglia di algoritmi che possono lavorare più velocemente su architetture parallele. Ci sono molti algoritmi che non sono migliorati dalle architetture parallele. Quindi identificare nuovi algoritmi per lo stesso problema che funzionano bene in parallelo è un'area di ricerca attiva.
Ma quegli algoritmi continuano a fare le stesse cose. Le architetture non cambiano ciò che fanno.
"It seems like parallel algorithms depend on parallel architectures?"
Secondo me la risposta è semplicemente: no. Generale, ho solo le proprietà
quando si pensa all'architettura hardware.
Facendo riferimento al parallelismo, è possibile calcolare in batch qualsiasi algoritmo parallelo e qualsiasi arco parallelo funzionare in modo seriale, in modo che l'algoritmo non dipenda da questo. La dimensione della parola potrebbe essere un problema per la stabilità numerica ma non per l'algoritmo stesso. I limiti di risorse come 64bit possono solo descrivere 2 ^ 64 numeri diversi potrebbero essere un problema, ma comunque gli elementi sono limitati.
Naturalmente potrebbero esserci alcuni algoritmi che dipendono da alcuni set di istruzioni estesi, ma almeno tutto può essere descritto con la matematica di base.
Ad esempio con il calcolo quantico alcuni valori di Big-O potrebbero cambiare e quindi direi che
"algorithms are independent of computer architectures"
non è più vero.
Gli algoritmi non dipendono dall'architettura del computer, tuttavia l'efficienza nell'esecuzione di un particolare algoritmo dipende dall'architettura. Qualsiasi macchina di Turing Complete può emulare qualsiasi altra macchina di Turing Complete, anche se alcune macchine sarebbero migliori in una cosa rispetto ad altre.
Ciò che intendiamo per algoritmi concorrenti è che l'algoritmo funziona bene o può sfruttare la concorrenza nella macchina, forse perché richiede meno blocchi che altrimenti sarebbero stati richiesti da algoritmi che non sono specificamente progettati per la macchina concorrente o forse perché l'algoritmo fa uso di divide e conquista in modo efficace per utilizzare tutta la potenza della macchina. L'esecuzione dell'algoritmo in una macchina non concorrente sarebbe ancora possibile ma potrebbe non essere altrettanto efficiente o richiedere il blocco aggiuntivo per eseguire correttamente.
Ci sono anche algoritmi che sono progettati per trarre vantaggio dalla stranezza di una particolare architettura, come algoritmi di cache-friendly, che ottimizzano la memorizzazione nella cache. Questi algoritmi possono essere meno efficienti in macchine che non memorizzano nella cache il modo in cui l'algoritmo assume.
In teoria, gli algoritmi sono completamente indipendenti dall'architettura. È sempre possibile emulare un'architettura parallela su un sistema con tempi di rilascio singoli. È possibile motivo sugli algoritmi senza un'architettura. Il libro di Knuth usa un'architettura fittizia.
In pratica ci sono algoritmi che tentano di ottenere un runtime migliore per la stessa complessità di "O" ottimizzando l'uso dell'hardware di cache e delle primitive di sincronizzazione.
Sì e no. Dipende dai vincoli che desideri soddisfare e dalle precondizioni necessarie per eseguire l'algoritmo.
Idealmente, un algoritmo è una ricetta astratta che definisce passo-passo come fare qualcosa. Gli algoritmi sono stati definiti in questo modo con l'obiettivo di riproducibilità e in seguito di automatizzazione. Gli algoritmi provengono da lambda-calcul, quindi puoi facilmente capire perché sono fatti in questo modo. Questa definizione è la solita, ma gli algoritmi moderni possono essere non sequenziali (non graduali, come algoritmi concorrenti, o logici come quelli che usano l'unificazione), non lineari (algoritmi stocastici) o semplicemente chiaramente (quantum algoritmi), ma lo passerò.
Quindi, idealmente, un algoritmo dovrebbe essere il più astratto possibile senza contare l'hardware.
Tuttavia, come con qualsiasi sistema, devi definire alcuni assiomi , non solo per ottenere un sistema coerente, ma anche per guadagnare tempo. Ad esempio, la maggior parte degli algoritmi presume, perlomeno implicitamente, che siano definiti su una macchina Von-Neumann. Se così non fosse, avrebbero bisogno di definire in modo esplicito ogni parte del sistema di cui hanno bisogno per essere eseguiti (poiché questo è necessario per riprodurre la ricetta, questa è una sorta di precondizione). Inoltre, spesso gli algoritmi si basano su comandi comuni come write () senza definirli completamente.
Un altro motivo per cui gli algoritmi non sono così astratti dall'architettura hardware, è quando devi soddisfare alcuni vincoli .
Diciamo che stai lavorando su sistemi embedded, quindi probabilmente non puoi contare sulla stessa quantità di risorse che hai sulle workstation. Una delle risorse più contenute è probabilmente la memoria. Tuttavia, la maggior parte degli algoritmi tende a ottimizzare la complessità del tempo (velocità di esecuzione sulla CPU), non la complessità della memoria (quantità di memoria necessaria per lavorare sui dati). Per questi sistemi, sono stati ideati algoritmi di memoria ottimizzati in cui gli algoritmi non ottimizzati per la memoria fallirebbero o sarebbero molto più lenti. In effetti, i sistemi embedded non sono l'unico obiettivo di algoritmi efficienti per la memoria: ad esempio, ci sono algoritmi cache-oblivious che adatta la loro elaborazione per utilizzare in modo efficiente la cache della CPU. Un altro esempio: alcuni algoritmi di apprendimento automatico per i big data sono adattati per apprendimento incrementale o calcolo fuori dai core per elaborare enormi quantità di dati molto più grandi della memoria disponibile su qualsiasi computer, ecc.
Esistono anche algoritmi che non ottimizzano una parte specifica del computer, ma uno standard che dipende dall'architettura hardware. Ad esempio, i dati numerici che richiedono precisione sono memorizzati all'interno di float o double, che sono per natura limitati a causa dei limiti hardware. Il problema è che calcoli complessi possono portare all'arrotondamento e più calcoli esegui su numeri arrotondati, più ti lascerai alla larga. Questa è chiamata interferenza catastrofica . Alcune applicazioni richiedono una precisione critica, anche a scapito della peggiore complessità. Per questo tipo di applicazioni, sono stati apportati algoritmi che ottimizzano il calcolo per ridurre o rimuovere le interferenze catastrofiche.
Quindi, progettare un algoritmo può anche essere un compromesso tra astrazione e vincoli.
Alla fine, possiamo dire che un algoritmo è astratto quanto il suo obiettivo, e come il suo precondizionato (architettura) ha bisogno di . Il target più specifico che il tuo algoritmo mira, più probabilmente si baserà sull'architettura hardware.
Alcune parole chiave correlate che potrebbero interessarti:
Non dovresti confondere un algoritmo in generale con algoritmi matematici o di calcolo. Se intendi algoritmi di calcolo, sì, sono indipendenti dall'architettura della macchina.
Definizione dell'algoritmo da Wikipedia:
In mathematics and computer science, an algorithm is a self-contained step-by-step set of operations to be performed. Algorithms exist that perform calculation, data processing, and automated reasoning.
Questa definizione viene utilizzata per riferire alcune operazioni di calcolo o di elaborazione dei dati chiuse. In altre parole, calcoli che possono essere eseguiti in modo astratto su Turing Machine . Tuttavia, recentemente c'è un concetto in matematica chiamato Calcolo interattivo che implica la comunicazione di input / output con il mondo esterno durante calcolo.
In una definizione generale, l'algoritmo è solo una ricetta (sequenza di istruzioni). Penso che non si possa pensare ad un algoritmo senza conoscere il set di istruzioni o le operazioni che è possibile utilizzare; Le operazioni matematiche riguardano il calcolo, quindi un algoritmo che include un passo chiamato " riscalda il forno " non è un algoritmo matematico, ma puoi darlo a uno chef, perché sa come eseguirlo.
Quindi, puoi creare una macchina che può fare X, Y, Z .... ognuno di questi potrebbe essere usato come algoritmo nell'algoritmo. Ma se si tratta di computazioni chiuse (in realtà calcoli digitali deterministici non interattivi non interattivi), allora si può dimostrare che la macchina è equivalente a Turing Machine . Ma se scegli come target altri tipi di calcoli (valori continui o calcolo interattivo [tuttavia non sono sicuro che siano davvero un altro tipo del calcolo]) o persino di compiti informatici, è possibile pensare a macchine che possono eseguirle.
Questa domanda e risposta sono anche interessanti per avere una prospettiva più ampia sugli algoritmi.
In generale, gli algoritmi sono progettati per alcuni problemi particolari, riducendo al minimo alcune misure di "costo". Storicamente, molti algoritmi sono stati progettati partendo dal presupposto che i costi relativi delle operazioni comuni sarebbero stati relativamente simili su molte architetture, e quindi alcune macchine tipiche avrebbero eseguito un algoritmo che avrebbe funzionato meglio di un altro, quindi sulla maggior parte delle macchine tipiche il vecchio algoritmo avrebbe, a peggio, sii solo leggermente inferiore a quest'ultimo. Col passare del tempo, una tale ipotesi non regge bene come prima.
Ad esempio, un tempo il numero di volte che un programma aveva bisogno di leggere le cose dalla memoria era considerato più importante delle posizioni delle cose da leggere. Leggere le cose che si trovavano vicine l'una all'altra in memoria era in qualche modo più economico che leggere cose che erano lontane, ma non scandalosamente mostrare. Poiché le velocità della CPU principale sono aumentate ad una velocità molto superiore alla velocità di memoria, tuttavia, l'importanza della sequenza di accesso è aumentata in modo significativo. È possibile che un programma esegua dieci volte più istruzioni di un altro e tuttavia funzioni più velocemente, se il 95% della memoria del programma precedente recupera generatori di cache L1 e la maggior parte dei recuperi di memoria del programma secondario generano errori di cache.
Inoltre, alcuni tipi di algoritmi relativi alla concorrenza fanno supposizioni su quando i dati scritti in memoria da un core del processore saranno "visti" da altri core. Molti processori hanno vari modi in cui possono leggere e scrivere memoria, con costi e garanzie variabili sulla visibilità. Alcuni algoritmi funzioneranno molto bene su architetture in grado di soddisfare i requisiti di visibilità "gratuitamente", ma scarsamente su altri in cui le istruzioni necessarie per tali garanzie sono costose. In effetti, su alcune architetture è possibile garantire che determinati algoritmi relativi alla concorrenza funzionino limitando l'esecuzione a un singolo core CPU condiviso nel tempo (che ovviamente annullerebbe il punto di utilizzo di un algoritmo concorrente).
Molte risposte mancano del fatto che un algoritmo può essere definito in termini astratti o in relazione letterale diretta con un'architettura. Un algoritmo deve essere non ambiguo, ma c'è ancora spazio per essere più o meno specifico.
Un algoritmo per convertire una stringa in maiuscoletto può essere facilmente descritto in pseudocodice indipendente dall'architettura. Ma allo stesso tempo, niente ti impedisce di descrivere un algoritmo per convertire una stringa in maiuscolo, in particolare su un'architettura x86. Tutto ciò che serve è un compito a casa dell'Assemblea x86. (Puoi ancora farlo in pseudocodice - solo uno pseudocodice relativo a quell'architettura!) Solo il fatto che il problema sia specifico per fare ciò su un'architettura x86 non significa che non hai più un algoritmo per risolverlo.
Dipende dal problema che l'algoritmo è definito per risolvere. L'algoritmo è indipendente dall'architettura se il problema che risolve è indipendente dall'architettura (e presupponendo che ciò non sia annullato dal modo in cui l'algoritmo è descritto o messo insieme). Il problema può essere teorico, a lavagna, o può essere in termini di un'architettura molto specifica. In quest'ultimo caso, l'algoritmo, a sua volta, sarebbe limitato a lavorare con tale architettura.
Algoritmi sono una sequenza di passaggi. Non dipendono da ciò che è (o non è) in esecuzione.
Tuttavia, la complessità temporale di un algoritmo può dipendere da cosa lo sta eseguendo. Ecco perché l'analisi dettagliata di un algoritmo richiede un "modello di calcolo", come una macchina ad accesso casuale . < br> Indipendentemente dal fatto che la memoria sia o meno accessibile in modo casuale, sicuramente influisce sulla durata dell'esecuzione dell'algoritmo e la maggior parte degli algoritmi presuppone che sia il caso, mentre in realtà la maggior parte delle architetture non soddisfa questa condizione.
Leggi altre domande sui tag architecture algorithms parallel-programming