Implementazione Iterativa

L'analisi di un programma sequenziale in termini di grafi di dipendenza dei data ne evidenzia il possibile parallelismo. Per i programmi riportati di seguito viene presentata

• la definizione astratta dell'algoritmo sequenziale,

• la sua implementazione sequenziale,

• il corrispondente grafo di dipendenza dei dati,

• l'implementazione mediante coroutine, con un meccanismo di comunicazione asincrona basato sullo scambio messaggi, in modo da realizzare un'esecuzione parallel control flow dell'algoritmo.

Somma dei Primi Numeri Interi

La definizione dell'algoritmo è molto semplice. Indicata con S(n) la somma in questione, vale la seguente definizione ricorsiva

S(0) = 0
S(n) = S(n-1) + n

  function nSum( N : integer ) : integer;
  var K : integer;
      S : integer;
  begin
    K := N;
    S := 0;
    while I > 0 do
      begin
        S := S + I;
        K := K - 1
      end;
    nSum := S
  end;

Grafo dataflow della somma dei primi numeri interi

Per ottenere l'implementazione in Concurrent Pascal è sufficiente sostituire i due cicli computazionali del grafo dataflow con altrettante coroutine, dove

• sLoop, corrispondente alla variabile S della rappresentazione sequenziale, è utilizzato per accumulare i valori delle somme successive,
• kLoop, corrispondente alla variabile K della rappresentazione sequenziale, tiene traccia del numero di iterazioni del ciclo sLoop

Si ha, allora, la richiesta implementazione

program nSum(input,output);
{$V+}
  
  var iC : Channel;
      xC : Event;
       N : integer;
       T : integer;
                 
  
  procedure kLoop( n : integer );
  var k : integer;
     xF : boolean;
  begin
    k := n;
    repeat
      xF := k = 0;
      Cause( xC, xF );
      if not xF then
        begin
          Send( iC, k );
          k := k - 1
        end
    until xF
  end;
  
  procedure sLoop( var s : integer );
  var k : integer;
     xF : boolean;
  begin
    s := 0;
    repeat
      Await( xC, xF );
      if not xF then
        begin
          Receive( iC, k );
          s := s + k
        end
    until xF
  end;
  
begin
  InitChannel( iC );
  StartEvent( xC );
  writeln;
  writeln('Somma dei primi n numeri interi');
  writeln;
  write('Enter N : ');
  readln( N );
  cobegin
    kLoop( N );
    sLoop( T )
  coend;
  writeln('nSum(', N:1, ') = ', T:1 )
end.

Divisione Intera

La struttura dello schema computazionale è molto semplice e si basa sul noto algoritmo di Euclide. Indicati con n ed m due interi qualunque, purchè il secondo non sia nullo, la loro divisione intera n/m deve fornire un'unica coppia di interi q ed r tali che

Tralasciando di scrivere l'ovvia funzione Pascal, in forma iterativa, è presto visto che l'implementazione concorrente deve essere caratterizzata da due cicli computazionali

• rLoop, corrispondente alla variabile R della rappresentazione sequenziale, ed utilizzato per controllare il numero di iterazioni, nel senso che il ciclo viene mantenuto finchè il valore di R non rappresenta il resto della divisione,
• qLoop, corrispondente alla variabile Q della rappresentazione sequenziale, per accumulare il valore che corrisponde al numero di cicli eseguiti da rLoop e che individua, al termine delle iterazioni, il quoziente della divisione.

Grafo dataflow della divisione intera

program IDiv(input,output);
{$V+}
  
  var xC : Event;
       A : integer;
       B : integer;
       T : integer;
                   
  procedure rLoop( N : integer; M : integer );
  var R : integer;
     xF : boolean;
  begin
    R := N;
    repeat
      xF := R < M;
      Cause( xC, xF );
      if not xF then R := R - M
    until xF
  end;
  
  procedure qLoop( var Q : integer );
  var xF : boolean;
  begin
    Q := 0;
    repeat
      Await( xC, xF );
      if not xF then Q := Q + 1
    until xF
  end;
  
begin
  StartEvent( xC );
  writeln;
  writeln('Calcolo della Divisione Intera');
  writeln;
  write('Enter N, M : ');
  readln( A, B );
  cobegin
    rLoop( A, B );
    qLoop( T )
  coend;
  writeln( A:1,' div ', B:1, ' = ', T:1 )
end.

Radice Quadrata Intera

La definizione dell'algoritmo è simile a quello già noto per la divisione intera. Indicata con Sqrt(n) la radice quadrata intera, vale la seguente definizione

che permette di realizzare immeditamente la seguente funzione Pascal, in forma iterativa

  function Sqrt( N : integer ) : integer;
  var I : integer;
      P : integer;
      K : integer;
  begin
    I := 0;
    P := 1;
    K := 0;
    while N > K do
      begin
        I := I + 1;
        P := P + 2;
        K := K + P
      end;
    Sqrt := I
  end;

Il grafo di dipendenza dei dati è facilmente derivabile dall'implementazione precedente, scorporando le operazioni all'interno del ciclo while su tre cicli distinti

Grafo dataflow della radice quadrata intera

Per ottenere l'implementazione in Concurrent Pascal è sufficiente sostituire i tre cicli del grafo dataflow con altrettante coroutine, dove

• kLoop, corrispondente alla variabile K della rappresentazione sequenziale, ed utilizzato per controllare il numero di iterazioni confrontando il valore quadratico di K col valore della variabile di ingresso N,
• pLoop, corrispondente alla variabile P della rappresentazione sequenziale, che determina l'i-esimo numero dispari utilizzato per valutare l'i-esimo valore quadratico K,
• iLoop, corrispondente alla variabile I della rappresentazione sequenziale, per accumulare il valore che rappresenta il numero di cicli eseguiti da kLoop e che individua, al termine delle iterazioni, la radice quadrata richiesta.

program DoSqrt(input,output);
{$V+}
  
  var pC : Channel;
      xC1 : Event;
      xC2 : Event;
      kC : Channel;
       N : integer;
       T : integer;
  
  procedure kLoop( N : integer );
  var K : integer;
      P : integer;
     xF : boolean;
  begin
    K := 1;
    repeat
      xF := K > N;
      Cause(xC1, xF );
      Cause(xC2, xF );
      if not xF then
        begin
          Receive( pC, P );
          K := K + P;
        end
      until xF
  end;
  
  procedure pLoop;
  var P : integer;
      K : integer;
     xF : boolean;
  begin
    P := 1;
    repeat
      Await( xC1, xF );
      if not xF then
        begin
          P := P + 2;
          Send( pC, P )
        end
    until xF
  end;
  
  procedure iLoop( var I : integer );
  var  xF : boolean;
  begin
    I := 1;
    repeat
      Await( xC2, xF );
      if not xF then I := I + 1
    until xF;
    I := I - 1
  end;
  
begin
  InitChannel( pC );
  InitChannel( kC );
  StartEvent( xC1 );
  StartEvent( xC2 );
  writeln;
  writeln('Calcolo della radice quadrata intera');
  write('Enter N : ');
  readln( N );
  cobegin
    kLoop( N );
    pLoop;
    iLoop( T )
  coend;
  write('Sqrt[', N:1, '] = ', T:1 );
  writeln
end.