Fig.1 Grafo dataflow del fattoriale
Il paradigma della programmazione sequenziale trova la sua origine nella Macchina di von Neumann dove l'esecuzione dei programmi è basata su due registri fondamentali
i quali, ad ogni ciclo fetch-execute, permettono di ottenere l'istruzione corrente per la successiva decodifica del codice operativo e attivarne la corrispondente rete logica di esecuzione.
E' altrettanto noto che l'eseguibilità di un programma richiede la presenza contemporanea in memoria centrale sia del programma che dei dati su cui deve operare, ai quali si accede per indirizzo (by reference, mentre il contatore di programma stabilisce il controllo sequenziale del flusso esecutivo e che si rispecchia fedelmente nel modo con cui i programmi sono pensati e realizzati.
L'ordinamento totale delle istruzioni in formato assembler si presenta in forma pressochè immutata nella programmazione strutturata del Pascal, o di qualunque altro linguaggio evoluto della stessa famiglia, imponendo una sequenzialità stretta sulle istruzioni.
Tuttavia, nella stesura dei programmi si verificano spesso situazioni in cui la scelta dell'ordine con cui manipolare un insieme di variabili è del tutto arbitraria. In generale, la corretta esecuzione di un programma richiede l'ordinamento solamente per un certo sottoinsieme di istruzioni; le rimanenti, per le quali non è prevista alcuna forma di restrizione temporale, possono essere eseguite in qualunque ordine e, quindi, contemporaneamente o, concorrentemente.
I grafi di dipendenza di dati permettono di rappresentare in forma esplicita l'ordinamento parziale delle istruzioni, evidenziando la rete di comunicazione che le interconnette. In questo modo scompare la memoria condivisa perchè i
L'esecuzione di programmi in forma di grafo, opportunamente rappresentati in memoria, avviene mediante un particolare meccanismo di ricostruzione delle istruzioni nel registro istruzioni dell'Unità di Elaborazione basato sulla disponibiltà dei dati di ciascuna istruzione.
Il ciclo esecutivo di questo nuovo tipo di macchine generalizza quello di von Neumann nel senso che la semplice fase di fetch viene sostituita con la coppia
Si consideri, a scopo esemplicativo, il seguente frammento di programma Pascal per il calcolo della funzione fattoriale in forma iterativa.
k := 1;
i := n;
while i > 0 do
begin
k := k * i;
i := i - 1
end;
Fact := k
|
k := 1; i := n; 1: if i = 0 then goto 2; k := k * i; i := i - 1 goto 1; 2: Fact := k |
Per facilità di comprensione, sono stati riportati sia il programma in cui compare l'istruzione while, sia quello espresso solamente in termini di salto condizionato. In essi è stata omessa l'intestazione comune
function Fact(n : integer) : integer; var k, i : integer;La sua traduzione in grafo di dipendenza dei dati è quella che appare nella figura seguente
Fig.1 Grafo dataflow del fattoriale
Un'analisi dettagliata di questo grafo rivela la presenza di due cicli, attivati contemporaneamente dalle istruzioni MRG, che si sincronizzano attraverso le istruzioni di salto BRR.
Per avere maggiori dettagli sulle istruzioni che compaiono in questo grafo si consulti la dispensa di Programamzione Concorrente. Ulteriori approfondimenti sui sistemi dataflow sono contenuti nel primo capitolo della dispensa relativa al Corso di Sistemi Operativi.
Si è già visto che il ciclo esecutivo delle macchine dataflow generalizza quello di von Neumann nel senso che si passa da due a tre fasi:
Il registro contatore di programma è sostituito da un pipeline di unità di elaborazione dedicate, secondo quanto appare nella figura seguente
Fig.1 Architettura di una macchina dataflow
la quale evidenzia come il traffico di token è realmente gestito.
Ciascun token (token package), che transita attraverso lo switch rappresenta un dato del programma, è costituito da 4 componenti:
per cui si parla anche di token segnati o colorati. Tale pacchetto confluisce nel modulo di accodamento, posizionato in prossimità dello switch, all'ingresso dell'anello.
Nell'architettura precedentemente schematizzata si suppone che sia due il numero massimo di operandi per istruzione. Il suo funzionamento, allora, può così riassumersi.
Il seguente sottoinsieme di istruzioni per un'ipotetica macchina dataflow, permette di realizzare grafi di programma per semplici algoritmi.
| Istruzione | Op1 | Op2 | Commento |
|---|---|---|---|
| ADD | Int | Int | |
| INC | Int | incremento unitario | |
| SUB | Int | Int | sottrae due valori interi |
| DEC | Int | decremento unitario | |
| MLT | Int | Int | moltiplica due valori interi |
| TST | Int | verifica se il valore intero è nullo | |
| CMP | Int | Int | confronta due valori interi |
| GTR | Int | Int | verifica se il primo valore è maggiore del secondo |
| GEQ | Int | Int | verifica se il primo valore non è minore del secondo |
| LSS | Int | Int | verifica se il primo valore è minore del secondo |
| LEQ | Int | Int | verifica se il primo valore non è maggiore del secondo |
| Istruzione | Op1 | Op2 | Commento |
|---|---|---|---|
| DUP | Any | Duplicate | |
| BRR | Any | Bool | Branch |
| MRG | Any | Any | Merge |
Si osservi che l'istruzione BRR riceve in ingresso, sull'arco sinistro un dato, che può essere di qualunque tipo, ed un segnale di controllo sull'arco destro, che determina se il dato uscirà sul lato destro o sinistro.
Per quanto riguarda, invece, l'istruzione MRG verrà considerato solamente il caso in cui un solo dato è presente in ingresso e che, pertanto, sarà automaticamente selezionato in uscita.
Le istruzioni di commutazione BRR e MRG sono molto potenti quando sono utilizzate per implementare cicli e funzioni e permettono di ricondurre computazioni potenzialmente complesse a programmi relativamente coincisi analogamente a quanto avviene per gli stessi costrutti della programmazione sequenziale.
Dall'esempio del fattoriale e dagli altri presentati nel seguito, si vede che l'uso dell'istruzione MRG funge da attivatore del ciclo nel quale è inserita. Ma l'attivazione si realizza anche rendendo contemporaneamente disponibile un dato di ingresso ad istruzioni appartenenti a differenti flussi computazionali paralleli.
In entrambi i casi la computazione è attivata dalla disponibilità iniziale di un certo numero di token, eventualmente duplicati se necessario. Se nell'istruzione di duplicazione DUP si evidenzia la parte relativa al controllo, implicitamente definito dalla disponibilità del token stesso, si vede che ciascun data token incorpora sia
quest'ultimo definito come un data token la cui componente relativa al dato è nulla e, per questo, detto token di controllo. Si parla, allora, di controllo parallelo esplicito della computazione e ricompare, nuovamente, la memoria condivisa in cui devono essere memorizzati i dati temporaneamente in uso.
In questo scenario l'istruzione DUP prende il nome di fork e il suo effetto è quello di duplicare il flusso sequenziale di controllo che la sta eseguendo. Entrambi i flussi condividono lo stesso dato a meno che non si assegnino rispettivamente due copie dello stesso. Si constata immediatamente che l'istruzione fork ha la capacità di estendere la computazione sequenziale di una macchina di Von Neumann alla computazione parallela di due macchine virtuali di Von Neumann.
Naturalmente, l'istruzione fork non è di per se sufficiente ad estendere la computazione sequenziale in modo da generare un modello equivalente debole delle macchine dataflow. Si deve poter disporre, a tal fine, di istruzioni che siano in grado di far cooperare attivamente i flussi sequenziali generati da tali istruzioni. A questo proposito si può utilizzare un'istruzione join il cui effetto è quello di ricongiungere i flussi le cui computazioni parziali contribuiscono a determinare il valore di opportune variabili globali.
I modelli dataflow multisequenziali si basano sulla realizzazione di un certo numero di macchine virtuali monosequenziali a partire dall'unica macchina di Von Neumann disponibile. Ciascuna di queste macchine esegue un unico flusso sequenziale che, per l'importanza che riveste, prende il nome di processo.
Si dice che due istruzioni sono eseguite
Possiamo, allora, riferire le stesse proprietà ai programmi, con le seguenti definizioni.
Per quanto riguarda, invece, l'esecuzione di un programma concorrente, questa si può classificare come
Se si impongono opportune restrizioni sintattiche alla struttura di un programma concorrente è possibile identificare facilmente le sezioni di programma che possono essere eseguite concorrentemente.
Ciascun costrutto può essere usato per caratterizzare computazioni aventi un numero fissato, o statico, di processi oppure in combinazione con meccanismi di creazione di processi per dar luogo a computazioni aventi un numero variabile, o dinamico, di processi.
Si dicono coroutine due o più procedure nelle quali il trasferimento del controllo avviene in modo simmetrico anzichè strettamente gerarchico, eseguendo l'istruzione resume la quale è realizzata in modo da salvare informazione sufficiente sullo stato della coroutine da permettere, al momento del ritorno del controllo, di eseguire l'istruzione immediatamente seguente l'istruzione resume. Ciascuna coroutine può vedersi come l'implementazione di un processo dove l'esecuzione di resume produce come effetto una sincronizzazione fra processi.
Usate con attenzione le coroutine rappresentano un modo accettabile di organizzare i programmi concorrenti che condividono un singolo processore. La multiprogrammazione può essere implementata usando coroutine sebbene queste non siano adeguate a definire una reale elaborazione parallela. In essenza, le coroutine sono processi concorrenti caratterizzati da un controllo esplicito dello scambio di contesto fra processi, piuttosto che essere lasciato a discrezione dell'implementazione.