Επόμενο:ΠΟΛΛΑΠΛΑΣΙΑΣΜΟΣ ΠΙΝΑΚΑ ΜΕ ΔΙΑΝΥΣΜΑ
Πάνω:Διάφορα Προβλήματα Παράλληλου Προγραμματισμού
Πίσω: ΣΥΣΤΗΜΑ ΚΕΝΤΡΙΚΗΣ ΘΕΡΜΑΝΣΗΣ
ΠΑΡΑΛΛΗΛΗ ΤΑΞΙΝΟΜΗΣΗ ΔΕΝΤΡΟΥ
Η ταξινόμηση είναι από τους πιό συνηθισμένους υποψήφιους γιά παράλληλη λύση γιατί συνήθως οι αλγόριθμοί της περιέχουν κάποια στοιχεία της μεθόδου 'διαίρει και βασίλευε' (divide and conquer). Αυτό σημαίνει ότι η ταξινόμηση πραγματοποιείται με την διαίρεση της σε απλούστερες, επί μέρους ταξινομήσεις, κάθε μιά από τις οποίες διαιρείται διαδοχικά μέχρις ότου μένουν να εκτελεστούν μόνον απλούστατες λειτουργίες. Μιά τέτοια στρατηγική βοηθά στον εύκολο διαχωρισμό των ξεχωριστών τμημάτων του αρχικού προβλήματος που μπορούν να επιλυθούν παράλληλα.
Το πρόγραμμα αποτελείται από έναν αριθμό απλών διεργασιών συνδεδεμένων μεταξύ τους σε μία δυαδική δενδρική δομή. 'Οπως και στη περίπτωση του πολλαπλασιασμού των πινάκων, καμμιά διεργασία δεν χρειάζεται να ξέρει που ακριβώς βρίσκεται μέσα στο δένδρο. Υπάρχουν μόνο δύο τύποι διεργασιών: τα φύλλα και οι κόμβοι. Και πάλι, η κάθε διεργασία είναι ανεξάρτητη του μεγέθους του προβλήματος, και αποθηκεύει μόνο δύο το πολύ τιμές και μερικές σημαίες (flags), ανεξάρτητα από τον αριθμό των ταξινομούμενων στοιχείων. 'Ενα μεγαλύτερο πρόβλημα χρειάζεται μεγαλύτερο δένδρο, αλλά τα συστατικά του δένδρου παραμένουν τα ίδια. Η στρατηγική έγκειται στην διανομή των στοιχείων πρός ταξινόμηση (π.χ. αριθμών) μέσα στο δένδρο, διά μέσου της ρίζας του, μέχρι τα στοιχεία να απλωθούν, ένα σε κάθε φύλλο. Στη συνέχεια κάθε διεργασία στέλνει στην πατρική της διεργασία την ακολουθία των αριθμών που έλαβε, αλλά ταξινομημένη σε αύξουσα σειρά. Γιά ένα φύλλο αυτή η διαδικασία είναι απλή, καθώς ο ένας μόνον αριθμός που έχει αποτελεί μιά απλούστατη ακολουθία αριθμών σε αύξουσα σειρά. Κάθε κόμβος στηρίζεται στις ταξινομημένες ακολουθίες που θα λάβει από τα παιδιά του, και τις οποίες συγχωνεύει σε μία ταξινομημένη σειρά, την οποία και στέλνει με τη σειρά του σαν ακολουθία εξόδου.
Για λόγους ομοιομορφίας, η ρίζα αντιμετωπίζεται σαν ένας απλός κόμβος, και εισάγεται μια διαδικασία εικονικής ρίζας, που φαίνεται σαν πατέρα της ρίζας, η driver_in. Επίσης υποθέτουμε ότι το δυαδικό δέντρο είναι πλήρες και ισορροπημένο.
Για κάθε κόμβο i, τα παιδιά του δεικτοδοτούνται σαν 2i+1 το αριστερό και 2i+2 το δεξιό. Τα κανάλια με δείκτη i ενώνουν τη διεργασία i με την πατρική της, ενώ για τη σύνδεση με τα παιδιά ακολουθείται η ίδια δεικτοδότηση όπως και στους κόμβους.
Υπάρχουν δύο φάσεις στη δραστηριότητα του δέντρου. Πρώτα η ακολουθία των αταξινόμητων αριθμών διανέμεται στα φύλλα. Κατόπιν η ταξινομημένη ακολουθία συλλέγεται μέσω των κόμβων. Κατά τη διάρκεια της φάσης της διανομής, κάθε κόμβος δέχεται μια ακολουθία αριθμών από την πατρική διεργασία. Αφού η διεργασία του κόμβου δεν γνωρίζει τη θέση της στο δέντρο, ούτε το μέγεθος του δέντρου, δε μπορεί να ξέρει πόσους αριθμούς να περιμένει. Για να δηλώνεται λοιπόν το τέλος της ακολουθίας πριν από κάθε αριθμό προηγείται ένα σήμα με τιμή TRUE, και μετά τον τελευταίο αριθμό, ακολουθεί ένα σήμα FALSE. Η διανομή των αριθμών προς τις διεργασίες-παιδιά γίνεται εναλλακτικά προς τα αριστερά και τα δεξιά.
Αφού οι διεργασίες λειτουργούν σε αυθαίρετα μεγάλο δέντρο, τότε και κατά τη φάση της συγχώνευσης θα παραληφθεί πάλι άγνωστο πλήθος αριθμών, οπότε και το πρωτόκολλο εισόδου θα είναι αντίστοιχο. Για να γίνει ταξινόμηση με συγχώνευση, οι αριθμοί που παραλαμβάνονται πρέπει να συγκρίνονται μεταξύ τους ανά δύο, και αυτό απαιτεί την αποθήκευση δύο αριθμών. Αφού το κάθε παιδί στέλνει την ακολουθία του σε αύξουσα σειρά, η κεφαλή της ακολουθίας είναι ο μικρότερος από τους αριθμούς της σειράς. Έτσι η διεργασία συγχώνευσης συγκρίνει τις δύο κεφαλές, περνά στην έξοδο το μικρότερο αριθμό, εισάγει τον επόμενο αριθμό από την ακολουθία που επιλέχθηκε, και συνεχίζει μέχρι την εξάντληση των ακολουθιών. Η επανάληψη εκτελείται μέχρι να εξαντληθούν οι δύο ακολουθίες εισόδου, συνθήκη που ελέγχεται από τις λογικές μεταβλητές left_more και right_more.
Αναλυτικότερα το πρόγραμμα είναι το ακόλουθο:
Program Parallhlh_ta3inomhsh;
Const
depth_tree=3;
number_leaves=8; (*number_leaves=2^depth_tree*)
number_forks=number_leaves-1;
number_processes=number_forks+number_leaves;
number_channels=number_processes;
root=0;
first_fork=root;
first_leaf=first_fork+number_forks;
true=-1;false=-99;
type
chan=channel of integer;
pin=array[0..number_channels+1] of chan;
var
up,down:pin;
i:integer;
Όπως είπαμε και παραπάνω η διεργασία αυτή εισάγει την εικονική ρίζα.
Procedure driver_in(var up,down:chan);
var
i,number:integer;
begin
for i:=0 to number_leaves-1 do
begin
writeln('dwse ton arithmo');
readln(number);
up:=true;
up:=number;
end;
up:=false;
end;
Η διεργασία εμφάνισης των αποτελεσμάτων.
Procedure driver_out(var down:chan);
var
number,temp:integer;
begin
for i:=0 to number_leaves-1 do
begin
if down? then
temp:=down;
if down? then
number:=down;
writeln(number:3,' ');
end;
end;
Η διεργασία διανομής των αριθμών μέσα στο δέντρο.
Procedure a_fork_distribute(var up,left_up,right_up:chan);
const
leftward=0;rightward=1;
var
more,inclination,number:integer;
begin
inclination:=leftward;
more:=up;
while more=true do
begin
number:=up;
if inclination=leftward then
begin
left_up:=true;
left_up:=number;
inclination:=rightward;
end
else if inclination=rightward then
begin
right_up:=true;
right_up:=number;
inclination:=leftward;
end;
more:=up;
end;
left_up:=false;
right_up:=false;
end;
Η διεργασία του φύλλου επιστρέφει τον αριθμό πίσω στον πατέρα.
Procedure leaf(var up,down:chan);
var
number,i:integer;
begin
for i:=0 to number_channels do
begin
if up? then
begin
number:=up;
down:=number;
end;
end;
end;
Η διεργασία συγχώνευσης των αριθμών.
Procedure a_fork_gather(var down,left_down,right_down:chan);
var
left_more,left_min,right_more,right_min:integer;
begin
left_more:=left_down;
left_min:=left_down;
right_more:=right_down;
right_min:=right_down;
while (left_more=true) or (right_more=true) do
begin
if ( left_more=true) and ((right_more=false) or (left_min<=right_min)) then
begin
down:=true;
down:=left_min;
left_more :=left_down;
if left_more=true then left_min:=left_down;
end
else if (right_more=true) and ((left_more=false) or (left_min>=right_min)) then
begin
down:=true;
down:=right_min;
right_more:=right_down;
if right_more=true then right_min:=right_down;
end;
end;
down:=false;
end;
Το κυρίως πρόγραμμα.
Begin
driver_in(up[root],down[root]);
forall i:=first_fork to number_forks-1 do
var temp1,temp2:integer;
begin
temp1:=(2*i)+1;
temp2:=(2*i)+2;
a_fork_distribute(up[i],up[temp1],up[temp2]);
end;
forall i:=first_leaf to (number_channels-1) do
leaf(up[i],down[i]);
forall i:=first_fork to number_forks-1 do
var temp1,temp2:integer;
begin
temp1:=(2*i)+1;
temp2:=(2*i)+2;
a_fork_gather(down[i],down[temp1],down[temp2]);
end;
writeln;
writeln(' oi arithmoi ta3inomhmenoi einai:');
writeln;
driver_out(down[root]);
End.
Tα αποτελέσματα για μια εκτέλεση του προγράμματος με τα παρακάτω δεδομένα είναι:
dwse ton arithmo 236 dwse ton arithmo -5 dwse ton arithmo 12 dwse ton arithmo 49 dwse ton arithmo -100 dwse ton arithmo 753 dwse ton arithmo 0 dwse ton arithmo 122
oi arithmoi ta3inomhmenoi einai:
-100 -5 0 12 49 122 236 753
Επόμενο:ΠΟΛΛΑΠΛΑΣΙΑΣΜΟΣ ΠΙΝΑΚΑ ΜΕ ΔΙΑΝΥΣΜΑ
Πάνω:Διάφορα Προβλήματα Παράλληλου Προγραμματισμού
Πίσω: ΣΥΣΤΗΜΑ ΚΕΝΤΡΙΚΗΣ ΘΕΡΜΑΝΣΗΣ