Επόμενο:Aσκήσεις Πάνω: Κεφάλαιο 9o : Επιμερισμός δεδομένων Πίσω: Αναφορές
ΠΡΟΓΡΑΜΜΑΤΙΣΤΙΚΕΣ ΕΡΓΑΣΙΕΣ
1. Ανάπτυξη Περιοχής
Η επεξεργασία εικόνας είναι από τις πιο απαιτητικές υπολογιστικές εφαρμογές εξαιτίας της μεγάλης ποσότητας δεδομένων. Στους περισσότερους αλγόριθμους επεξεργασίας εικόνας διαφορετικοί επεξεργαστές μπορούν να επεξεργαστούν παράλληλα διαφορετικά τμήματα της εικόνας. Γι’ αυτό το λόγο η επεξεργασία εικόνας αποτελεί μια από τις μεγαλύτερες εφαρμογές των παράλληλων υπολογιστών. Όταν η επεξεργασία εικόνας πραγματοποιείται σε ένα σύστημα κατανεμημένης μνήμης, φυσικά η εικόνα πρέπει να επιμεριστεί στους διάφορους επεξεργαστές. Για κάποιους αλγόριθμους υπάρχει μια αλληλεπίδραση μεταξύ των διαφορετικών τμημάτων της εικόνας και συνεπώς απαιτείται κάποια ενδοδιεργασιακή επικοινωνία.
Ένας σημαντικός αλγόριθμος επεξεργασίας εικόνας ονομάζεται ανάπτυξη περιοχής. Αρχικά μια εικόνα διαιρείται σε γειτονικές περιοχές. Η διαδικασία ανάπτυξης περιοχής είναι το πρώτο βήμα στην αναγνώριση των αντικειμένων της εικόνας. Κάθε περιοχή έχει κάποια κοινά χαρακτηριστικά, όπως είναι το χρώμα ή η κλίμακα του γκρίζου. Ομαδοποιώντας τα εικονοστοιχεία σε περιοχές, γίνεται πιο εύκολη η αναγνώριση διαφόρων αντικειμένων ή περιοχών αντικειμένων στην εικόνα. Η εργασία αυτή αφορά το γράψιμο ενός προγράμματος συστήματος κατανεμημένης μνήμης που θα διαιρεί μια εικόνα σε περιοχές της ίδιας κλίμακας γκρίζου.
Η εικόνα θα αναπαρίσταται σαν ένας δι-διάστατος πίνακας ακεραίων. Κάθε ακέραια τιμή είναι η κλίμακα γκρίζου του αντίστοιχου εικονοστοιχείου στη δεδομένη θέση της εικόνας. Κάθε εικονοστοιχείο θεωρείται ότι έχει τέσσερα γειτονικά: πάνω, κάτω, αριστερά και δεξιά. Ένα μονοπάτι στην εικόνα καθορίζεται ως μια ακολουθία εικονοστοιχείων (x1, x2, ..., xn) τέτοια ώστε όλα τα κοντινά εικονοστοιχεία στην ακολουθία να είναι γειτονικά στην εικόνα. Μια περιοχή της εικόνας καθορίζεται ως ένα σύνολο εικονοστοιχείων, τέτοιο ώστε για δύο οποιαδήποτε εικονοστοιχεία x και y της περιοχής να υπάρχει ένα μονοπάτι από το x στο y που παραμένει αυστηρά μέσα στην περιοχή. Κατά συνέπεια μια περιοχή είναι απλώς ένα συνδεδεμένο σύνολο εικονοστοιχείων, όπου η σύνδεση μπορεί να μετακινηθεί μόνο κατά οριζόντια και κάθετη κατεύθυνση, όχι διαγώνια.
Το πρόγραμμά σας θα χωρίσει την εικόνα σε περιοχές με την ίδια κλίμακα γκρι. Για λόγους απλότητας υποθέστε ότι υπάρχουν μόνο δύο κλίμακες γκρι: 1 και 0. Σε αυτή την περίπτωση κάθε συνδεδεμένη περιοχή από 0 ή 1 θεωρείται ως ξεχωριστή περιοχή. Το αποτέλεσμα του προγράμματός σας θα πρέπει να είναι ένας αριθμός για κάθε εικονοστοιχείο της εικόνας, έτσι ώστε όλα τα εικονοστοιχεία της ίδιας περιοχής να έχουν τον ίδιο αριθμό. Για παράδειγμα, θεωρείστε την ακόλουθη εικόνα:
1 1 1 0 0 0
1 1 1 0 0 0
1 0 1 1 0 1
1 0 1 0 1 1
0 0 0 0 1 1
0 0 0 1 1 1
Η περιοχή που αριθμείται για αυτή την εικόνα είναι η ακόλουθη (θυμηθείτε ότι τα διαγώνια εικονοστοιχεία δεν συνδέονται):
1 1 1 2 2 2
1 1 1 2 2 2
1 3 1 1 2 2
1 3 1 3 4 4
3 3 3 3 4 4
3 3 3 4 4 4
Ένας ακολουθιακός αλγόριθμος που επιτυγχάνει αυτόν τον “χρωματισμό περιοχής” είναι ο ακόλουθος:
Για κάθε εικονοστοιχείο x έστω ότι το G(x) δηλώνει το επίπεδο 0 ή 1.
Κάθε εικονοστοιχείο x αρχικά έχει έναν μοναδικό αριθμό “χρώματος” Color(x) που βασίζεται στη θέση γραμμής και στήλης που έχει στον πίνακα.
Σάρωσε την εικόνα από τα αριστερά προς τα δεξιά και από πάνω προς τα κάτω και κάνε τα ακόλουθα σε κάθε εικονοστοιχείο x:
For each neighbor y of pixel x,
If G(y)= G(x) and Color(y) < Color(x),
then Color(x):= Color(y); (*Επιλογή του μικρότερου αριθμού χρώματος*)
Επαναλάβετε την παραπάνω σάρωση σε όλη την εικόνα μέχρι να μην συμβαίνει καμία αλλαγή. Το τελικό Χρώμα κάθε εικονοστοιχείου είναι ο αριθμός περιοχής του.
Η εργασία αυτή αφορά την προσαρμογή αυτού του ακολουθιακού αλγορίθμου ανάπτυξης περιοχής έτσι ώστε να εκτελείται αποδοτικά σε Υπερκύβο συστήματος κατανεμημένης μνήμης. Φυσικά η εικόνα θα πρέπει να επιμεριστεί στους επεξεργαστές του Υπερκύβου. Ένας πιθανός τρόπος οργάνωσης του προγράμματος αυτού είναι να το μοντελοποιήσετε μετά το πρόγραμμα Jacobi με επιμερίσεις κατά γραμμή και ανταλλαγή των οριακών τιμών μεταξύ των επεξεργαστών.
Προσπαθήστε να κάνετε το πρόγραμμα να εκτελείται όσο το δυνατόν πιο αποδοτικά και να επιτυγχάνει την μεγαλύτερη δυνατή παράλληλη επιτάχυνση χρησιμοποιώντας την Multi-Pascal. Αρχικά κατά τη διάρκεια του ελέγχου και της αποσφαλμάτωσης χρησιμοποιήστε μικρές εικόνες. Μετά κατά τη διάρκεια του ελέγχου απόδοσης χρησιμοποιήστε μεγαλύτερες τιμές για να αυξήσετε το μέγεθος της διεργασίας. Πειραματιστείτε με διάφορες τιμές της βασικής καθυστέρησης επικοινωνίας και δείτε πως επιδρούν στην απόδοση του προγράμματος.
2. Αλγόριθμος Jacobi σε Πλέγμα
Η Διχρωματική Επανάληψη είναι μια εναλλακτική μέθοδος για τον παράλληλο αλγόριθμο Jacobi, η οποία παράγει πιο γρήγορη σύγκλιση. Αυτή η μέθοδος περιγράφεται στο κεφάλαιο 6 στην προγραμματιστική εργασία 1. Σκοπός της παρούσας εργασίας είναι να γράψετε ένα πρόγραμμα Jacobi για μια τοπολογία Δι-διάστατου Πλέγματος χρησιμοποιώντας την Διχρωματική Επανάληψη. Το πρόγραμμά σας θα πρέπει να χρησιμοποιεί τη δι-διάστατη μέθοδο επιμερισμού των δεδομένων του πίνακα, στην οποία κάθε τμήμα έχει το σχήμα ενός μικρού τετραγώνου, όπως φαίνεται στο κάτω μέρος του σχήματος 9.15. Οργανώστε έτσι το πρόγραμμά σας ώστε να ελαχιστοποιείσετε την επιβάρυνση επικοινωνίας και να πετύχετε καλή απόδοση. Εκτελέστε και ελέξτε το πρόγραμμά σας χρησιμοποιώντας την MESH2 τοπολογία της Multi-Pascal.
3. Απαλοιφή Gauss
Η 2η εργασία προγραμματισμού στο τέλος του κεφαλαίου 6 περιγράφει έναν αλγόριθμο που ονομάζεται Απαλοιφή Gauss και ο οποίος υλοποιεί τα πιο απαιτητικά υπολογιστικά βήματα στην επίλυση ενός συστήματος γραμμικών εξισώσεων. Εδώ πρέπει να γράψετε μια έκδοση της παράλληλης Απαλοιφής Gauss για σύστημα κατανεμημένης μνήμης.
Η κύρια δομή των δεδομένων είναι ένας πίνακας δύο διαστάσεων από πραγματικούς αριθμούς, οι οποίοι είναι οι συντελεστές των όρων των γραμμικών εξισώσεων. Ο σκοπός της Απαλοιφής Gauss είναι η μετατροπή του πίνακα σε άνω τριγωνική μορφή, στην οποία όλα τα στοιχεία που βρίσκονται κάτω από την κύρια διαγώνιο είναι μηδέν. Οι μετατροπές που εφαρμόζονται κατά τη διάρκεια της Απαλοιφής Gauss προκύπτουν από μια σημαντική ιδιότητα κάθε συστήματος γραμμικών εξισώσεων. Αν οι συντελεστές μιας γραμμής πολλαπλασιαστούν με την ίδια σταθερά και προστεθούν σε μια άλλη γραμμή, τότε το σύστημα που προκύπτει έχει την ίδια λύση με το αρχικό. Μετά από μια σειρά τέτοιων μετατροπών ο αλγόριθμος της Απαλοιφής Gauss ο πίνακας καταλήγει να λαμβάνει άνω τριγωνική μορφή, που είναι σχετικά εύκολο να λυθεί με Προς τα Πίσω Αντικατάσταση.
Για να εφαρμοστεί ο αλγόριθμος της Απαλοιφής Gauss σε σύστημα κατανεμημένης μνήμης ο πίνακας πρέπει να επιμεριστεί στους επεξεργαστές. Η μελέτη του αλγορίθμου αποκαλύπτει ότι μπορεί να έχουμε πρόβλημα εξισορρόπησης φορτίου αν ο πίνακας δεν επιμεριστεί σωστά. Αν σε κάθε επεξεργαστή ανατεθεί μια συνεχής ομάδα γραμμών ή στηλών, τότε πολλοί επεξεργαστές ίσως γίνουν αδρανείς καθώς ο αλγόριθμος προχωράει. Η καλύτερη τεχνική επιμερισμού είναι να ανατεθούν σε κάθε επεξεργαστή αρκετές μη-συνεχόμενες τιμές, που χωρίζονται με ίσα διαστήματα στον πίνακα. Αν υπάρχουν p επεξεργαστές τότε οι στήλες από 1 ως p θα ανατεθούν αντίστοιχα στους επεξεργαστές 1 ως p. Μετά οι στήλες από p+1 έως 2p θα ανατεθούν πάλι στους επεξεργαστές από 1 ως p. Αυτό επαναλαμβάνεται σε όλο τον πίνακα, έτσι ώστε κάθε στήλη με αριθμό k να ανατεθεί στον επεξεργαστή k MOD p. Με αυτή τη μέθοδο επιμερισμού κάθε επεξεργαστής θα συνεχίσει νε έχει ενεργές στήλες καθώς ο αλγόριθμος συνεχίζει και η εκτέλεση θα είναι ισορροπημένη.
Η εργασία περιλαμβάνει το γράψιμο της έκδοσης για σύστημα κατανεμημένης μνήμης του αλγόριθμου της Απαλοιφής Gauss και τον έλεγχο του σε μια Πλήρως Συνδεδεμένη τοπολογία τέτοιου συστήματος. Για μεγάλους πίνακες το πρόγραμμά σας πρέπει να επιτυγχάνει καλή επιτάχυνση. Προσέξτε ώστε να αποφύγετε σημεία συμφόρησης. Δώστε διάφορες τιμές την βασική καθυστέρηση επικοινωνίας για να δείτε πώς επιδρά στην απόδοση του προγράμματος.
ΠΡΟΤΕΙΝΟΜΕΝΕΣ ΛΥΣΕΙΣ
1.
Program Anaptyksi_Perioxis;
ARCHITECTURE HYPERCUBE(5);
const n=4;
d=2;
type rowtype=Array [1..n] of integer;
var G,A:array [1..n] of rowtype;
i,s,c:integer;
upchancol,downchancol,upchangr,downchangr:array [1..n] of channel of rowtype;
Graycode:array [1..n] of integer;
inchan:array [0..n-1,1..d] of channel of boolean;
Function Aggregate(mydone:boolean):boolean;
var mynum,partner,bitvalue,stage:integer;
hisdone:boolean;
begin
mynum:=%self;
bitvalue:=1;
for stage:=1 to d do
begin
if mynum DIV bitvalue MOD 2 = 0
then partner:=mynum+bitvalue
else partner:=mynum-bitvalue;
inchan[partner,stage]:=mydone;
hisdone:=inchan[mynum,stage];
mydone:=mydone AND hisdone;
bitvalue:=2*bitvalue;
end;
Aggregate:=mydone;
end;
Procedure Updaterow(me:integer;myrowgr,myrowcol:rowtype;var out:rowtype);
var j,z,change,maxchange:integer;
newrowcol,uprowcol,downrowcol,uprowgr,downrowgr:rowtype;
flagup,flagdown,flagleft,flagright,done,mydone:boolean;
begin
newrowcol:=myrowcol;
if me=1 then
begin
upchangr[me+1]:=myrowgr;
downrowgr:=downchangr[me];
end;
if me=n then
begin
downchangr[me-1]:=myrowgr;
uprowgr:=upchangr[me];
end;
if (me>1) and (me < n) then
begin
upchangr[me+1]:=myrowgr;
downchangr[me-1]:=myrowgr;
uprowgr:=upchangr[me];
downrowgr:=downchangr[me];
end;
repeat
for z:=1 to d*n do
begin
mydone:=false;
maxchange:=0;
if me=1 then
begin
upchancol[me+1]:=newrowcol;
downrowcol:=downchancol[me];
end;
if me=n then
begin
downchancol[me-1]:=newrowcol;
uprowcol:=upchancol[me];
end;
if (me>1) and (me < n) then
begin
upchancol[me+1]:=newrowcol;
downchancol[me-1]:=newrowcol;
uprowcol:=upchancol[me];
downrowcol:=downchancol[me];
end;
for j:=1 to n do
begin
flagup:=true;flagdown:=true;flagright:=true;flagleft:=true;
if me=1 then flagup:=false;
if j=1 then flagleft:=false;
if me=n then flagdown:=false;
if j=n then flagright:=false;
if flagright=true then
if (myrowgr[j]=myrowgr[j+1]) and (newrowcol[j]>newrowcol[j+1]) then
newrowcol[j]:=newrowcol[j+1];
if flagdown=true then
if (myrowgr[j]=downrowgr[j]) and (newrowcol[j]>downrowcol[j]) then
newrowcol[j]:=downrowcol[j];
if flagleft=true then
if (myrowgr[j]=myrowgr[j-1]) and (newrowcol[j]>newrowcol[j-1]) then
newrowcol[j]:=newrowcol[j-1];
if flagup=true then
if (myrowgr[j]=uprowgr[j]) and (newrowcol[j]>uprowcol[j]) then
newrowcol[j]:=uprowcol[j];
change:=ABS(newrowcol[j]-myrowcol[j]);
if change>0 then maxchange:=change;
if maxchange=0 then mydone:=true;
end;
myrowcol:=newrowcol;
end;
done:=Aggregate(mydone);
Until done;
out:=myrowcol;
end;
begin
graycode[1]:=0;
graycode[2]:=1;
graycode[3]:=3;
graycode[4]:=2;
c:=0;
for i:=1 to n do
for s:=1 to n do
begin
c:=c+1;
A[i,s]:=c;
end;
for i:=1 to n do
begin
for s:=1 to n do
G[i,s]:=0;
end;
for s:=1 to n-2 do
begin
G[1,s]=1;
G[2,s+1]:=1;
G[2,1]:=1;
G[3,s]:=1;
end;
writeln;
for i:=1 to n do
begin
for s:=1 to n do
write(A[i,s]);
writeln;
end;
writeln;
for i:=1 to n do
begin
for s:=1 to n do
write(G[i,s]);
writeln;
end;
forall i:=1 to n do
(@Graycode[i] PORT upchangr[i]; downchangr[i]; upchancol[i]; downchancol[i];
inchan[Graycode[i]])
Updaterow(i,G[i],A[i],A[i]);
writeln;
for i:=1 to n do
begin
for s:=1 to n do
write(A[i,s]);
writeln;
end;
end.
2.
Program Red_Black_Jacobi;
Architecture Mesh2(10);
Const
n=10;
p=2;
numiter=3;
type
partition=array[0..p+1,0..p+1] of real;
Var
A,C:array[0..n+1,0..n+1] of partition;
upchan,downchan,leftchan,rightchan:array[1..5,1..5] of partition;
i,j,k,l,st:integer;
Procedure Kokkinh_fash(r,d:integer;Var pin:partition);
Var
step:integer;
begin
step:=d;
while(step<=p)do
begin
pin[r,step]:=(pin[r-1,step]+pin[r+1,step]+pin[r,step-1]+pin[r,step+1])/4;
step:=step+2;
end;
end;
Procedure Mayrh_fash(r,d:integer;Var pin:partition);
Var
step:integer;
begin
step:=d;
while (step<=p) do
begin
pin[r,step]:=(pin[r-1,step]+pin[r+1,step]+pin[r,step-1]+pin[r,step+1])/4;
step:=step+2;
end;
end;
Procedure fash(row,col:integer;in:partition;Var out:partition);
Var
downrow,uprow,leftrow,rightcol:partition;
r,d1,d2,t,z:integer;
above,left:integer;
begin
if row=1 then downrow:=downchan[row,col];
if row=p then uprow:=upchan[row,col];
if col=1 then leftcol:=leftchan[row,col];
if col=p then rightcol:=rightchan[row,col];
if row > 1 then above:=row-1;
if row < n then above:=row+1;
if col > 1 then left:=col-1;
if col < n then left:=col+1;
for r:=1 to p do
begin
for t:=1 to numiter do
begin
ir row>1 then upchan[above,col]:=in;
if row < p then
begin
downchan[above,col]:=in;
uprow:=upchan[row,col];
end;
if row > 1 then downrow:=downchan[row,col];
if col > 1 then leftchan[row,left]:=in;
if col < p then
begin
rightchan[row,left]:=in;
leftcol:=leftchan[row,col];
end;
if col > 1 then rightcol:=rightchan[row,col];
for z:=1 to p do in[0,z]:=uprow[p+1,z];
for z:=0 to p do in[z,0]:=leftcol[p+q,z];
for z:=0 to p do in[p+1,z]:=downrow[1,z];
for z:=0 to p+1 do in[z,p+1]:=rightcol[z,1];
if r mod 2=o then
begin
d1:=2;
d2:=1;
end
else
begin
d1:=1;
d2:=2;
end;
Kokkinh_fash(r,d1,in);
Mayrh_fash(r,d2.in);
end;
end;
out:=in;
end;
begin
st:=n div p;
for i:=1 to st do
for j:=1 to st do
for k:=1 to p do
for l:=1 to p do
readln(a[i,j][k,l]);
for i:=1 to st do
begin
upchan[1,i]:=a[0,i];
leftchan[i,1]:=a[i,0];
end;
for i:=1 to st do
begin
downchan[p,i]:=a[n+1,i];
rightchan[i,p]:=a[i,n+1];
end;
fot i:=1 to st do
for j:=1 to st do
fork(@i*n+j port
upchan[i,j];downchan[i,j];leftchan[i,j];rightchan[i,j])
fash(i,j,a[i,j],c[i,j]);
for i:=1 to st do
for j:=1 to st do
for k:=1 to p do
for l:=1 to p do
writeln(c[i,j][k,l]);
end.
3.
program gauss;
architecture fullconnect(5);
const n=50;p=5;
type pin=array[1..n]of real;
var
i,j:integer;a,tmp:array[1..n]of pin;
chan:array[1..n]of channel of real;
(*****************************************************)
procedure g(me:integer;in:pin;var out:pin);
var j,k:integer;paronom:real;
begin
for j:=1 to me-1 do
begin
paronom:=chan[me];
if paronom=0 then paronom:=1;
for k:=j+1 to n do in[k]:=in[k]-(chan[me]*in[j])/paronom;
end;
for j:=me+1 to n do for k:=me to n do chan[j]:=in[k];
for j:=me+1 to n do in[j]:=0;
out:=in;
end;
(*****************************************************)
begin
(*arxikopihsh*)
for i:=1 to n do
for j:=1 to n do
begin
tmp[i,j]:=1;
if i=j then tmp[i,j]:=n;
end;
(*anastrofh*)
for i:=1 to n do for j:=1 to n do a[i,j]:=tmp[j,i];
(*break*)
forall i:=1 to n do
(@((i-1) mod p) port chan[i]) g(i,a[i],tmp[i]);
(*break*)
(*apotelesmata*)
(*anastrofh*)
for i:=1 to n do for j:=1 to n do a[i,j]:=tmp[j,i];
for i:=1 to n do
begin
writeln;
for j:=1 to n do write(a[i,j]:6:2);
end;
end.
Επόμενο:Aσκήσεις Πάνω: Κεφάλαιο 9o : Επιμερισμός δεδομένων Πίσω: Αναφορές