42) In cosa consiste il modello PRAM?

Una macchina parallela ad accesso random (Parallel Random Access Machine) è costituita da una collezione di RAM.

Una PRAM di dimensione P è composta da:

• P programmi inalterabili fatto di istruzioni in sequenza.
• una sola memoria composta di una sequenza di parole capaci di contenere un intero.
• P accumulatori capace di operare.
• un nastro di input ed uno di output.

Durante un passo, la PRAM esegue P istruzioni, una per ogni programma (modello MIMD o meglio MIMD sincrono)

Distinzione semantica su come si eseguono le operazioni su una stessa cella di memoria (operazioni di lettura/scrittura):

sono previste:

• operazioni simultanee (Concorrenti)
• operazioni sequenzializzate (Esclusive)

e quindi si definiscono i seguenti tipi di PRAM:

• Concurrent Read Exclusive Write (CREW PRAM)
• Exclusive Read Exclusive Write (EREW PRAM)
• Concurrent Read Concurrent Write (CRCW PRAM)
• Exclusive Read Concurrent Write (ERCW PRAM)

Le operazioni concorrenti sono considerate secondo il principio di serializzazione: gli effetti come se una fosse fatta per prima, poi un'altra in successione, un'altra ancora, etc.

limiti:

• le istruzioni richiedono lo stesso tempo.
• il tempo di operazione non dipende da P, in quanto l’accesso a memoria comune avviene in un tempo che non cresce con P.
• il tempo di operazione di input/output trascurato, in quanto l’accesso ad un unico nastro non cresce con P.

I/O bottleneck (rimedio: uso di concorrenza per la gestione del sottosistema di I/O)

Problema: Il modello PRAM è troppo potente ed astratto. Gli algoritmi sono più veloci sul modello che nei sistemi reali modellati