Επόμενο:Ασκήσεις Πάνω:Κεφάλαιο 2ο: Παραλληλισμός Δεδομένων Πίσω:Αναφορές
ΠΡΟΓΡΑΜΜΑΤΙΣΤΙΚΕΣ ΕΡΓΑΣΙΕΣ
Οι προγραμματιστικές εργασίες του κειμένου μπορούν να πραγματοποιηθούν με το πακέτο λογισμικού της Multi-Pascal που συνοδεύει το κείμενο. Το λογισμικό περιλαμβάνει χαρακτηριστικά που βοηθούν στην αποσφαλμάτωση και τον έλεγχο της απόδοσης των Multi-Pascal προγραμμάτων. Αναλυτικό εγχειρίδιο χρήσεως του λογισμικού υπάρχει στο παράρτημα.
1. Πολλαπλασιασμός Πολυωνύμων
Σε αυτήν την εργασία πρέπει να γράψετε και να εκτελέσετε ένα παράλληλο πρόγραμμα που υπολογίζει το γινόμενο 2 πολυωνύμων. Επιπλέον, θα δημιουργήσετε ένα γράφημα για την απόδοση του προγράμματος σας, που θα απεικονίζει την επιτάχυνση σε συνάρτηση με το μέγεθος των πολυωνύμων. Το παρακάτω είναι ένα παράδειγμα πολυωνύμου:
Πολυώνυμο Α : 6x10 + 4x5 - 8x2+ 2
Γενικά ένα πολυώνυμο αποτελείται από ένα άθροισμα όρων. Κάθε όρος περιλαμβάνει ένα συντελεστή και μια δύναμη του x. Όταν δύο πολυώνυμα Α και Β πολλαπλασιάζονται, κάθε όρος του Α πρέπει να πολλαπλασιασθεί με όλους τους όρους του Β. Όταν δύο όροι πολλαπλασιάζονται, οι συντελεστές τους πολλαπλασιάζονται ενώ οι δυνάμεις τους προστίθενται. Μελετείστε το παρακάτω παράδειγμα πολλαπλασιασμού 2 όρων:
6x10*10x8 = 60x18
Το παρακάτω είναι ένα παράδειγμα ενός άλλου πολυωνύμου:
Πολυώνυμο Β: 10x8 + 3x3
Από τον πολλαπλασιασμό του πολυωνύμου Β με το πολυώνυμο Α θα προκύψει ένα νέο πολυώνυμο με 8 όρους:
60x18 + 18x13 + 40x13 + 12x8 - 80x10 + 32x8 - 24x5 + 6x3
Για να έρθει το νέο πολυώνυμο στη τελική του μορφή, οι όροι πρέπει να ταξινομηθούν σε φθίνουσα σειρά με βάση τις δυνάμεις και οι όροι με την ίδια δύναμη να συνδυασθούν, προσθέτοντας τους συντελεστές τους. Το παρακάτω είναι το τελικό αποτέλεσμα:
60x18 + 58x13 - 80x10 + 32x8 - 24x5 + 6x3
Σε ένα πρόγραμμα, κάθε πολυώνυμο μπορεί να απεικονισθεί με μια απλή δομή δεδομένων. Κάθε όρος μπορεί να απεικονισθεί με μια εγγραφή που αποτελείται από 2 πεδία: το πρώτο αποθηκεύει το συντελεστή και το δεύτερο τη δύναμη. Επομένως ένα πολυώνυμο μπορεί να αποθηκευθεί σε ένα πίνακα που περιέχει τέτοιες εγγραφές. Το πρόγραμμα σας, πρέπει να έχει τις παρακάτω φάσεις:
1. Αρχικοποίηση των 2 πολυωνύμων.
2. Πολλαπλασιασμό των όρων των πολυωνύμων ώστε να σχηματισθεί το νέο πολυώνυμο που θα αποθηκευθεί σε ένα νέο πίνακα.
3. Ταξινόμηση του νέου πολυωνύμου ως προς τις δυνάμεις των όρων, κάνοντας χρήση της παράλληλης ταξινόμησης σειράς.
4. Σάρωση του πολυωνύμου σειριακά και πρόσθεση των όρων που έχουν την ίδια δύναμη.
Τα στάδια 2 και 3 του προγράμματος μπορούν να παραλληλισθούν σε μεγάλο βαθμό και επομένως να παράγουν μια εξαιρετική επιτάχυνση για πολυώνυμα με πολλούς όρους. Ο στόχος της εργασίας είναι η ελαχιστοποίηση του χρόνου εκτέλεσης του προγράμματος και μεγιστοποίηση της επιτάχυνσης. Εκτελέστε και ελέγξετε το πρόγραμμα, χρησιμοποιώντας το διαλογικό σύστημα της Multi-Pascal. Μετά που αποσφαλματώσετε το πρόγραμμα, εκτελέστε το για μια σειρά από πολυώνυμα διαφορετικού μήκους και παρατηρείστε την αυξανόμενη επιτάχυνση για πολυώνυμα με περισσότερους όρους. Σχεδιάστε ένα γράφημα που να απεικονίζει την επιτάχυνση σε σχέση με το μήκος των πολυωνύμων. Εξηγείστε γιατί το γράφημα έχει αυτή τη μορφή. ( είναι χρήσιμο να αγνοήσετε τη φάση της αρχικοποίησης του προγράμματος, κατά τον υπολογισμό της επιτάχυνσης, κάνοντας χρήση των τεχνικών που περιγράφονται στο παράρτημα ).
2. Συγχωνεύοντας ταξινομημένες λίστες.
Σε αυτή την προγραμματιστική εργασία θα γράψετε και θα εκτελέσετε ένα παράλληλο πρόγραμμα για να συγχωνεύσετε 2 ταξινομημένες λίστες σε μια απλή ταξινομημένη λίστα. Σκοπός σας είναι να φτιάξετε ένα όσο το δυνατό πιο αποδοτικό πρόγραμμα ελαχιστοποιώντας τον παράλληλο χρόνο εκτέλεσης και μεγιστοποιώντας την επιτάχυνση.
Με μια πρώτη ματιά, μπορεί να φαίνεται ότι η συγχώνευση ταξινομημένων λιστών είναι μια ενέργεια που απαιτεί σειριακή επεξεργασία και έχει μικρή πιθανότητα να παραλληλιστεί. Όμως υπάρχει μια έξυπνη παράλληλη τεχνική που παράγει πολύ μεγάλες επιταχύνσεις γι’ αυτό το πρόγραμμα. Υποθέστε ότι οι δύο ταξινομημένες λίστες είναι αρχικά αποθηκευμένες στους πίνακες X και Y και η τελική συγχωνευμένη λίστα θα αποθηκευτεί στον πίνακα Ζ. Ο παράλληλος αλγόριθμος βασίζεται στην παρακάτω απλή παρατήρηση σε σχέση με κάθε μονάδα δεδομένων X[i] της πρώτης ταξινομημένης λίστας:
Θεώρησε ότι συγχωνεύουμε αμέσως το στοιχείο X[i] στην τελική ταξινομημένη του θέση στην δεύτερη λίστα Y. Έστω Y[j] η τελική αυτή θέση. Τότε η τελική θέση του X[i] στην τελική συγχωνευμένη λίστα πρέπει να είναι Z[i+j-1].
Η παραπάνω παρατήρηση επιβεβαιώνεται εύκολα. Τα πρώτα i-1 στοιχεία της λίστας X είναι μικρότερα από το X[i] και επομένως πρέπει να παρουσιάζονται πριν από το X[i] στην τελική ταξινομημένη λίστα Z. Επίσης τα πρώτα j-1 στοιχεία της λίστας Y είναι μικρότερα από το X[i] και επομένως πρέπει να εμφανιστούν επίσης πριν από το X[i] της Ζ. Έτσι υπάρχουν ακριβώς i-1+j-1 στοιχεία τα οποία πρέπει να εμφανιστούν πριν από το X[i] στην τελική ταξινομημένη λίστα Ζ. Αυτό μας δίνει την Σειρά του X[i] σαν i+j-1. Επομένως, το X[i] πρέπει να τοποθετηθεί στην θέση Z[i+j-1]. Αυτή η απλή παρατήρηση οδηγεί σε ένα αλγόριθμο με υψηλή παραλληλία για την συγχώνευση των δύο ταξινομημένων λιστών. Για κάθε στοιχείο X[i] σαρώστε την λίστα Y, για να το τοποθετήσετε στην κατάλληλη θέση j. Αυτό μπορεί να γίνει πιο αποδοτικά με δυαδική αναζήτηση στην λίστα Υ. Στη συνέχεια απλά αντιγράψτε το X[i] στην θέση Z[i+j-1]. Φυσικά το ίδιο ακριβώς μπορεί να γίνει για κάθε στοιχείο Υ[k]: εκτελέστε δυαδική αναζήτηση στην λίστα Χ, για να βρείτε την κατάλληλη θέση m και μετά αντιγράψτε το Y[k] στην θέση Z[k+m-1].
H παραπάνω συζήτηση αγνοεί το πρόβλημα επανάληψης ενός στοιχείου στις δύο λίστες. Αυτό μπορεί εύκολα να λυθεί με την δημιουργία μιας μικρής ασυμμετρίας στον χειρισμό των δύο λιστών. Όταν γίνεται η δυαδική αναζήτηση στην λίστα Υ για να βρεθεί η θέση του X[i], κάθε στοιχείο της Υ που είναι ίσο με το X[i] λειτουργεί σαν να ήταν μεγαλύτερο του X[i]. Όμως η δυαδική αναζήτηση στη λίστα Χ για το στοιχείο Y[k], χειρίζεται τα ίσα δεδομένα της λίστας Χ σαν να ήταν μικρότερα του Y[k]. Αυτή η ασυμμετρία θα εμποδίζει τα δεδομένα με τις ίδιες τιμές και από τις δύο λίστες να συγκρουστούν στην ίδια θέση της συγχωνευμένης λίστας Ζ.
Βασιζόμενοι στην παραπάνω συζήτηση, γράψτε ένα πρόγραμμα υψηλού παραλληλισμού για να συγχωνεύσετε δύο οποιεσδήποτε ταξινομημένες λίστες. Προσπαθήστε να βελτιστοποιήσετε την απόδοση του προγράμματος, να ελαχιστοποιήσετε τον χρόνο εκτέλεσης και να μεγιστοποιήσετε την επιτάχυνση. Παρατηρήστε πως η επιτάχυνση και η διαχείριση του επεξεργαστή αλλάζει, καθώς το μέγεθος της λίστας αυξάνει. Για τον προσδιορισμό της επιτάχυνσης, αγνοήστε την σειριακή αρχικοποίηση του κώδικα χρησιμοποιώντας την τεχνική που περιγράφετε στο παράρτημα.
ΠΡΟΤΕΙΝΟΜΕΝΕΣ ΛΥΣΕΙΣ
1.
program polywnyma;
Var
m,n,i,j,tmp: integer;
oros: array[1..2,1..10]of record
syn,ek: integer;
end;
apot, temp: array[1..100]of record
syn,ek:integer;
end;
Διεργασία ταξινόμησης όρων.
procedure putinrank(index : integer);
var
toput, rank, j : integer;
begin
j := index;
rank := 0;
repeat
j :=(j mod tmp)+1 ;
if apot[index].ek > apot[j].ek then αν ο εκθέτης είναι μεγαλύτερος
rank:= rank + 1 η θέση του στον temp αυξάνεται κατά 1
else
if apot[index].ek = apot[j].ek then αν ο εκθέτης είναι ίσος η θέση του
if index >= j then αυξάνεται μόνο αν η θέση του στο apot
rank := rank + 1; είναι μεγαλύτερη(ή μικρότερη) ίση
until j = index;
temp[rank]:= apot[index];
end;
Begin
for i:=1 to 100 do Αρχικοποίηση
begin
apot[i].ek:=-1;
temp[i].ek:=-1;
end;
write('oroi 1ou polyonymou:');
readln(m);
write('oroi 2ou polyonymou:');
readln(n);
tmp:=m*n;
for i:=1 to m do
begin
writeln('1o polyonymo oros:',i);
write('syntelesths:');
readln(oros[1,i].syn);
write('ek0eths:');
readln(oros[1,i].ek);
end;
for i:=1 to n do
begi
writeln('2o polyonymo oros:',i);
write('syntelesths:');
readln(oros[2,i].syn);
write('ek0eths:');
readln(oros[2,i].ek);
end;
forall i:=1 to m do γινόμενο όρων
forall j:=1 to n do
begin
apot[n*(i-1)+j].syn:=oros[1,i].syn*oros[2,j].syn;
apot[n*(i-1)+j].ek:=oros[1,i].ek+oros[2,j].ek;
end;
forall i := 1 to tmp do
putinrank(i);
i:=1; πρόσθεση ομοίων όρων
j:=1;
repeat
apot[i]:=temp[j];
while temp[j].ek=temp[j+1].ek do
begin
j:=j+1;
apot[i].syn:=apot[i].syn+temp[j].syn;
end;
i:=i+1; θέση στον apot
j:=j+1; θέση στον temp
until temp[j].ek=-1;
writeln; Εμφάνιση αποτελεσμάτων
for j := 1 to i-1 do
writeln('oros',j,'synt:',apot[j].syn,' ek:',apot[j].ek);
End.
Επόμενο:Ασκήσεις Πάνω:Κεφάλαιο 2ο: Παραλληλισμός Δεδομένων Πίσω:Αναφορές