Επόμενο:ΤΟ ΠΑΙΧΝΙΔΙ ΤΗΣ 'ΖΩΗΣ' ΤΟΥ CONWAY Πάνω: Διάφορα Προβλήματα Παράλληλου Προγραμματισμού Πίσω: ΠΟΛΛΑΠΛΑΣΙΑΣΜΟΣ ΠΙΝΑΚΑ ΜΕ ΔΙΑΝΥΣΜΑ
ΠΟΛΛΑΠΛΑΣΙΑΣΜΟΣ ΠΙΝΑΚΩΝ
Ο πολλαπλασιασμός πινάκων μπορεί να ειδωθεί ως πολλαπλασιασμός ενός αριθμού διανυσμάτων με τον ίδιο πίνακα. Οι διαστάσεις της δυσδιάστατης διάταξης των επεξεργαστών εξαρτάται από το n. Γι’ αυτό λοιπόν δεν είναι δυνατόν να αποθηκεύει τον πίνακα Y του αποτελέσματος ούτε τον πίνακα K, οι οποίοι είναι διερχόμενοι, όπως και ο Χ. Αντίθετα μπορεί να τοποθετηθεί στους επεξεργαστές ο πίνακας Α του οποίου οι διαστάσεις είναι ίδιες με αυτές της διάταξης.
Στη διάταξη αυτή ο πίνακας Χ εισέρχεται από το πάνω μέρος της διάταξης, ταξιδεύει από βορρά προς νότο και “καταναλώνεται” καθώς εξέρχεται από το κάτω μέρος της διάταξης. Ο πίνακας Υ σχηματίζεται σταδιακά όπως ταξιδεύει από τη δύση προς την ανατολή και τελικά βγαίνει από τη δεξιά πλευρά της διάταξης. Αρχικά ο πίνακας Υ ουσιαστικά ταυτίζεται με τον πίνακα Κ που εισέρχεται από την αριστερή πλευρά και τα στοιχεία του οποίου αποτελούν τις αρχικές τιμές των αντίστοιχων στοιχείων του πίνακα Υ.
Κάθε επεξεργαστής έχει τρεις δουλείες να κάνει κατά τη διάρκεια ενός πολλαπλασιασμού πινάκων:
Το πρόγραμμα έχει ως εξής:
Program pollaplasiasmos_pinakwn;
Const
n=4;
m=3;
Type
pin=array[0..n,0..m] of integer;
pin1=array[0..n,0..n] of integer;
chan=channel of integer;
Var
i,j:integer;
x,y,k:pin;
a:pin1;
north_south,east_west:array[0..n+1,0..n+1] of chan;
Στη διεργασία αυτή πραγματοποιείται το εσωτερικό γινόμενο καθώς και οι τρεις δουλειές που κάνει κάθε επεξεργαστής κατά τη διάρκεια ενός πολλαπλασιασμού.
Procedure ips_cell(g,j,a:integer;var north,south,east,west:chan);
var
i:integer;
temp_x,temp_y:array[0..1] of integer;
begin
temp_x[1]:=0;
temp_y[1]:=0;
for i:=0 to m do
begin
temp_y[0]:=east;
temp_x[0]:=north;
temp_y[1]:=temp_y[0]+(a*temp_x[0]);
temp_x[1]:=temp_x[0];
west:=temp_y[1];
south:=temp_x[1];
end;
end;
Διεργασία παραγωγής του x.
Procedure produce_x(m,index:integer;var out:chan);
var
i:integer;
begin
for i:=0 to m do
out:=x[index,i];
end;
Διεργασία παραγωγής του k.
Procedure produce_k(m,index:integer;var out:chan);
var
i:integer;
begin
for i:=0 to m do
out:=k[index,i];
end;
Η διεργασία αυτή βγάζει τον πίνακα Υ από τη δεξιά πλευρά της διάταξης.
Procedure consume_y(n,m,index:integer;var in:chan);
var
i:integer;
begin
for i:=0 to m do
y[index,i]:=in;
end;
Κατανάλωση των τελικών εξόδων του προγράμματος:
Procedure discard_x(var in:chan);
var
i,temp:integer;
begin
for i:=0 to n+1 do
if in? then temp:=in;
end;
Ακολουθεί η αρχικοποίηση των πινάκων και των διανυσμάτων:
Procedure initialise(n,m: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
for j:=0 to m do
readln(x[i,j]);
writeln;
writeln('dwse ta stoixeia toy k');
for i:=0 to n do
for j:=0 to m do
readln(k[i,j]);
writeln;
end;
Και τέλος το κυρίως πρόγραμμα.
Begin
initialise(n,m,x,k,a);
fork forall i:=0 to n do
produce_x(m,j,north_south[0,i]);
fork forall i:=0 to n do
produce_k(m,i,east_west[i,0]);
join;join;
fork forall i:=0 to n do
forall j:=0 to n do
ips_cell(i,j,a[i,j],north_south[i,j],north_south[i+1,j],east_west[i,j],east_west[i,j+1]);
fork forall i:=0 to n do
discard_x(north_south[n,i]);
fork forall i:=0 to n do
consume_y(n,m,i,east_west[i,n+1]);
join;join;join;
write('o pinakas y einai: ');
writeln;
for i:=0 to n do
begin
for j:=0 to m do
write( y[i,j]:2);
writeln;
end;
End.
Για παράδειγμα τα αποτελέσματα για μια εκτέλεση του προγράμματος με τα παρακάτω δεδομένα είναι:
dwse ta stoixeia toy a :
8 3 2 -1
Α = 6 4 8
-3 9 10 4
3 -2 5 8
dwse ta stoixeia toy x :
3 5 4
x = 2 6 1
-4 7 -1
0 -3 2
dwse ta stoixeia toy k :
-5 1 5
k = 6 7 4
8 0 9
5 -4 2
o pinakas y einai:
17 76 36
y = 17 69 42
-23 97 4
-10 7 23
Επόμενο:ΤΟ ΠΑΙΧΝΙΔΙ ΤΗΣ 'ΖΩΗΣ' ΤΟΥ CONWAY Πάνω:Διάφορα Προβλήματα Παράλληλου Προγραμματισμού Πίσω: ΠΟΛΛΑΠΛΑΣΙΑΣΜΟΣ ΠΙΝΑΚΑ ΜΕ ΔΙΑΝΥΣΜΑ