2.4 Παράδειγμα: Πολλαπλασιασμός μητρών

Επόμενο:2.5 Διαμοιραζόμενες και Τοπικές Μεταβλητές Πάνω:Κεφάλαιο 2ο: Παραλληλισμός Δεδομένων Πίσω:2.3 Φωλιασμένοι Βρόχοι

2.4 Παράδειγμα: Πολλαπλασιασμός μητρών

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

Για να πολλαπλασιάσουμε δύο ανύσματα, πρέπει και τα δύο να έχουν τον ίδιο αριθμό στοιχείων. Το αποτέλεσμα του εσωτερικού γινόμενου υπολογίζεται, αν πολλαπλασιάσουμε τα αντίστοιχα στοιχεία των δύο ανυσμάτων και μετά προσθέσουμε όλα αυτά τα αποτελέσματα. Ας θεωρήσουμε δύο ανύσματα που είναι αποθηκευμένα στους πίνακες X και Y, που ο καθένας έχει n στοιχεία. Το εσωτερικό γινόμενο είναι ένας απλός αριθμός όπως ορίζεται παρακάτω:

X[1].Y[1] + X[2].Y[2] + ...+ X[n].Y[n]

Αυτό το εσωτερικό γινόμενο μπορεί να υπολογιστεί με τον ακόλουθο κώδικα:

sum := 0;
  FOR k := 1 TO n DO
	sum := sum +X[k]*Y[k];

Το στοιχείο C[i,j] της μήτρας του πολλαπλασιασμού υπολογίζεται σαν εσωτερικό γινόμενο της γραμμής i από την Α μήτρα με την στήλη j από την μήτρα Β.

mitraImage

ΣΧΗΜΑ 2.5 Πολλαπλασιασμός μητρών.

Τώρα θεωρείστε των πολλαπλασιασμό δύο μητρών Α και Β, που η κάθε μια αντιστοιχεί σε ένα πίνακα πραγματικών αριθμών με διαστάσεις n επί n. Το αποτέλεσμα των Α και Β θα είναι μια άλλη μήτρα C διαστάσεων n επί n. Κάθε στοιχείο C[i,j] της παραγόμενης μήτρας υπολογίστηκε από το εσωτερικό γινόμενο της γραμμής i της Α με την στήλη j της Β. Αυτό παρουσιάζεται στο Σχήμα 2.5. Η μήτρα Α έχει n γραμμές, και κάθε γραμμή είναι ένα άνυσμα με n στοιχεία. Η μήτρα Β έχει n στήλες, και κάθε στήλη είναι ένα άνυσμα με n στοιχεία. Το εσωτερικό γινόμενο της γραμμής 1 της Α με την στήλη 1 της Β δίνει το στοιχείο C[1,1] της παραγόμενης μήτρας. Το εσωτερικό γινόμενο της γραμμής 1 της Α με την στήλη 2 της Β δίνει το στοιχείο C[1,2] της παραγόμενης μήτρας. Το προϊόν της γραμμής 1 της Α με την στήλη 3 της Β δίνει το C[1,3]. Έτσι, η πρώτη γραμμή της Α συνδυάζεται με όλες τις στήλες της Β και δίνει της πρώτη γραμμή της C. Όμοια, η δεύτερη γραμμή της Α, αν πολλαπλασιαστεί με κάθε στήλη της Β θα δώσει την δεύτερη γραμμή της C. Η λειτουργία πολλαπλασιασμού μητρών μπορεί εύκολα να εκφραστεί με τον ακόλουθο σειριακό υπολογισμό.

Πολλαπλασιασμός Μητρών C = A * B:
	FOR i := 1 TO n DO
	  FOR j := 1 TO n DO
		υπολόγισε το  C[i,j] σαν το εσωτερικό γινόμενο της γραμμής i της A με την στήλη j της B;

Αν υπάρχουν αρκετοί διαθέσιμοι επεξεργαστές, θα είναι δυνατόν καθένα από τα παραπάνω παραγόμενα ανύσματα να υπολογιστούν παράλληλα σε διαφορετικό επεξεργαστή. Από τη στιγμή που υπάρχουν n γραμμές στην Α και n στήλες στην Β, υπάρχουν n²παραγόμενα ανύσματα, των οποίων τα αποτελέσματα μορφοποιούν τα n²στοιχεία του πίνακα C. Aν υπάρχουν τουλάχιστον n² επεξεργαστές στην αρχιτεκτονική του συστήματος διαμοιραζόμενης μνήμης, τότε οι παραπάνω σειριακοί υπολογισμοί μπορούν να παραλληλιστούν μετατρέποντας τους φωλιασμένους FOR βρόχους σε φωλιασμένες FORALL εντολές με τον ακόλουθο τρόπο:

Παράλληλος Πολλαπλασιασμός Μητρών C= A * B:
	FORALL := 1 TO n DO
	 FORALL := 1 TO n DO
		υπολόγισε το C[i,j] σαν το εσωτερικό γινόμενο της γραμμής i της Α με την στήλη  j της Β;

Το ολοκληρωμένο πρόγραμμα για τον σειριακό πολλαπλασιασμό μητρών έχει ως εξής:

PROGRAM MatrixMultiply;
 CONST n=10;
 VAR A, B, C: ARRAY [1..n, 1..n] OF REAL;
		i, j, k: INTEGER;
		sum: REAL;
  BEGIN
  ...

  FOR i := 1 TO n DO
   FOR j := 1 TO n DO
   BEGIN
		sum := 0;
  		FOR k := 1 TO n DO
				sum := sum + A[i,k] +B[k,j];
				C[i,j] := sum;
   END;
   ...
END.

Στο παραπάνω πρόγραμμα, ο εσωτερικός βρόχος FOR με τον μετρητή k χρησιμοποιείται για να υπολογίσει το εσωτερικό γινόμενο της γραμμής i της Α με την στήλη j της Β. Η μεταβλητή sum χρησιμοποιείται για να συσσωρεύσει το άθροισμα κατά τη διάρκεια των υπολογισμών του ανύσματος. Εφόσον υπάρχουν τρεις φωλιασμένοι βρόχοι, που για τον κάθε ένα ο μετρητής μεταβάλλεται από 1 σε n, ο συνολικός χρόνος εκτέλεσης γι’ αυτόν τον αλγόριθμο πολλαπλασιασμού μητρών είναι Ο(n³).

O παραλληλισμός σε αυτόν τον αλγόριθμο μπορεί να επιτευχθεί μετατρέποντας τον εξωτερικό i βρόχο σε FORALL, έτσι δημιουργείται ένα σύνολο από n παράλληλες διεργασίες - μια διεργασία για κάθε τιμή του i. Αν απαιτείται και επιπλέον παραλληλισμός τότε και ο βρόχος j θα πρέπει να μετατραπεί σε FORALL βρόχο. Για λόγους που θα εξηγήσουμε σύντομα, η παράλληλη έκδοση του προγράμματος απαιτεί ελάχιστη τροποποίηση: ο εσωτερικός βρόχος FOR που υπολογίζει το εσωτερικό γινόμενο τοποθετείται σε μια διαδικασία που ονομάζεται ‘’VectorProduct’’. Ακολουθεί το παράλληλο πρόγραμμα πολλαπλασιασμού μητρών:

PROGRAM ParallelMatrixMultiply;


    CONST n=10;


    VAR A, B, C: ARRAY [1..n, 1..n] OF REAL;


        i,j:integer;


    PROCEDURE VectorProduct(i, j: INTEGER);


    VAR sum: REAL;


        k: INTEGER;


    BEGIN


        sum := 0;


        FOR k := 1 TO n DO


            sum := sum + A[i,k] * B[k,j];


     C[i,j] := sum;


    END;


BEGIN (* Σώμα κυρίως προγράμματος*)


...


FORALL i := 1 TO n DO


    FORALL j := 1 TO n DO


      VectorProduct(i,j); (*υπολογίζει την γραμμή i της Α τόσες φορές


      όσες και οι στήλες j της Β*)


...


END.

Αυτό το πρόγραμμα χρησιμοποιεί n² επεξεργαστές, και ως τούτου προσφέρει μεγάλη επιτάχυνση σε σχέση με την σειριακή έκδοση του προγράμματος. Η υπολογιστική πολυπλοκότητα του πολλαπλασιασμού μητρών μετριέται με τον αριθμό των πολλαπλασιασμών και των προσθέσεων, που είναι οι πιο χρονοβόρες λειτουργίες. Για να υπολογιστεί ένα απλό εσωτερικό γινόμενο απαιτούνται n προσθέσεις και n πολλαπλασιασμοί. Ο συνολικός αλγόριθμος πολλαπλασιασμού μητρών υπολογίζει n² παραγόμενα ανύσματα. Επομένως, το σειριακό πρόγραμμα MatrixMultiply απαιτεί n³ προσθέσεις και n³πολλαπλασιασμούς. Ο συνολικός χρόνος εκτέλεσης θα είναι τότε Ο(n³).

Στο παράλληλο Matrix Multiply πρόγραμμα που είδαμε παραπάνω, τα απαιτούμενα n²παραγόμενα ανύσματα που υπολογίζονται παράλληλα από διαφορετικούς φυσικούς επεξεργαστές. Επομένως, ο συνολικός χρόνος εκτέλεσης του προγράμματος είναι Ο(n). Αν το σύστημα διαμοιραζόμενης μνήμης έχει περισσότερους από n²επεξεργαστές, τότε είναι πιθανόν να επιταχυνθεί ο πολλαπλασιασμός μητρών ακόμα περισσότερο με το να χρησιμοποιήσουμε αρκετούς επεξεργαστές για κάθε εσωτερικό γινόμενο. Αν είναι διαθέσιμοι n³επεξεργαστές, τότε ο χρόνος εκτέλεσης του παράλληλου προγράμματος μπορεί να μειωθεί σε O(logn). Στο Κεφάλαιο 6 παρουσιάζεται μια παράλληλη μέθοδος για τον υπολογισμό του εσωτερικού γινομένου.

Όμως, ας παρατηρήσουμε στο παραπάνω παράλληλο πρόγραμμα ότι ο παράλληλος υπολογισμός του παραγόμενου ανύσματος δεν μπορεί να επιτευχθεί απλά με τη μετατροπή του εσωτερικού βρόχου FOR (μετρητή k) σε εντολή FORALL. Οι επαναλήψεις του εσωτερικού βρόχου χρησιμοποιούν τη μεταβλητή sum για να συσσωρεύσουν το άθροισμα: η μεταβλητή sum διαβάζει και γράφει σε κάθε επανάληψη του βρόχου. Επομένως, αυτές οι σειριακές επαναλήψεις δεν μπορούν απλά να μοιραστούν σε διαφορετικούς επεξεργαστές που εκτελούνται παράλληλα. Αν αυτό γινόταν τότε όλοι οι επεξεργαστές θα προσπαθούσαν να διαβάσουν και να μεταβάλουν την τιμή του sum, γεγονός που θα προκαλούσε παρεμβολές και θα παρήγαγε λανθασμένα αποτελέσματα. Το σημαντικό θέμα των ανταγωνιζόμενων αναφορών παράλληλων επεξεργαστών σε διαμοιραζόμενες μεταβλητές θα συζητηθεί με λεπτομέρεια στο Κεφάλαιο 4.