Επόμενο: Ασκήσεις Πάνω: Κεφάλαιο 5ο : Μοίρασμα Δεδομένων Πίσω: Αναφορές
ΠΡΟΓΡΑΜΜΑΤΙΣΤΙΚΕΣ ΕΡΓΑΣΙΕΣ
1. Το στοιχείο καμπής ενός πίνακα
Το στοιχείο καμπής ενός πίνακα δυο διαστάσεων είναι εκείνο το στοιχείο που είναι το μεγαλύτερο στη σειρά του και το μικρότερο στη στήλη του. Στην εργασία αυτή πρέπει να γραφεί ένα πρόγραμμα που να διαβάζει έναν πίνακα δύο διαστάσεων, να βρίσκει το στοιχείο καμπής και να γράφει τη θέση στην οποία αυτό βρίσκεται. Αν στον πίνακα δεν υπάρχει στοιχείο καμπής τότε πρέπει να εμφανίζεται το ανάλογο μήνυμα από το πρόγραμμα.
Για μεγάλους πίνακες υπάρχει η δυνατότητα εφαρμογής παραλληλισμού στο πρόγραμμα. Για ένα δεδομένο μέγεθος πίνακα προσπαθήστε να αυξήσετε την ταχύτητα εκτέλεσης του προγράμματος. Εκτελέστε και ελέγξτε το πρόγραμμα χρησιμοποιώντας το σύστημα της Multi-Pascal..
2. Ταξινόμηση του δοχείου (Bucket sorting)
Οι βασικές αρχές πίσω από την ταξινόμηση του δοχείου γίνονται καλύτερα κατανοητές μέσα από ένα παράδειγμα. Ας θεωρήσουμε μια λίστα ονομάτων που πρέπει να ταξινομηθούν. Ένα δοχείο αντιστοιχεί και σε κάθε γράμμα της αλφαβήτου. Το πρώτο γράμμα κάθε ονόματος στη λίστα χρησιμοποιείται για την διανομή όλων των ονομάτων στα δοχεία. Το δοχείο “Α” περιλαμβάνει όλα τα ονόματα που αρχίζουν από “Α”, το “Β” όλα τα ονόματα που αρχίζουν από “Β” και ούτω καθεξής. Στη συνέχεια κάθε δοχείο ταξινομείται εσωτερικά και στο τέλος τα ονόματα από τα δοχεία συνενώνονται για να δημιουργήσουν την ταξινομημένη πλέον λίστα. Το “Α” δοχείο πηγαίνει πρώτο, ακολουθεί το “Β” κ.τ.λ.
Υπάρχει φανερά μια πολύ καλή δυνατότητα παραλληλισμού όσον αφορά την ταξινόμηση του δοχείου. Το βήμα στο οποίο τα ονόματα διανέμονται σε κάθε δοχείο μπορεί να αναπτυχθεί παράλληλα αναθέτοντας σε κάποιες διεργασίες διαφορετικά τμήματα της αρχικής λίστας. Κατόπιν, η ταξινόμηση κάθε δοχείου ξεχωριστά μπορεί να γίνει παράλληλα. Παράλληλα επίσης μπορεί να πραγματοποιηθεί και η συνένωση όλων των δοχείων σε μια λίστα, έχοντας διαφορετικές διεργασίες να αντιγράψουν τα δοχεία στην τελική ταξινομημένη λίστα.
Η εκτέλεση και της παράλληλης και της ακολουθιακής έκδοσης της ταξινόμησης δοχείου εξαρτάται από την ομαλότητα της φάσης διανομής. Αν υπάρχει μεγάλος αριθμός δοχείων και καθένα λαμβάνει έναν ακριβώς ίδιο αριθμό αντικειμένων - στο παράδειγμά μας λέξεις - τότε μπορεί να επιτευχθεί μια αρκετά καλή απόδοση του προγράμματος. Όμως, αν τα περισσότερα αντικείμενα πηγαίνουν σε λίγα δοχεία τότε το βήμα ταξινόμησης θα έχει ένα μη-ισορροπημένο φορτίο ανά επεξεργαστή και συνεπώς θα μειωθεί η απόδοση.
Η εργασία αυτή αφορά τη σύνταξη και τον έλεγχο ενός προγράμματος σε Multi-Pascal που να αναπτύσσει την παράλληλη ταξινόμηση δοχείου. Για ευκολία χρησιμοποιήστε για την ταξινόμηση έναν πίνακα με ακέραιες τιμές. Υποθέστε ότι το πρόγραμμα γνωρίζει εκ των προτέρων το πλήθος των αριθμητικών τιμών του πίνακα και το πλήθος αυτό διαιρείται ακριβώς με τον αριθμό των δοχείων, έτσι ώστε να γνωρίζουμε το μέγεθος κάθε δοχείου. Το κατάλληλο δοχείο για κάθε τιμή μπορεί να προσδιοριστεί με μια απλή πράξη διαίρεσης.
Ένα πολύ σημαντικό στοιχείο του προγράμματος είναι η χρήση κάθε δοχείου παράλληλα από πολλές διεργασίες κατά τη φάση της διανομής. Θα πρέπει να αντιμετωπίσετε το πρόβλημα του αποκλεισμού και του ανταγωνισμού. Το άλλο ενδιαφέρον στοιχείο είναι η επίτευξη του παραλληλισμού κατά την τελευταία φάση της συνένωσης. Κάθε διεργασία πρέπει εκ των προτέρων να γνωρίζει που θα τοποθετήσει τις τιμές της στην ταξινομημένη λίστα. Για να μπορεί να το γνωρίζει αυτό κάθε διεργασία πρέπει οι διεργασίες να αναπτύξουν ένα βήμα επικοινωνίας πριν τη φάση της συνένωσης. Κατά τη διάρκεια αυτού του βήματος κάθε διεργασία παίρνει από τις υπόλοιπες τις πληροφορίες που θέλει σχετικά με το που να γράψει τις τιμές της στον τελικό πίνακα. Το σημείο έναρξης στον τελικό ταξινομημένο πίνακα για κάθε διεργασία είναι το άθροισμα του μεγέθους των δοχείων από όλες τις προηγούμενες διεργασίες.
ΠΡΟΤΕΙΝΟΜΕΝΕΣ ΛΥΣΕΙΣ
1.
Program SimioKambis;
const n=4;
var A:array [1..n,1..n] of integer;
mark:array [1..n,1..n] of boolean;
L:array [1..n] of spinlock;
flag,i,k:integer;
Procedure process(i:integer);
var t,s,d,thesi,thesi2,simio:integer;
flag1,flag2:boolean;
begin
d:=-999;
flag1:=false;flag2:=false;
for s:=1 to n do
mark[i,s]:=false;
for s:=1 to n do
begin
if a[i,s]>=d then
begin
if a[i,s]=d then flag1:=true;
d:=a[i,s];
thesi:=s;
end;
end;
if flag1=false then
begin
Lock(L[thesi]);
simio:=a[i,thesi];
for t:=1 to n do
begin
if a[t,thesi]<=simio then
begin
if (a[t,thesi]=simio) and (a[t,thesi]<>a[i,thesi]) then flag2:=true;
if a[t,thesi]<simio then flag2:=true;
end;
end;
if flag2=false then mark[i,thesi]:=true;
Unlock(L[thesi]);
end;
end;
begin
flag:=0;
A[1,1]:=3;
A[1,2]:=7;
A[1,3]:=8;
A[1,4]:=10;
A[2,1]:=4;
A[2,2]:=5;
A[2,3]:=1;
A[2,4]:=4;
A[3,1]:=9;
A[3,2]:=6;
A[3,3]:=2;
A[3,4]:=17;
A[4,1]:=1;
A[4,2]:=6;
A[4,3]:=5;
A[4,4]:=20;
writeln('O pinakas einai');
for i:=1 to n do
begin
for k:=1 to n do
write(A[i,k]);
writeln;
end;
forall i:=1 to n do
process(i);
for i:=1 to n do
for k:=1 to n do
begin
if mark[i,k]=true then
begin
writeln('Σημείο καμπής:',i,',',k,'-',A[I,K]);
flag:=1;
end;
end;
if flag=1 then writeln('Βρέθηκαν σημεία καμπής στα πιο πάνω σημεία');
if flag=0 then writeln('Δεν βρέθηκαν σημεία καμπής');
end.
2.
program bucket;
Const
n=30;
bs=150;
bn=10;
Type
pin=array[1..n]of integer;
pin1=array[1..bs]of integer;
buckets=array[1..bn]of pin1;
Var
big,res:pin;
others:buckets;
k:array[1..bn]of integer;
m,i:integer;
procedure ranksort(var tosort:pin1;count:integer);
var
unsorted,sorted :pin1; i : integer;
(*--*)procedure putinrank(index : integer);
var
toput, rank, j : integer;
begin
j := index;
rank := 0;
repeat
j := (j mod count)+1 ;
if unsorted[index] >unsorted[j] then αν ο αριθμός είναι μεγαλύτερος
rank := rank + 1 η θέση του στον sorted αυξάνεται κατα 1
else
if unsorted[index] = unsorted[j] then αν ο αριθμός είναι ίσος η θέσηaii aneeiuo a?iae ?oio
if index >= j then αυξάνεται μόνο αν η θέση του στον unsorted
rank := rank + 1; είναι μεγαλύτερη(ή μικρότερη) ίση
until j = index;
sorted[rank] := unsorted[index];
(*----*)end;
begin
forall i:=1 to count do
unsorted[i]:=tosort[i];
forall i:=1 to count do
putinrank(i);
forall i:=1 to count do
tosort[i]:=sorted[i];
end;
procedure tobuckets(a:pin;var b:buckets);
var
j:integer;bl:spinlock;
begin
forall j:=1 to n do
var tmp:integer;
begin
tmp:=(a[j] div 100)+1; υπολογίζει σε ποιο δοχείο ανήκει ο αριθμός
lock(bl);
k[tmp]:=k[tmp]+1; ο μετρητής του πλήθους των αριθμών στο δοχείο
unlock(bl);
b[tmp,k[tmp]]:=a[j]; τοποθέτηση του αριθμού στο δοχείο
end;
end;
procedure frombuc(var a:pin;b:buckets);
var
tmp,j:integer;
tar:array[1..bn]of integer;
begin
tmp:=0;
for j:=1 to bn do
begin
tar[j]:=tmp; i tar[j] κρατάει τη θέση από την οποία ξεκινά το bucket j*)
tmp:=tmp+k[j];
end;
forall j:=1 to bn do
var tmp,h:integer;
begin
tmp:=0;
for h:=tar[j]+1 to tar[j]+k[j] do
begin
tmp:=tmp+1;
a[h]:=b[j,tmp]; τοποθέτηση του αριθμού πίσω στον πίνακα
end;
end;
end;
Begin
for i:=1 to n do Αρχικοποίηση
readln(big[i]);
for i:=1 to bn do
k[i]:=0;
tobuckets(big,others);
forall i:=1 to bn do
ranksort(others[i],k[i]);
frombuc(res,others);
for i:=1 to n do Εμφάνιση αποτελεσμάτων
begin
m:=m+1;
if m>10 then
begin
m:=0;
writeln;
end;
write(res[i]:5);
end;
End.
Επόμενο: Ασκήσεις Πάνω: Κεφάλαιο 5ο : Μοίρασμα Δεδομένων Πίσω: Αναφορές