Επόμενο:ΠΟΛΛΑΠΛΑΣΙΑΣΜΟΣ ΠΙΝΑΚΩΝ Πάνω:Διάφορα Προβλήματα Παράλληλου Προγραμματισμού Πίσω:ΠΑΡΑΛΛΗΛΗ ΤΑΞΙΝΟΜΗΣΗ

ΠΟΛΛΑΠΛΑΣΙΑΣΜΟΣ ΠΙΝΑΚΑ ΜΕ ΔΙΑΝΥΣΜΑ

Μια από τις πιο απλές παράλληλες διατάξεις που έχουν προταθεί για τον πολλαπλασιασμό πίνακα με διάνυσμα είναι μια σωληνωτή διάταξη επεξεργαστών, με διαμόρφωση όμοια με αυτή των στοιχείων του διανυσμάτων του αποτελέσματος, δηλαδή στη περίπτωσή μας το y. Ο επεξεργαστής p_i, με i = 0,1,2, έχει αποθηκευμένο το στοιχείο k_i και πραγματοποιεί εσωτερικό γινόμενο με βάση αυτό το στοιχείο, και τα δεδομένα εισόδου, δηλαδή τα διανύσματα x και a_i^T, όπου a_i^T είναι η i γραμμή του πίνακα Α. Τα δεδομένα εισόδου “διέρχονται” από τον επεξεργαστή και οι υπολογισμοί γίνονται όπως εξηγείται παρακάτω.

Τα στοιχεία του διανύσματος x εισάγονται στον πίνακα από την αριστερή πλευρά (δύση, west), και μετακινούνται προς τα δεξιά (ανατολή, east). Ταυτόχρονα τα στοιχεία των γραμμών του πίνακα Α εισέρχονται από την άνω πλευρά (βορράς, north) και “καταναλώνονται” από τον αντίστοιχο επεξεργαστή προς τα κάτω (νότος, south), μέσα από τα αντίστοιχα κανάλια. Μετά από κάθε μετακίνηση στοιχείου οι επεξεργαστές πραγματοποιούν παράλληλα από ένα βήμα εσωτερικού γινομένου, το αποτέλεσμα του οποίου συσσωρεύεται τοπικά. Έτσι μετά το τέλος των υπολογισμών το στοιχείο y_i του τελικού διανύσματος βρίσκεται στον επεξεργαστή p_i. Το χρονοδιάγραμμα δίνεται στον πίνακα που ακολουθεί όπου ο εκθέτης του y σημειώνει το βήμα εσωτερικού γινομένου.

Κάθε επεξεργαστής έχει τρεις δουλειές να κάνει κατά τη διάρκεια ενός πολλαπλασιασμού πίνακα επί διάνυσμα:

• να πάρει το x από τη δύση και το a από το βορρά
• να υπολογίσει το βήμα εσωτερικού γινομένου
• να στείλει το x προς την ανατολή

Ο κώδικας του παράλληλου αυτού προγράμματος έχει ως εξής:

Program pollaplasiasmos_pinaka_me_dianysma;

    Const

        n=3;

    Type

        chan=channel of integer;

        pin=array[0..n] of integer;

        pin1=array[0..n,0..n] of integer;

    Var

        time,i:integer;

        x,y,k:pin;

        a:pin1;

        north_south:array[0..n] of chan;

        east_west:array[0..n+1] of chan;
 

Στη διεργασία αυτή πραγματοποιείται το εσωτερικό γινόμενο καθώς και οι τρεις δουλειές που κάνει κάθε επεξεργαστής κατά τη διάρκεια ενός πολλαπλασιασμού.

Procedure ips_cell(k:integer;var y:integer;var north,east,west:chan);

    var

        a,i,tmp:integer;

        temp:array[0..1] of integer;

    begin

        y:=k;

        temp[1]:=0;

        for i:=0 to n do

        begin

            temp[0] := east;

            a := north;

            y:= y+(a*temp[0]);

            temp[1] := temp[0];

            west := temp[1];

        end;

    end;

Διεργασία παραγωγής του x.

Procedure produce_x(n:integer;var out:chan);

    var

        i:integer;

    begin

        for i:=0 to n do

            out:=x[i];

    end;

 

Αυτή είναι η διεργασία παραγωγής για κάθε γραμμή του Α.

Procedure produce_a(n,index:integer;var out:chan);

    var

        i:integer;

    begin

        for i:=0 to n do

            out:=a[index,i];

    end;

Κατανάλωση των τελικών εξόδων του προγράμματος:

Procedure discard_x(n:integer;var in:chan);

    var

        i,temp:integer;

 

    begin

        for i:=0 to n+1 do

        begin

            if in? then temp:=in;

        end;

    end;

Η αρχικοποίηση των πινάκων και των διανυσμάτων:

Procedure initialise(n:integer;var x,k:pin;var a:pin1);

    var

        i,j:integer;

    begin

        writeln('dwse ta stoixeia toy a');

        for i:=0 to n do

            for j:=0 to n do

                readln(a[i,j]);

        writeln;

        writeln('dwse ta stoixeia toy x');

        for i:=0 to n do

            readln(x[i]);

        writeln;

        writeln('dwse ta stoixeia toy k');

        for i:=0 to n do

            readln(k[i]);

            writeln;

  end;

Το κυρίως πρόγραμμα :

Begin

    initialise(n,x,k,a);

    fork produce_x(n,east_west[0]);

    fork forall i:=0 to n do

        produce_a(n,i,north_south[i]);

    fork forall i:=0 to n do

        ips_cell(k[i],y[i],north_south[i],east_west[i],east_west[i+1]);

    fork discard_x(n,east_west[n+1]);

    join;join;join;join;

    writeln(' to dianysma y einai:');

    write('y = ');

    for i:=0 to n do

        write(y[i]:3);

End.

Για παράδειγμα τα αποτελέσματα για μια εκτέλεση του προγράμματος με τα παρακάτω δεδομένα είναι:

dwse ta stoixeia toy a :

dwse ta stoixeia toy a :

 

     8         3        2       -1

Α =  5         6        4        8

    -3         9        10       4

     3        -2        5        8


dwse ta stoixeia toy x :

 

x = 4 2 5 1

 

dwse ta stoixeia toy k :

 

k = 8 10 -2 5

 

to dianysma y einai:

 

y = 55     70     58      46 

Επόμενο:ΠΟΛΛΑΠΛΑΣΙΑΣΜΟΣ ΠΙΝΑΚΩΝ Πάνω:Διάφορα Προβλήματα Παράλληλου Προγραμματισμού Πίσω: ΠΑΡΑΛΛΗΛΗ ΤΑΞΙΝΟΜΗΣΗ