Articolo pubblicato sul n. 109 di MCmicrocomputer (Edizioni Technimedia Srl - Roma) nel luglio 1991

Multitasking:
OCCAM: parallelismo puro

di Andrea de Prisco

Puo' anche darsi che non abbiate mai sentito la parola OCCAM. Non potete pero' dire altrettanto della parola "transputer". OCCAM, per tagliare corto, e' il linguaggio di programmazione dei transputer. E se quest'ultimo e' il processore piu' "multitasking" che c'e', OCCAM e' il linguaggio di programmazione piu' "parallelo" che c'e'. Tanto parallelo che un programma scritto in OCCAM puo' essere formato da istruzioni da eseguire non "una dopo l'altra" ma addirittura contemporaneamente. Si', un intero programma eseguito, dal punto di vista logico, in un solo passo: anche se le istruzioni sono centinaia o migliaia. O, addirittura, formato da pochissime istruzioni che pero' sottindendono un parallelismo a tempo di esecuzione pronto ad esplodere al fatidico "run".

Parallelismo "esplosivo"

Non e' proprio l'argomento di questa puntata, ma tanto per farvi venire ancora di piu' la voglia di continuare a leggere (o, soprattutto, per non farvela passare...) anticipiamo questo mese qualche informazione in piu' riguardo l'ultima frase dell'introduzione di quest'articolo.
Chiunque programma i computer sa che i loop quali FOR-NEXT, WHILE-DO, REPEAT-UNITL servono essenzialmente per non riscrivere tante volte la stessa porzione di codice. Se dobbiamo eseguire 5 volte una sezione di un programma, nessuno si sognerebbe mai di riscriverla 5 volte di seguito (a meno di non avere problemi di velocita') ma semplicemente la incorpora in un loop impostando questo all'esecuzione sequenziale per il numero di volte voluto.
OCCAM, da bravo linguaggio di programmazione parallela, permette di fare la stessa cosa nel "parallelo". Esistono costrutti OCCAM che permettono di lanciare in parallelo tanti processi quanti ne abbiamo impostato nel costrutto stesso: ognuno lavorera' su un certo insieme proprio di dati e il comando di ripetizione parallela terminera' quando saranno terminate tutte le istruzioni lanciato comando stesso e che, ripetiamo, saranno eseguite parallelamente.
Chiariamo con un esempio. Immaginate la sezione di programma Pascal-Like:

for i:=1 to 20
a[i] := 0;

che non fa altro che annullare il vettore 'a'. Qualsiasi linguaggio di programmazione sequenziale azzerera' i vari elementi l'uno dopo l'altro, partendo dal numero 1 fino al numero 20. In OCCAM, volendo, possiamo parallelizzare l'esecuzione scrivendo cosi':

PAR i=1 FOR 20
a[i] := 0

che annullera' simultaneamente i venti elementi del vettore 'a'. Se non ci credete, in parte non avete tutti i torti.
OCCAM non e' stato ancora impementato nella sua pienezza e un'istruzione come quella appena vista, in esecuzione su un singolo transputer sara' eseguita si' in parallelo, ma in parallelismo simulato. In pratica il transputer e' in grado di eseguire piu' processi contemporaneamente ma, ovviamente, grazie al proprio multitasking di macchina. Quindi su un singolo transputer i venti assegnamenti saranno eseguiti l'uno dopo l'altro (anche se non necessariamente in ordine), mentre su una rete di chip di questo tipo sara' possibile l'esecuzione in parallelismo reale.
Come pero' vedremo meglio nei prossimi appuntamenti, il meccanismo della ripetizione parallela e' tutt'altro che un'inutile esercitazione tecnologica in quanto ci permettera', anche sul singolo chip, di implementare in maniera parallela algoritmi intrinsecamente paralleli senza la necessita' di forzare un'implementazione sequenziale degli stessi...
Ne riparleremo piu' approfonditamente a partire dal prossimo mese.

Un programma OCCAM

La struttura di un programma OCCAM e' la seguente:

dichiarazione:
processo

La dichiarazione e' a sua volta... una dichiarazione oppure una dichiarazione seguita da un'altra dichiarazione. Con le dichiarazioni, come in altri linguaggi convenzionali, indichiamo nomi e tipi delle variabili, costanti, array o canali (vedi dopo) che utilizzeremo nel processo che segue. Lo scope dei nomi dichiarati e' sempre locale al processo che segue. Un processo puo' essere un processo primitivo oppure un costrutto (che combina piu' processi primitivi). Questi sono di solo cinque tipi: assegnamenti, processi d'ingresso, processi d'uscita, processi nulli (SKIP) e processi di terminazione (STOP).
Gli assegnamenti (anche qui nulla di nuovo) permettono di associare valori alle variabili precedentemente dichiarate. Come in Pascal il simbolo di assegnamento e' ":=" (duepunti uguale). I processi di ingresso e di uscita permettono la comunicazione. Come nel modello CSP visto lo scorso mese, il comando di uscita e' rappresentato da un punto esclamativo quello di ingresso dal punto interrogativo. Alla sinistra di questi metteremo il nome del canale sul quale effettuare la comunicazione, alla destra l'oggetto da trasferire se si tratta di un comando d'uscita, una variabile targa per il comando d'ingresso. Ad esempio:

Pippo ! 118

invia sul canale "Pippo" l'intero 118, mentre:

Pippo ? A

riceve nella variabile A il valore depositato nel canale dal mittente. In OCCAM tutte le comunicazioni sono simmetriche e sincrone. Ogni canale e' utilizzato da un solo mittente e un solo destinatario e la comunicazione avviene tanto per il primo quanto per il secondo nel medesimo istante logico. Se il mittente arriva all'appuntamento prima del destinatario aspettera' che questo legga il messaggio inviato prima di proseguire per la sua strada. Discorso analogo per destinatario che aspettera' il mittente nel caso in cui dovesse eseguire la sua "receive" prima della corrispondente "send". Come per le variabili il canale, nome e tipo, deve essere dichiarato prima dell'utilizzo da parte del processo. Il tipo del canale corrisponde al tipo del messaggio che dovra' trasportare. Occorre sottolineare che il canale, nella stesura di un programma OCCAM, e' un oggetto logico che diventera' fisico solo nel momento in cui verra' lanciata l'applicazione. Se l'applicazione multitask che stiamo lanciando girera' su un singolo transputer il canale puo' essere inteso come una struttura implementata in memoria in cui il processo mittente inserisce il messaggio da trasferire, il processo destinatario preleva il messaggio in arrivo. Se la stessa applicazione (senza bisogno di ricompilazione alcuna) viene invece lanciata su piu' transputer, processi in esecuzione su chip diversi accedendo al canale di comunicazione, di fatto utilizzeranno i link fisici di cui il transputer dispone e con i quali dialoga con gli altri transputer.
I principali costrutti (per combinare piu' processi primitivi) sono:

SEQ
IF
CASE
WHILE
PAR
ALT

Il primo, il piu' semplice, permette di eseguire piu' processi in sequenza. Ad esempio:

SEQ
a:=1
b:=2
Canale1 ! a+b
Canale2 ? R

i quattro processi indicati dopo SEQ (attenzione che in OCCAM quelle che sembrano normali statement sono processi essi stessi!) saranno eseguiti in sequenza, come in un normale linguaggio di programmazione. In pratica SEQ identifica un blocco ed e' esso stesso (a sua volta) un processo. Quindi possiamo associare a questo alcune dichiarazioni locali che non saranno piu' valide una volta eseguita la sequenza.
Dove termina il costrutto SEQ ? Ovvero: qual e' l'ultima istruzione del SEQ in cui ci troviamo ? In OCCAM i blocchi sono tutti delimitati dall'indentazione: due caratteri a destra per iniziare una sequenza, due caratteri a sinistra per terminarla. Cosi', il frammento di codice:

SEQ
a:=1
b:=2
Canale1 ! a+b
Canale2 ? R
c:=0
d:=a+R

e' in pratica formato da tre processi. Un primo processo SEQ (a sua volta composto da quattro processi) e due processi di assegnamento. Chiaramente il tutto deve poi essere combinato per formare (in qualsiasi altro modo) un ulteriore unico processo combinato dai tre processi appena descritti. Se ad esempio questi tre processi devono essere eseguiti in sequenza bastera' aggiungere un altro SEQ all'inizio scrivendo cosi':

SEQ
SEQ
a:=1
b:=2
Canale1 ! a+b
Canale2 ? R
c:=0
d:=a+R

proviamo allora a completare questo codice per farlo diventare un programma OCCAM. Mancano innanzitutto le dichiarazioni, immaginiamo di voler limitare lo scope della variabile "b" al solo SEQ interno; tutte le altre dichiarazioni sono, per cosi' dire, globali:

INT a, c, d, R:
CHAN OF INT Canale1, Canale2:
SEQ
INT b:
SEQ
a:=1
b:=2
Canale1 ! a+b
Canale2 ? R
c:=0
d:=a+R

La lettura del codice dovrebbe essere abbastanza semplice cosi' come riconoscere in questo la struttura base fornita all'inizio. La dichiarazioni iniziale e' formata da due dichiarazioni, una per le variabili di tipo INT l'altra per i canali anch'essi di tipo INT. Segue l'unico processo SEQ a sua volta formato da altri processi: la dichiarazione della variabile "b" e' locale al SEQ piu' interno quindi non esiste piu' una volta terminata l'esecuzione di questo.
Detto questo non ci rimane che svelarvi il funzionamento degli altri costrutti. Rapidamente:

IF
{Espressione Booleana1}
Processo1
{Espressione Booleana2}
Processo2
:
:
{Espressione BooleanaN}
ProcessoN

e' il costrutto condizionale. In pratica viene eseguito il primo processo (che puo' essere a sua volta primitivo o combinato come ci pare) la cui espressione booleana ha valore TRUE. Da segnalare che se nessuna espressione booleana e' verificata l'intero programma si blocca terminando li' l'esecuzione (comportamento simile al processo primitivo STOP). Per questo e' conveniente prendere gli opportuni provvedimenti prevedendo una uscita finale con espressione booleana costante TRUE magari con processo SKIP se non dobbiamo eseguire nulla in questo caso. Esempio:

IF
a>0
a:= a-1
b>0
b:=b+1
c>0
SEQ
a:=0
b:=0
c:=c-1
TRUE
SKIP


alla terza scelta e' stato associato un processo combinato (un SEQ) quindi nel caso in cui le prime due espressioni danno esito falso e "c" e' maggiore di zero saranno eseguite le tre line indicate. Come caso finale abbiamo inserito un TRUE...SKIP che ci permette di continuare l'esecuzione nel caso in cui nessuna delle tre espressioni logiche dia esito TRUE.
Il costrutto CASE e' molto simile (come al solito) all'IF: e' eseguito il primo processo corrispondente all'espressione che ha lo stesso valore della variabile del CASE. Come nell'IF e' necessario che almeno una alternativa sia verificata pena il blocco del programma. Per forzare una uscita d'emergenza si usa lo statament ELSE. Esempio:

CASE x
1
x:=0
2
x:=5
ELSE
x:=x-1

se x e' uguale ad 1 sara' eseguito x:=0, se x e' uguale a 2 sara' eseguito x:=5, in tutti gli altri casi x sara' diminuito di 1.
Il costrutto WHILE permette di effettuare loop su condizione. Ad esempio:

WHILE a>0
SEQ
x:=x+2
a:=a-x

esegue il processo SEQ (formato a sua volta da due processi di assegnamento) fintantoche' "a" e' maggiore di zero.
Il costrutto PAR (gia' precedentemente citato) permette di eseguire tutti i processi indicati in parallelo. Naturalmente devono esistere le condizioni affinche' l'esecuzione in parallelo sia possibile. E' sintatticamente simile al costrutto SEQ. Ad esempio:

PAR
a:=a+1
Canale ! b
c:=2

esegue in parallelo i tre processi indicati. Si sarebbe avuto errore a tempo di compilazione se, ad esempio, avessimo scritto:

PAR
a:=a+1
Canale ! a
c:=2

(notare la 'a' al posto della 'b' nel processo di uscita) In questo caso non e' possibile l'esecuzione in parallelo dal momento che la variabile 'a' e' contemporaneamente modificata nel primo processo ed utilizzata nel secondo.
Per finire, il costrutto ALT permette di effettuare il controllo del non determinismo come gia' visto negli articoli che hanno preceduto questa puntata.
La forma piu' semplice del costrutto ALT non prevede, per la verita', alcun controllo ma permette di attendere simultaneamente messaggi da piu' canali. Non appena arriva un messaggio su uno dei canali indicati, sara' letto il messaggio ed, eventualmente, eseguito un apposito processo. Esempio:

ALT
chan1 ? x
{processo 1}
chan2 ? y
{processo 2}
chan3 ? z
{processo 3}

La versione "completa" del costrutto ALT permette di aggiungere una espressione logica ad ogni processo di ingresso in modo da ottenere una guardia d'ingresso. Ad esempio:

ALT
(ax>0) & chan1 ? x
{processo 1}
(ay>0) & chan2 ? y
{processo 2}
(az>0) & chan3 ? z
{processo 3}

in questo modo e' possibile restringere il range di canali da testare in funzione del valore delle espressioni booleane che abbiamo inserito prima di ogni processo di ingresso: saranno testati solo i canali le cui espressioni booleane hanno dato esito positivo. Se tutte le espressioni booleane danno esito negativo il programma si blocca: anche in questo caso e' necessario prevedere una via d'uscita tramite la solita costante TRUE.

REPLICATOR

Non si tratta di un film di fantascienza anche se, per alcuni versi potremmo definirla tale. Ai costrutti SEQ, PAR, ALT e IF e' possibile aggiungere un indice in modo da far "ciclare" il costrutto stesso. In questa sede analizzaremo solo SEQ e PAR che utilizzeremo piu' spesso in seguito, rimandanto le altre spiegazioni al momento piu' opportuno. Il costrutto:

SEQ variabile = valore FOR volte
{processi}

esegue i processi indicati tante volte quante indicate dopo la parola chiave FOR assegnando alla variabile indicata il valore iniziate di volta in volta incrementato di uno. Ad esempio:

SEQ i=0 FOR 5
x = i*2
canale ! x

equivale a scrivere:


SEQ
x = 0
canale ! x
x = 2
canale ! x
x = 4
canale ! x
x = 6
canale ! x
x = 8
canale ! x


Il costrutto:

PAR variabile = valore FOR volte
{processi}

Esegue i processi indicati in parallelo tante volte quante indicate dopo la parola chiave FOR utilizzando in ogni processo lanciato un diverso indice della variabile indicata.
Come nel normale PAR non deve verificarsi che una qualsiasi variabile modificata da un processo parallelo sia contemporaneamente utilizzata da un altro processo parallelo.

Conclusioni

Non facciamo in tempo, questo mese, a mostrarvi un esempio di programma OCCAM. Tenete duro fino al prossimo MC: intanto, tra un bagno ed una rilassante passeggiata in riva al mare, studiatevi un po' tutto quello che abbiamo mostrato in questa puntata. Vi assicuro comunque che ne vedremo delle belle...

Articolo pubblicato su www.digiTANTO.it - per ulteriori informazioni clicca qui