Δραστηριότητα 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
Η εντολή S1 χρησιμοποιεί την τιμή που καθορίστηκε στην προηγούμενη επανάληψη από τη εντολή S2 και άρα υπάρχει μια εξάρτηση που μεταφέρεται με τον βρόχο. Σε αντιδιαστολή με το βρόχο του προηγούμενου παραδείγματος, αυτή η εξάρτηση δεν είναι κυκλική γιατί καμία εντολή δεν εξαρτάται από τον εαυτό της και ενώ η S1 εξαρτάται από την S2, η S2 δεν εξαρτάται από την S1. Ο βρόχος μπορεί να γίνει παράλληλος, εκτός αν υπάρχει κύκλος εξαρτήσεων. Η απουσία κύκλου σημαίνει ότι οι εξαρτήσεις προϋποθέτουν ένα μερικό καθορισμό σειράς εκτέλεσης των εντολών.
Αν και δεν υπάρχουν κυκλικές εξαρτήσεις στον παραπάνω βρόχο, πρέπει να μετατραπεί έτσι ώστε να είναι προσαρμοσμένος σε μια μερική διάταξη των εντολών και να εμφανίζεται η παραλληλία.
Δύο παρατηρήσεις είναι σημαντικές για την υλοποίηση αυτής της μετατροπής :
1. Η S2 δεν εξαρτάται από την S1 οπότε η εναλλαγή των δύο εντολών δεν θα έχει επίδραση στην εκτέλεση της S2. Αν είχε εξάρτηση, τότε θα είχαμε κυκλική εξάρτηση και ο βρόχος δεν θα ήταν παράλληλος.
2. Κατά τη διάρκεια της πρώτης επανάληψης του βρόχου, η εντολή S1 εξαρτάται από την αρχική τιμή που δόθηκε στον B[1].
Αυτές οι δύο παρατηρήσεις μας επιτρέπουν να αντικαταστήσουμε τον παραπάνω βρόχο με το επόμενο τμήμα κώδικα :
A[1] = A[1] + B[1];
for (i=1; i<=99; i =i+1) {
B[i+1] = C[i] + D[i];
A[i+1] = A[i+1] + B[i+1];
}
B[101] = C[100] + D[100];
Η εξάρτηση μεταξύ των δύο εντολών δεν είναι εξάρτηση που μεταφέρεται με τον βρόχο, οπότε οι επαναλήψεις του βρόχου μπορούν να επικαλυφθούν, με την προϋπόθεση όμως, ότι οι εντολές σε κάθε επανάληψη διατηρούν την κατάλληλη σειρά.
