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

 
This item is provided by the institution :

Repository :
National Archive of PhD Theses
see the original item page
in the repository's web site and access all digital files if the item*
share



PhD thesis (EN)

1994 (EN)
DEVELOPMENT AND COMPARISON OF PARALLEL ALGORITHMS FOR SOLVING LINEAR SYSTEMS
ΑΝΑΠΤΥΞΗ ΚΑΙ ΑΞΙΟΛΟΓΗΣΗ ΠΑΡΑΛΛΗΛΩΝ ΑΛΓΟΡΙΘΜΩΝ ΓΙΑ ΤΗΝ ΑΡΙΘΜΗΤΙΚΗ ΕΠΙΛΥΣΗ ΓΡΑΜΜΙΚΩΝ ΣΥΣΤΗΜΑΤΩΝ

ΤΖΑΦΕΡΗΣ, ΦΙΛΙΠΠΟΣ

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

Linear systems
ΠΑΡΑΛΛΗΛΟΙ ΑΡΙΘΜΗΤΙΚΟΙ ΑΛΓΟΡΙΘΜΟΙ
CRITICAL (OR LONGEST) PATH
ΠΑΡΑΛΛΗΛΟΙ ΥΠΟΛΟΓΙΣΤΕΣ
Factorization
PARALLEL NUMERICAL ALGORITHMS
Gaussian elimination
Parallel computers
Γραμμικά συστήματα
Παραγοντοποίηση
ΓΡΑΦΗΜΑ ΕΡΓΑΣΙΩΝ
Direct methods
TASKS GRAPH
Απαλοιφή Gauss
ΑΜΕΣΟΙ ΜΕΘΟΔΟΙ
ΚΡΙΣΙΜΟ (Η ΜΕΓΑΛΥΤΕΡΟ) ΜΟΝΟΠΑΤΙ

Εθνικό Κέντρο Τεκμηρίωσης (ΕΚΤ) (EL)
National Documentation Centre (EKT) (EN)

Greek

1994


National and Kapodistrian University of Athens
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών (ΕΚΠΑ)



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)