2.3 Φωλιασμένοι Βρόχοι

Επόμενο:2.4 Παράδειγμα : Πολλαπλασιασμός μητρών Πάνω:Κεφάλαιο 2ο: Παραλληλισμός Δεδομένων Πίσω:2.2 Παράδειγμα : Παράλληλη Ταξινόμηση

2.3 Φωλιασμένοι Βρόχοι

Οι εντολές FORALL μπορούν να χρησιμοποιηθούν σε φωλιασμένους βρόχους προκειμένου να επιτευχθεί μεγαλύτερος παραλληλισμός. Για παράδειγμα, το παρακάτω τμήμα προγράμματος προσθέτει δύο πολυδιάστατους πίνακες:

PROGRAM SumArrays1;
 VAR i,j: integer;
		A, B, C: ARRAY [1..20, 1..30] OF REAL;
  BEGIN
   ... 

  FORALL i := 1 TO 20 DO
		FORALL j := 1 TO 30 DO
			C[i, j] := A[i,j]+B[i,j];
			...

  END.

Σε αυτό το παράδειγμα δημιουργούνται 600 διεργασίες: μια για κάθε στοιχείο του διδιάστατου πίνακα. Κάθε μια από τις διεργασίες έχει την δική της κατάλληλη τιμή για τους μετρητές i και j. H εξωτερική FORALL μεταβάλλει τον μετρητή i από 1 σε 20 και η εσωτερική FORALL μεταβάλλει την τιμή του μετρητή j από 1 σε 30. Το φώλιασμα αυτών των εντολών έχει το ίδιο συνολικά αποτέλεσμα με τους συνηθισμένους σειριακούς βρόχους FOR: παράγονται όλοι οι δυνατοί συνδυασμοί των δύο μετρητών. Εφόσον υπάρχουν 20 διαφορετικές τιμές για το i και 30 διαφορετικές τιμές για το j θα παραχθούν συνολικά 20*30=600 συνδυασμοί. Ο κάθε συνδυασμός θα έχει την δική του μοναδική διεργασία παιδί η οποία θα εκχωρείται σε ένα φυσικό επεξεργαστή για εκτέλεση.

Η δυναμική των φωλιασμένων FORALL εντολών είναι τέτοια που πραγματικά δημιουργεί δύο γενιές από διεργασίες παιδιά. Στην εξωτερική FORALL ο μετρητής i μεταβάλλεται από 1 σε 20. Έτσι δημιουργούνται 20 διεργασίες παιδιά, μια για κάθε τιμή του i. Κάθε μια από αυτές τις διεργασίες παιδιά θα αποτελείται από ένα στιγμιότυπο του εσωτερικού βρόχου FORALL με την κατάλληλη τιμή του i. Όταν η κάθε μια από αυτές τις διεργασίες παιδιά της πρώτης γενιάς εκτελούνται στον φυσικό επεξεργαστή που τους έχει εκχωρηθεί, θα δημιουργεί 30 ακόμα διεργασίες- μια για κάθε τιμή του μετρητή j. Έτσι συνολικά 600 διεργασίες δημιουργούνται στην δεύτερη γενιά. Η διεργασία γονέας θα έχει έτσι 20 παιδιά και 600 εγγόνια.

Η δημιουργία διεργασιών με πολλαπλά στάδια μειώνει τον συνολικό χρόνο δημιουργίας της διεργασίας επειδή οι διεργασίες παιδιά της πρώτης γενιάς εκτελούνται όλες παράλληλα σε διαφορετικούς φυσικούς επεξεργαστές. Αντί ένας μόνο φυσικός επεξεργαστής να δημιουργεί όλες τις διεργασίες, θα υπάρχουν 20 φυσικοί επεξεργαστές που θα δημιουργούν τις διεργασίες παιδιά παράλληλα. Ας θεωρήσουμε την γενική περίπτωση των δύο φωλιασμένων FORALL βρόχων, όπου η ο μετρητής στον εξωτερικό βρόχο έχει n τιμές και στον εσωτερικό m τιμές. Αν ο χρόνος για την δημιουργία μιας απλής διεργασίας είναι C, τότε ο συνολικός χρόνος δημιουργίας των nm διεργασιών είναι C(n+m). Αν όλες αυτές οι διεργασίες είχαν δημιουργηθεί από την διεργασία γονέα, τότε ο συνολικός χρόνος δημιουργίας θα ήταν Cnm, που είναι πολύ μεγαλύτερος.

Σε αυτό το παράδειγμα, οι διεργασίες παιδιά αποτελούνται από μια μόνο εντολή και έτσι έχουν σχετικά μικρή διάρκεια. Από τη στιγμή που υπάρχει ένας πολύ μεγάλος αριθμός από πολύ μικρές διεργασίες, όπως και στο παράδειγμα του παράλληλου προγράμματος Τετραγωνικής Ρίζας έτσι και εδώ υπάρχει το πρόβλημα του μεγέθους διεργασίας. Επομένως, η εκτέλεση του προγράμματος μπορεί να βελτιωθεί με την ομαδοποίηση των τιμών του j στο εσωτερικό βρόχο:

PROGRAM SumArrays2;
 VAR i,j:integer;
		A, B, C: ARRAY [1..20, 1..30] OF REAL;
  BEGIN
  ...

  FORALL i := 1 TO 20 DO
		FORALL j := 1 TO 30 GROUPING 6 DO
			C[i,j] := A[i,j]+B[i,j];
      ....
  END.

Σε αυτή την καινούργια έκδοση του προγράμματος με τη χρήση των ομάδων, οι τιμές του μετρητή j μπαίνουν σε ομάδες μεγέθους 6. Έτσι, αντί για 600 μεμονωμένες διεργασίες, θα παραχθούν μόνο 100 διεργασίες παιδιά. Το μέγεθος για κάθε διεργασία παιδί είναι 6 φορές μεγαλύτερο από πριν, επειδή κάθε παιδί πρέπει να επαναλαμβάνεται και για τις 6 τιμές του μετρητή j.