ΑΝΑΠΤΥΞΗ ΚΑΙ ΑΞΙΟΛΟΓΗΣΗ ΠΑΡΑΛΛΗΛΩΝ ΑΛΓΟΡΙΘΜΩΝ ΓΙΑ ΤΗΝ ΑΡΙΘΜΗΤΙΚΗ ΕΠΙΛΥΣΗ ΓΡΑΜΜΙΚΩΝ ΣΥΣΤΗΜΑΤΩΝ

Abstract

THE OBJECTIVE OF THE THESIS IS THE DEVELOPMENT AND COMPARISON OF PARALLEL ALGORITHMS FOR THE SOLUTION OF LINEAR SYSTEMS ON MIMD MACHINES. SPECIFICALLY THE IMPLEMENTATION OF THE CLASSIC DIRECT METHODS GAUSSIAN ELIMINATION (GE), GAUSS-JORDAN (GJ) AND HUARD (HU) AS WELL AS THE FACTORIZATION METHODS LU AND WZ ARECONSIDERED FOR SHARED MEMORY MIMD MACHINES. BY CONSIDERED LOOP UNROLLING TECHNIQUES, DIFFERENT VERSIONS OF THE SAME SEQUENTIAL ALGORITHM ARE PRODUCED AND ARE STUDIED IN DETAIL. MOTIVATED BY THE FACT OF REVEALING THE HIGHEST DEGREE OFPARALLELISM WHICH MIGHT EXIST IN A CERTAIN ALGORITHM WE ATTEMPT DIFFERENT SELECTION STRATEGIES FOR SPECIFYING THE INDEPENDENT TASKS IN THE ABOVE ALGORITHMSNEXT, THE TASK GRAPH IS FORMED WHICH IS DERIVED BY THE PRECEDENCE CONSTRAINTSIMPOSED BY THE FLOW OF THE SEQUENTIAL ALGORITHMS. THE DEVELOPMENT OF GOOD HEURISTIC (OR OPTIMAL) SCHEDULING ALGORITHMS RESPECTING THE PRECEDENCE CONSTRAINTS OF THE TASK GRAPH IS ALSO CONSIDERED. FOR THE DIFFERENT PARALLEL FORMS OF THE METHODS GE, GJ, HU, LU AND WZ, THE PARALLEL EXECUTION TIMES, THE SPEEDUPS AND THE EFFICIENCIES ARE COMPARED. IN ORDER TO SHOW THAT THE DEVELOPED ANALYSIS CAN ALSO BE APPLIED, WITH CERTAIN MODIFICATIONS, FOR THE IMPLEMENTATION OF THE CONSIDERED ALGORITHMS ON DISTRIBUTED MIMD MESSAGE PASSING MACHINES, THE IMPLEMENTATION OF THE GJ WITH PARTIAL PIVOTING IS CONSIDERED ON THE NCUBE 10 MACHINE.

Ο ΑΝΤΙΚΕΙΜΕΝΙΚΟΣ ΣΚΟΠΟΣ ΤΗΣ ΔΙΑΤΡΙΒΗΣ ΑΥΤΗΣ ΕΙΝΑΙ Η ΑΝΑΠΤΥΞΗ ΚΑΙ ΑΞΙΟΛΟΓΗΣΗ ΑΛΓΟΡΙΘΜΩΝ ΓΙΑ ΤΗΝ ΑΡΙΘΜΗΤΙΚΗ ΕΠΙΛΥΣΗ ΓΡΑΜΜΙΚΩΝ ΣΥΣΤΗΜΑΤΩΝ ΣΕ ΠΟΛΥΕΠΕΞΕΡΓΑΣΤΕΣ ΜΕΚΟΙΝΗ (SHARED) ΚΑΙ ΚΑΤΑΝΕΜΗΜΕΝΗ (DISTRIBUTED) ΜΝΗΜΗ. ΠΙΟ ΣΥΓΚΕΚΡΙΜΕΝΑ ΜΕΛΕΤΑΤΑΙ Η ΕΦΑΡΜΟΓΗ ΤΩΝ ΚΛΑΣΣΙΚΩΝ ΑΜΕΣΩΝ ΜΕΘΟΔΩΝ ΑΠΑΛΟΙΦΗΣ ΤΟΥ GAUSS (GE), GAUSS-JORDAN (GJ) ΚΑΙ HUARD (HU) ΚΑΘΩΣ ΕΠΙΣΗΣ ΚΑΙ ΤΩΝ ΜΕΘΟΔΩΝ ΠΑΡΑΓΟΝΤΟΠΟΙΗΣΗΣ LU ΚΑΙWZ ΣΕ MIMD ΜΗΧΑΝΕΣ ΜΕ ΚΟΙΝΗ ΜΝΗΜΗ. ΕΞΕΤΑΖΟΝΤΑΙ ΠΑΡΑΛΛΗΛΕΣ ΤΩΝ ΑΚΟΛΟΥΘΙΑΚΩΝ ΑΛΓΟΡΙΘΜΩΝ ΤΩΝ ΠΑΡΑΠΑΝΩ ΜΕΘΟΔΩΝ, ΟΙ ΟΠΟΙΕΣ ΠΑΡΑΓΟΥΝ ΔΙΑΦΟΡΕΤΙΚΟΥΣ ΠΑΡΑΛΛΗΛΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ. ΜΕ ΚΙΝΗΤΡΟ ΤΗΝ ΟΣΟ ΤΟ ΔΥΝΑΤΟΝ ΚΑΛΥΤΕΡΗ ΕΚΜΕΤΑΛΛΕΥΣΗ ΤΗΣ ΠΑΡΑΛΛΗΛΙΑΣ ΕΠΙΧΕΙΡΟΥΝΤΑΙ ΕΝΑΛΛΑΚΤΙΚΕΣ ΕΠΙΛΟΓΕΣ ΣΤΟΝ ΤΡΟΠΟ ΚΑΘΟΡΙΣΜΟΥ ΤΩΝ ΑΝΕΞΑΡΤΗΤΩΝ ΥΠΟΛΟΓΙΣΤΙΚΩΝ ΕΡΓΑΣΙΩΝ (TASKS) ΣΕ ΟΛΟΥΣ ΤΟΥΣ ΠΑΡΑΠΑΝΩ ΑΛΓΟΡΙΘΜΟΥΣ. ΣΤΗ ΣΥΝΕΧΕΙΑ ΣΧΗΜΑΤΙΖΕΤΑΙ ΤΟ ΓΡΑΦΗΜΑ ΤΩΝ ΕΡΓΑΣΙΩΝ, ΤΟ ΟΠΟΙΟ ΠΑΡΑΓΕΤΑΙ ΑΠΟ ΤΙΣ ΑΛΛΗΛΟΕΞΑΡΤΗΣΕΙΣ ΤΩΝ ΔΕΔΟΜΕΝΩΝ ΤΟΥΣ ΠΟΥ ΕΠΙΒΑΛΛΟΝΤΑΙ ΑΠΟ ΤΗ ΡΟΗ ΤΩΝ ΑΚΟΛΟΥΘΙΑΚΩΝ ΑΛΓΟΡΙΘΜΩΝ.ΜΕ ΒΑΣΗ ΤΟ ΓΡΑΦΗΜΑ ΑΥΤΟ ΕΠΙΧΕΙΡΕΙΤΑΙ Η ΕΥΡΕΣΗ "ΚΑΛΩΝ" ΕΥΡΕΣΤΙΚΩΝ ΑΛΓΟΡΙΘΜΩΝ ΔΡΟΜΟΛΟΓΗΣΗΣ ΜΕ ΤΗ ΜΕΛΕΤΗ ΕΝΑΛΛΑΚΤΙΚΩΝ ΤΡΟΠΩΝ ΕΚΤΕΛΕΣΗΣ ΤΩΝ ΑΝΕΞΑΡΤΗΤΩΝ ΕΡΓΑΣΙΩΝ ΤΗΡΩΝΤΑΣ ΤΟΥΣ ΔΟΘΕΝΤΕΣ ΠΕΡΙΟΡΙΣΜΟΥΣ ΠΡΟΤΕΡΑΙΟΤΗΤΑΣ. ΑΚΟΛΟΥΘΩΣ ΣΥΓΚΡΙΝΟΝΤΑΙ ΟΙ ΧΡΟΝΟΙ ΠΑΡΑΛΛΗΛΗΣ ΕΚΤΕΛΕΣΗΣ, ΟΙ ΕΠΙΤΑΧΥΝΣΕΙΣ ΚΑΙ ΟΙ ΑΠΟΔΟΤΙΚΟΤΗΤΕΣ ΤΩΝ ΠΡΟΤΕΙΝΟΜΕΝΩΝ ΠΑΡΑΛΛΗΛΩΝ ΑΛΓΟΡΙΘΜΩΝ. ΤΕΛΟΣ ΠΑΡΟΥΣΙΑΖΕΤΑΙ Η ΥΛΟΠΟΙΗΣΗ ΤΗΣ ΜΕΘΟΔΟΥ GJ ΜΕ ΜΕΡΙΚΗ ΟΔΗΓΗΣΗ ΣΕ ΕΝΑ ΠΟΛΥΕΠΕΞΕΡΓΑΣΤΗ ΤΥΠΟΥ ΥΠΕΡΚΥΒΟΥ (NCUBE 10).