Algoritmo parallelo - Introduzione

Un algorithmè una sequenza di passaggi che riceve input dall'utente e, dopo alcuni calcoli, produce un output. UNparallel algorithm è un algoritmo che può eseguire più istruzioni contemporaneamente su diversi dispositivi di elaborazione e quindi combinare tutte le singole uscite per produrre il risultato finale.

Elaborazione simultanea

La facile disponibilità di computer insieme alla crescita di Internet ha cambiato il modo in cui archiviamo ed elaboriamo i dati. Viviamo in un'epoca in cui i dati sono disponibili in abbondanza. Ogni giorno trattiamo enormi volumi di dati che richiedono elaborazioni complesse e anche questo, in tempi rapidi. A volte, abbiamo bisogno di recuperare dati da eventi simili o correlati che si verificano simultaneamente. Questo è dove abbiamo bisognoconcurrent processing che può dividere un compito complesso ed elaborarlo su più sistemi per produrre l'output in tempi rapidi.

L'elaborazione simultanea è essenziale quando l'attività comporta l'elaborazione di una massa enorme di dati complessi. Gli esempi includono: accesso a grandi database, test di aeromobili, calcoli astronomici, fisica atomica e nucleare, analisi biomedica, pianificazione economica, elaborazione delle immagini, robotica, previsioni meteorologiche, servizi basati sul web, ecc.

Cos'è il parallelismo?

Parallelismè il processo di elaborazione simultanea di più set di istruzioni. Riduce il tempo di calcolo totale. Il parallelismo può essere implementato utilizzandoparallel computers,cioè un computer con molti processori. I computer paralleli richiedono algoritmi paralleli, linguaggi di programmazione, compilatori e sistemi operativi che supportano il multitasking.

In questo tutorial, parleremo solo di parallel algorithms. Prima di andare oltre, discutiamo prima degli algoritmi e dei loro tipi.

Cos'è un algoritmo?

Un algorithmè una sequenza di istruzioni seguite per risolvere un problema. Durante la progettazione di un algoritmo, dovremmo considerare l'architettura del computer su cui verrà eseguito l'algoritmo. Secondo l'architettura, ci sono due tipi di computer:

  • Computer sequenziale
  • Computer parallelo

A seconda dell'architettura dei computer, abbiamo due tipi di algoritmi:

  • Sequential Algorithm - Un algoritmo in cui vengono eseguiti alcuni passaggi consecutivi di istruzioni in ordine cronologico per risolvere un problema.

  • Parallel Algorithm- Il problema è suddiviso in sottoproblemi e vengono eseguiti in parallelo per ottenere singoli output. Successivamente, questi singoli output vengono combinati insieme per ottenere l'output finale desiderato.

Non è facile suddividere un grosso problema in sub-problems. I problemi secondari possono avere dipendenza dai dati tra di loro. Pertanto, i processori devono comunicare tra loro per risolvere il problema.

È stato riscontrato che il tempo necessario ai processori per comunicare tra loro è maggiore del tempo di elaborazione effettivo. Quindi, durante la progettazione di un algoritmo parallelo, è necessario considerare un corretto utilizzo della CPU per ottenere un algoritmo efficiente.

Per progettare correttamente un algoritmo, dobbiamo avere un'idea chiara delle basi model of computation in un computer parallelo.

Modello di calcolo

Sia i computer sequenziali che quelli paralleli operano su un insieme (flusso) di istruzioni chiamate algoritmi. Questo insieme di istruzioni (algoritmo) istruisce il computer su ciò che deve fare in ogni passaggio.

A seconda del flusso di istruzioni e del flusso di dati, i computer possono essere classificati in quattro categorie:

  • Computer con flusso di istruzioni singolo, flusso di dati singolo (SISD)
  • Computer con flusso di istruzioni singolo, flusso di dati multipli (SIMD)
  • Computer con più istruzioni, flusso di dati singolo (MISD)
  • Flusso di istruzioni multiple, computer MIMD (Multiple Data Stream)

Computer SISD

I computer SISD contengono one control unit, one processing unit, e one memory unit.

In questo tipo di computer, il processore riceve un singolo flusso di istruzioni dall'unità di controllo e opera su un singolo flusso di dati dall'unità di memoria. Durante il calcolo, ad ogni passo, il processore riceve un'istruzione dall'unità di controllo e opera su un singolo dato ricevuto dall'unità di memoria.

Computer SIMD

I computer SIMD contengono one control unit, multiple processing units, e shared memory or interconnection network.

Qui, una singola unità di controllo invia istruzioni a tutte le unità di elaborazione. Durante il calcolo, ad ogni passo, tutti i processori ricevono un unico set di istruzioni dall'unità di controllo e operano su diversi set di dati dall'unità di memoria.

Ciascuna delle unità di elaborazione ha la propria unità di memoria locale per memorizzare sia i dati che le istruzioni. Nei computer SIMD, i processori devono comunicare tra loro. Questo viene fatto dashared memory o da interconnection network.

Mentre alcuni processori eseguono una serie di istruzioni, i restanti processori attendono la loro successiva serie di istruzioni. Le istruzioni dell'unità di controllo decidono quale processore saràactive (eseguire istruzioni) o inactive (attendere la prossima istruzione).

Computer MISD

Come suggerisce il nome, i computer MISD contengono multiple control units, multiple processing units, e one common memory unit.

Ogni processore ha la propria unità di controllo e condivide un'unità di memoria comune. Tutti i processori ricevono istruzioni singolarmente dalla propria unità di controllo e operano su un unico flusso di dati secondo le istruzioni che hanno ricevuto dalle rispettive unità di controllo. Questo processore funziona contemporaneamente.

Computer MIMD

I computer MIMD hanno multiple control units, multiple processing units, e a shared memory o interconnection network.

Ogni processore ha la propria unità di controllo, unità di memoria locale e unità aritmetica e logica. Ricevono diversi set di istruzioni dalle rispettive unità di controllo e operano su diversi set di dati.

Nota

  • Un computer MIMD che condivide una memoria comune è noto come multiprocessors, mentre quelli che utilizzano una rete di interconnessione sono noti come multicomputers.

  • In base alla distanza fisica dei processori, i multicomputer sono di due tipi:

    • Multicomputer - Quando tutti i processori sono molto vicini tra loro (es. Nella stessa stanza).

    • Distributed system - Quando tutti i processori sono lontani l'uno dall'altro (es- nelle diverse città)