Next              Up                Back               Contents

Επόμενο:Ασκήσεις Πάνω: Κεφάλαιο 4o : Επικοινωνία διεργασιών Πίσω:Αναφορές


 

ΠΡΟΓΡΑΜΜΑΤΙΣΤΙΚΕΣ ΕΡΓΑΣIΕΣ

 

1. Κόσκινο πρώτων αριθμών

 

Σε αυτή την εργασία θα πρέπει να γράψετε την παράλληλη έκδοση του κλασσικού αλγόριθμου κόσκινο του Ερατοσθένη που υπολογίζει πρώτους αριθμούς. Το πρόγραμμα είναι αποδοτικό και μπορεί να πετύχει ιδιαίτερα μεγάλες επιταχύνσεις.

Το πρώτο βήμα είναι να δούμε πως πρέπει να είναι το σειριακό πρόγραμμα κόσκινο του Ερατοσθένη. Για τον υπολογισμό των πρώτων αριθμών από το 1 ως το n, η βασική δομή δεδομένων είναι ένας απλός πίνακας τύπου boolean που ονομάζεται και περιέχει n στοιχεία. Κατά την αρχικοποίηση των δεδομένων, το πρόγραμμα θέτει την τιμή true σε όλα τα στοιχεία του πίνακα Prime. Στη συνέχεια, το πρόγραμμα θα αλλάξει τις τιμές σε ορισμένα στοιχεία από true σε false. Στο τέλος, τα εναπομείναντα στοιχεία του πίνακα που θα έχουν την τιμή true θα δείχνουν πρώτους αριθμούς. Το σειριακό πρόγραμμα φαίνεται παρακάτω:

 

PROGRAM Sieve;

    CONST n=100;

    VAR Prime:ARRAY[1..n] OF BOOLEAN;

        i,num,loc:INTEGER;

    BEGIN

        FOR i:=1 TO n DO

            Prime[i]:= TRUE;

        FOR num:=2 TO Trunc(Sqr(n)) DO

            IF Prime[num] THEN

            BEGIN

               loc := num + num;

               WHILE loc <= loc + num;

               BEGIN

                   Prime[loc] := False;

                   loc := loc +num;

               END;

           END;

    END.

Το πρόγραμμα έχει ένα βρόχο FOR ο οποίος σαρώνει τον πίνακα από την τιμή 2 έως την τετραγωνική ρίζα του n. Κάθε στοιχείο που έχει τιμή TRUE όταν σαρώνεται πρέπει να είναι ο πρώτος αριθμός. Ο πρωτοεμφανιζόμενος πρώτος αριθμός είναι ο 2. Για κάθε τέτοιο πρώτο αριθμό που αναγνωρίζεται (με την κλήση της num στο πρόγραμμα), ένας εσωτερικός βρόχος WHILE θα αλλάξει την τιμή όλων των πολλαπλάσιων αυτού του αριθμού στον πίνακα σε FALSE. Η μεταβλητή loc χρησιμοποιείται για να διατρέξει βηματικά τον πίνακα κατά το μέγεθος της μεταβλητής num. Αυτή η διεργασία θα απαλοίψει ελαχιστοποιήσει όλους τους μη πρώτους αριθμούς του πίνακα. Τα εναπομείναντα στοιχεία του πίνακα με τιμή TRUE στο τέλος αυτού του προγράμματος θα είναι όλοι οι πρώτοι αριθμοί.

Η εργασία σας είναι να γράψετε μια παράλληλη έκδοση αυτού του κόσκινου προγράμματος του Ερατοσθένη. Το πρόγραμμα παραλληλίζεται με το να τμηματοποιηθεί ο πίνακας Prime σε ίσου μεγέθους τμήματα και να δημιουργηθεί μια παράλληλη διεργασία για κάθε τμήμα. Τα τμήματα πρέπει να είναι αρκετά μεγάλα έτσι ώστε όλα τα στοιχεία που είναι μεγαλύτερα από την τετραγωνική ρίζα του n να περιέχονται στο πρώτο τμήμα. Η διεργασία που αναφέρεται στο πρώτο τμήμα είναι σχεδόν όμοια με αυτή του σειριακού προγράμματος που δίνεται παραπάνω. Η βασική διαφορά είναι ότι ο βρόχος WHILE τερματίζει όταν φτάνει στο τέλος του πρώτου τμήματος του πίνακα. Τα υπόλοιπα τμήματα θα τα χειριστούν οι δικές τους διεργασίες.

Όλες οι διεργασίες ξεκινούν αρχικοποιώντας τα τμήματα τους με τιμή TRUE. Αυτές οι αρχικοποιήσεις μπορούν να γίνουν παράλληλα. Στη συνέχεια η πρώτη διεργασία αναζητά την πρώτη τιμή TRUE, η οποία φυσικά είναι η 2. Ο αριθμός 2 στη συνέχεια στέλνεται σε όλες τις άλλες διεργασίες. Καθώς κάθε διεργασία λαμβάνει αυτό τον αριθμό, ξεκινάει το δικό της τμήμα με βήματα μεγέθους 2, αλλάζοντας έτσι κάθε αριθμό σε FALSE. Στη συνέχεια η πρώτη διεργασία την αναζήτηση της με τη χρήση του βρόχου για την επόμενη τιμή TRUE, και πάλι στέλνει αυτή την τιμή στις άλλες διεργασίες, όπου χρησιμοποιείται για την αλλαγή των τιμών TRUE σε FALSE. Σε αυτή την παράλληλη έκδοση του προγράμματος υπάρχει μια ξεχωριστή διεργασία που επεξεργάζεται κάθε τμήμα του προγράμματος παράλληλα.

Η εκπομπή του αριθμού σε κάθε βήμα μπορεί να γίνει πιο αποδοτική αν η πρώτη διεργασία στέλνει την τιμή αυτή μόνο στην δεύτερη διεργασία. Η δεύτερη διεργασία την στέλνει στην τρίτη, η τρίτη στην τέταρτη, κ.ο.κ. Περνώντας τον αριθμό από κάθε βήμα με αυτήν την διεργασία διασωλήνωσης ο συνολικός χρόνος εκτέλεσης μειώνεται.

Ένα άλλο σημαντικό θέμα είναι το πως η κάθε διεργασία ορίζει το σημείο εκκίνησης αφού λάβει τον αριθμό num. Τα βήματα θα είναι μεγέθους num, αλλά από που θα αρχίσει; Η απάντηση βρίσκεται στον πρώτο αριθμό αυτού του τμήματος του πίνακα που δεν είναι ορατός από την μεταβλητή num. Υποθέτοντας ότι το πρώτο στοιχείο του πίνακα σε αυτό το τμήμα είναι το Prime[first], η ακόλουθη Τεχνική μπορεί να χρησιμοποιηθεί σαν σημείο εκκίνησης:

remainder := first MOD num;

if remainder = 0 then starting point “first”

else starting point is (first DIV num + 1) * num

 

Γράψτε αυτή την παράλληλη έκδοση του προγράμματος και εκτελέστε την, χρησιμοποιώντας την Multi-Pascal. Ελέγξτε το πρόγραμμα σας, και πειραματιστείτε με διαφορετικά μεγέθη πίνακα για να δείτε πόση επιτάχυνση μπορείτε να επιτύχετε. Θα δείτε ότι πολύ μεγάλες επιταχύνσεις μπορούν να επιτευχθούν με μεγάλους πίνακες.

 

2. Διτονική Ταξινόμηση με Συγχώνευση

 

Σε αυτή την εργασία θα γράψετε ένα πρόγραμμα για την διτονική ταξινόμηση με συγχώνευση. Το πιο σημαντικό θέμα που ανακύπτει είναι η σύγκριση και η πιθανή εναλλαγή των τιμών ανάμεσα στις διεργασίες. Αν υπάρχουν n διεργασίες τότε η κάθε διεργασία έχει αριθμό αναγνώρισης μεγέθους d=log n bits. Επομένως κάθε διεργασία έχει d ενδυνάμες διεργασίες με τις οποίες πρόκειται να συνεργαστεί, και χρειάζεται τον δικό της πίνακα με d κανάλια για κάθε μια από αυτές τις διεργασίες. Για την σύγκριση των τιμών μιας διεργασίας με μια άλλη, η μια διεργασία στέλνει ένα αντίγραφο της τιμής της στην άλλη και λαμβάνει ένα αντίγραφο από αυτήν. Έτσι η κάθε διεργασία μπορεί να συγκρίνει τις τιμές της και να κρατήσει την μικρότερη ή μεγαλύτερη τιμή. Για να εξασφαλιστεί η σωστή διαδοχή των διεργασιών ένας πίνακας από κανάλια είναι απαραίτητος.

Εκτελέστε και επαληθεύστε το πρόγραμμα, χρησιμοποιώντας την Multi -Pascal. Συγκρίνετε την απόδοση αυτού του προγράμματος με αυτή της Ταξινόμησης Σειράς (Rank Sort) όσον αφορά το πεδίο τιμών του n.

 

ΠΡΟΤΕΙΝΟΜΕΝΕΣ ΛΥΣΕΙΣ

 

1.

program koskino;

    Const

       n=100;

    Var

       prime:array[1..n]of boolean;

       i,rootn,num,loc:integer;

       chan:array[1..n]of channel of integer;

procedure protoi(id:integer);

    var

       tmp,start,data,first,last,c:integer;

    begin

       data:=chan[id];                                      διαβάζει την τιμή από τα αριστερά

       chan[id+1]:=data;                                    στέλνει την τιμή προς τα δεξιά

       first:=((id-1)*rootn)+1;                             ο πρώτος αριθμός του τμήματος

       last:=id*rootn;                                      ο τελευταίος αριθμός του τμήματος

       if last>n then

           last:=n;

       tmp:=first mod data;

       start:=first;

       if tmp>0 then

           start:=((first div data) + 1) * data;             βρίσκει το πολλαπλάσιο του data

       while start<=last do

       begin

           prime[start]:=false;                              όλα τα πολλαπλάσια του data που ανήκουν στο τμήμα

           start:=start+data;                                γίνονται false

       end;

end;

Begin

    for i:=1 to ndo                                          Αρχικοποίηση

       prime[i]:=true;

   rootn:=round(sqrt(n));

    for num:=2 to rootn do

           if prime[num] then

           begin

               chan[2]:=num;

               forall i:=2 to (rootn+1) do

                       protoi(i);

              loc:=num+num;                                   έλεγχος του πρώτου τμήματος

             while loc<=rootn do

             begin

                    prime[loc]:=false;                                            όλα τα πολλαπλάσια του num που ανήκουν

                   loc:=loc+num;                              στο πρώτο τμήμα γίνονται false

           end;

       end;

       for i:=1 to n do                                       Εμφάνιση αποτελεσμάτων

               if prime[i] then writeln(i);

End.

 

2.

Program ditoniki;

    Const

        n=16;

        d=4;

    Type

        bitar=array [0..d-1] of integer;

    Var

        myid,s:integer;

        main:array[0..n-1]of channel of integer;

        data,tmpdata:array[0..n-1]of integer;

procedure retbits(myid:integer;var b:bitar);

    var

        nd,id,i:integer;

    begin

        nd:=n div 2;

        id:=myid;

        for i:=d-1 downto 0 do

        begin

            b[i]:=id div nd;

            id:=id mod nd;

            nd:=nd div 2;

        end;

    end;

function power2(t:integer):integer;

    var

        a,k:integer;

    begin

        k:=1;

        if t>0 then

            for a:=1 to t do

                k:=k*2;

        power2:=k;

    end;

procedure retnum(var id:integer;a:bitar);

    var

        i,tmpid:integer;

    begin

        tmpid:=0;

        for i:=d-1 downto 0 do

            tmpid:=tmpid+a[i]*power2(i);

        id:=tmpid;

    end;

procedure dsort(myid:integer);

    var

        i,j,s,syntid,tmp:integer;

        syntb,b:bitar;

    begin

        retbits(myid,b);

        for j:=d-1 downto 0 do

        begin

            syntb:=b;

            if syntb[j]=1 then

                syntb[j]:=0

            else

                syntb[j]:=1;

        retnum(syntid,syntb);

        main[syntid]:=data[myid];

        tmp:=main[myid];

        if b[j]=0 then

        begin

            if tmp<data[myid] then

            data[myid]:=tmp;

        end

        else

        begin

            if tmp>data[myid] then

            data[myid]:=tmp;

        end;

    end;

end;

Begin

    data[0]:=10;data[1]:=20;data[2]:=30;data[3]:=40; (*arxikopoihsh*)

    data[4]:=50;data[5]:=60;data[6]:=70;data[7]:=80;

    data[8]:=75;data[9]:=65;data[10]:=55;data[11]:=45;

    data[12]:=35;data[13]:=25;data[14]:=15;data[15]:=5;

    tmpdata:=data;

    forall s:=0 to n-1 do

        dsort(s);

    writeln('arxikh lista');

    for s:=0 to n-1 do (*emfanish apotelesmatwn*)

        write(tmpdata[s]:4);

    writeln;writeln;

    writeln('telikh lista');

    for s:=0 to n-1 do

        write(data[s]:4);

End.


     Next              Up                Back               Contents

Επόμενο:Ασκήσεις Πάνω: Κεφάλαιο 4o : Επικοινωνία διεργασιών Πίσω:Αναφορές