Κεφάλαιο 2 | Ενότητα3 | Ερωτήσεις επισκόπησης | Επόμενο| Προηγούμενο | Λεξικό όρων

Αρχές και τεχνικές της παραλληλίας σε επίπεδο βρόχου

   Η ανάλυση σε επίπεδο βρόχου καθορίζει τις εξαρτήσεις μεταξύ των εντολών του κυρίου μέρους του βρόχου και όλων των επαναλήψεων του. Επίσης καθορίζει κατά πόσο τα δεδομένα των μεταγενέστερων επαναλήψεων έχουν εξάρτηση δεδομένων με τα δεδομένα που παράχθηκαν από τις αρχικές επαναλήψεις. Θα ασχοληθούμε μόνο με τις εξαρτήσεις δεδομένων, ενώ οι εξαρτήσεις ονομάτων που υπάρχουν θα αντιμετωπιστούν με τη μέθοδο της μετονομασίας. Οι υπολογισμοί σε κάθε επανάληψη είναι ανεξάρτητοι των προηγούμενων επαναλήψεων.

Παράδειγμα

Έστω το παρακάτω τμήμα κώδικα

for (i=1; i 1000; i++)
x[i]=x[i]+s;

Απάντηση:
Στο σώμα του βρόχου υπάρχει εξάρτηση μεταξύ της παλιάς και νέας τιμής του x[i], η οποία βρίσκεται, κάθε φορά, μέσα σε μία επανάληψη. Αντιθέτως δεν υπάρχει εξάρτηση μεταξύ εντολών διαφορετικών επαναλήψεων. Επομένως ο βρόχος είναι παράλληλος. Υπενθυμίζουμε ότι για να μειωθούν οι εξαρτήσεις, μετατρέπουμε τον πηγαίο κώδικα σε γλώσσα assembly:

Στον κώδικα, μετά την ανάπτυξη, δημιουργείται εξάρτηση μεταξύ των επαναλήψεων λόγω του καταχωρητή R1.

ΔΡΑΣΤΗΡΙΟΤΗΤΑ 4

 · Να εκτελέσετε των κώδικα του παραδείγματος χρησιμοποιώντας το λογισμικό προσομοίωσης του DLX, Windlx, το οποίο παρατίθεται στις ιστοσελίδες:

http://www.gup.uni-linz.ac.at/downloads/ti3/windlx
http://www.mkp.com/pub/dlx

· Να συγκρίνετε την απάντηση του παραδείγματος με τα αποτελέσματα από τη χρήση του λογισμικού προσομοίωσης Windlx.

· Για περισσότερες λεπτομέρειες καλό θα ήταν να συμβουλευόσασταν το παράρτημα Α: «Εργαλεία Προσομοίωσης του DLX».


Παράδειγμα

θεωρούμε το βρόχο:

Υποθέτουμε ότι οι πίνακες A, B και C είναι διαφορετικοί χωρίς επικαλύψεις. Ποιες είναι οι εξαρτήσεις δεδομένων μεταξύ των εντολών S1 και S2 στο βρόχο;

Απάντηση:
Υπάρχουν δύο διαφορετικές εξαρτήσεις :

  • Η S1 χρησιμοποιεί την τιμή που υπολογίστηκε από την S1 σε προηγούμενη επανάληψη , αφού η επανάληψη i υπολογίζει το A[i+1] το οποίο διαβάζεται στην i+1 επανάληψη. Το ίδιο συμβαίνει και με την S2 για τα B[i] και B[i+1].

  • Η S2 χρησιμοποιεί την τιμή A[i+1] που υπολογίστηκε από την S1 στην ίδια επανάληψη.

Θα εξετάσουμε κάθε περίπτωση χωριστά, αγνοώντας κάθε φορά την ύπαρξη της άλλης.
Η πρώτη περίπτωση εξάρτησης, όπου η εντολή S1 (ή S2) εξαρτάται από την εντολή S1 (ή S2) της αμέσως προηγούμενης επανάληψης, ονομάζεται εξάρτηση που μεταφέρεται με τον βρόχο. Η εξάρτηση αυτή, παρουσιάζεται μεταξύ δύο διαδοχικών επαναλήψεων του βρόχου. Επειδή η εντολή S1 εξαρτάται από τον εαυτό της, πρέπει οι επαναλήψεις της εντολής S1 να εκτελούνται με τη σειρά προκειμένου να είναι επιτυχείς. Το ίδιο ισχύει και για την S2.
Η δεύτερη περίπτωση εξάρτησης, όπου η S2 εξαρτάται από την S1, βρίσκεται μέσα σε κάθε επανάληψη, δηλαδή στο εσωτερικό του βρόχου και άρα δεν είναι εξάρτηση που μεταφέρεται με τον βρόχο. Συνεπώς, πολλαπλές επαναλήψεις του βρόχου εκτελούνται παράλληλα, εφόσον διατηρούμε τη σειρά για κάθε ζευγάρι εντολών σε κάθε επανάληψη.

ΔΡΑΣΤΗΡΙΟΤΗΤΑ 5

 Έστω το παρακάτω τμήμα κώδικα.

for (i=1; i<=100; i = i+1)
     {
     A[i] = A[i] + B[i]; /* S1 */
     B[i+1] = C[i] + D[i]; /* S2 */
      }
· Μπορείτε να εντοπίστε τις εξαρτήσεις δεδομένων μεταξύ των εντολών S1 και S2;
· Θεωρείτε πως είναι ο βρόχος αυτός παράλληλος; Αν θεωρείτε πως δεν είναι, να δείξετε τον τρόπο με τον οποίο θα γίνει παράλληλος.

 

ΑΠΑΝΤΗΣΗ ΔΡΑΣΤΗΡΙΟΤΗΤΑΣ 5



ΔΡΑΣΤΗΡΙΟΤΗΤΑ 6

 Έστω ότι έχουμε δύο αρχεία: το second1.s και το second2.s, τα οποία περιέχουν τα αντίστοιχα προγράμματα:

Ο κώδικας του second1.sΟ κώδικας του second2.s
.data
.word 4,4
.text
main: LW r1,$DATA(r0)
        LW r2,$DATA +4(r0)
        SUB r3,r1,#2
        BNEZ r3,L1
        ADD r1,r0,r0
L1:   SUB r3,r2,#2
        BNEZ r3,L2
        ADD r1,r0,r0
L2:   SUB r3,r1,r2
.data
.word 4,4
.text
main: LW r1,$DATA(r0)
        LW r2,$DATA +4(r0)
        SUB r3,r1,#4
        BNEZ r3,L1
        ADD r1,r0,r0
L1:   SUB r3,r2,#4
        BNEZ r3,L2
        ADD r2,r0,r0
L2:   SUB r3,r1,r2


· Να προσδιορίσετε τους κινδύνους που προκύπτουν κατά την εκτέλεση των προγραμμάτων και να προτείνετε τρόπους αντιμετώπισης των κινδύνων.
· Να εκτελέσετε τα προγράμματα χρησιμοποιώντας το λογισμικό προσομοίωσης του DLX, Windlx, το οποίο παρατίθεται στην ιστοσελίδα:
· Να εκτελέσετε των κώδικα του παραδείγματος χρησιμοποιώντας το λογισμικό προσομοίωσης του DLX, Windlx, το οποίο παρατίθεται στην ιστοσελίδα:
http://www.gup.uni-linz.ac.at/downloads/ti3/windlx
· Να συγκρίνετε την απάντηση που δώσατε με τα αποτελέσματα από την εκτέλεση των προγραμμάτων από τον προσομοιωτή Windlx.
· Για περισσότερες λεπτομέρειες καλό θα ήταν να συμβουλευτείτε το παράρτημα Α: «Εργαλεία Προσομοίωσης του DLX».

 

ΑΠΑΝΤΗΣΗ ΔΡΑΣΤΗΡΙΟΤΗΤΑΣ 6