ΑΝΑΛΥΣΗ ΚΑΙ ΣΧΕΔΙΑΣΜΟΣ ΤΟΥ ΠΥΡΗΝΑ ΤΟΥ ΛΕΙΤΟΥΡΓΙΚΟΥ ΣΥΣΤΗΜΑΤΟΣ ΤΗΣ ΠΟΛΥΕΠΕΞΕΡΓΑΣΤΙΚΗΣ ΜΗΧΑΝΗΣ SIMULA

Abstract

THE AREA OF DISCRETE EVENT SIMULATION (DES) IS THE LEAST IMPACTED BY PARALLEL PROCESSING EVEN THOUGH MOST OF ITS APPLICATIONS REQUIRE TREMENDOUS AMOUNTS OF PROCESSING TIME. THE COMMON APPROACH OF PARALLELIZING INDIVIDUALLY SPECIAL PURPOSE PROGRAMS LEADS TO VERY LIMITED IMPROVEMENTS IN PERFORMANCE. WE PROPOSE HERE THE PARALLELIZATION OF GENERAL DES APPLICATIONS WRITTEN IN SIMULA, AS A PART OF AN ONGOING PROJECT THAT AIMS TOWARDS DEVELOPING METHODOLOGIES AND ARCHITECTURESFOR PARALLEL DES. SIMULA IS A GENERAL PURPOSE PROCESS ORIENTED LANGUAGE WHOSE STRUCTURE ALLOWS THE CREATION OF PROCESSES WHICH CAN PARTICIPATE IN A QUASI-PARALLEL EXECUTION ACCORDING TO AN INTERLEAVED FASHION . THE ARGUMENT THAT THE EVENT LIST OF THE SEQUENTIAL DES ALGORITHM CANNOT BE EFFICIENTLY PARTITIONED SO THAT TO SUPPORT CONCURRENT PROCESS EXECUTION IS DISPUTED, AND THE PROBLEM OF PARALLELIZING THE SEQUENTIAL DES ALGORITHM EMBEDDED IN HIGHER LEVEL SIMULATION LANGUAGES IS STUDIED. A GRAPH MODEL IS FIRST DEVELOPED TO REPRESENT THE PROCESS INTERFERENCE. THEN, THE DUAL PROBLEM OF MUTUALLY EXCLUDING INTERFERING PROCESSES AND CRITICAL (SUB)SECTIONS IS DEFINED AND SOLVED BY STATING THE QUASI-PARALLEL EQUIVALENCE AS THE BASIC REQUIREMENT THAT THE SOLUTION SHOULD SATISFY. FURTHERMORE, THE RELATION BETWEEN PROCESS CONCURRENCY AND INTERFERENCE IS INVESTIGATED, THE DEGREE OF PARALLELISM IS DEFINED AND ITS BOUNDS ARE ESTABLISHED. IMPLEMENTATION ASPECTS ARE ALSO INTRODUCED, INCLUDING THE NEW PARALLEL DES PACKAGE P_SIMULATION, THE SCHEDULER AND THE SYNCHRONIZER OF THE OPERATING SYSTEM KERNEL, AND THE MAIN FEATURES OF THE PROPOSED MULTIPROCESSOR ARCHITECTURE. FINALLY, EXPERIMENTAL RESULTS AND PERFORMANCE STUDIES ARE CONDUCTED, WHICH VALIDATE THE CORRECTNESS OF OUR APPROACH AND THE HIGH PERFORMANCE EXPECTED.

ΤΟ ΠΕΔΙΟ ΤΗΣ ΕΞΟΜΟΙΩΣΗΣ ΚΑΙ ΕΙΔΙΚΑ ΤΗΣ ΕΞΟΜΟΙΩΣΗΣ ΔΙΑΚΡΙΤΩΝ ΓΕΓΟΝΟΤΩΝ (ΕΔΓ), ΕΧΕΙ ΛΙΓΩΤΕΡΟ ΕΠΗΡΕΑΣΤΕΙ ΑΠΟ ΤΗΝ ΠΑΡΑΛΛΗΛΗ ΕΠΕΞΕΡΓΑΣΙΑ ΠΑΡΟΤΙ ΑΠΑΙΤΕΙ ΤΕΡΑΣΤΙΟΥΣ ΧΡΟΝΟΥΣ ΕΠΕΞΕΡΓΑΣΙΑΣ. Η ΜΕΘΟΔΟΛΟΓΙΑ ΤΗΣ ΜΟΝΟΜΕΡΟΥΣ ΠΑΡΑΛΛΗΛΟΠΟΙΗΣΗΣ ΠΡΟΓΡΑΜΜΑΤΩΝ ΕΙΔΙΚΟΥ ΣΚΟΠΟΥ, ΕΧΕΙ ΟΔΗΓΗΣΕΙ ΜΟΝΟ ΣΕ ΠΕΡΙΟΡΙΣΜΕΝΗ ΒΕΛΤΙΩΣΗ ΤΗΣ ΕΠΙΔΟΣΗΣ ΤΩΝ ΕΦΑΡΜΟΓΩΝ. ΣΤΗΝ ΕΡΓΑΣΙΑ ΑΥΤΗ ΠΡΟΤΕΙΝΕΤΑΙ Η ΠΑΡΑΛΛΗΛΟΠΟΙΗΣΗ ΓΕΝΙΚΩΝ ΠΡΟΓΡΑΜΜΑΤΩΝΕΔΓ ΓΡΑΜΜΕΝΩΝ ΣΕ SIMULA. Η ΠΡΟΤΑΣΗ ΑΥΤΗ ΑΠΟΤΕΛΕΙ ΜΕΡΟΣ ΕΝΟΣ ΓΕΝΙΚΩΤΕΡΟΥ ΣΧΕΔΙΟΥ ΑΝΑΠΤΥΞΗΣ ΜΕΘΟΔΟΛΟΓΙΑΣ ΚΑΙ ΑΡΧΙΤΕΚΤΟΝΙΚΩΝ ΓΙΑ ΠΑΡΑΛΛΗΛΗ ΕΔΓ. Η SIMULA ΕΙΝΑΙ ΜΙΑ OBJECT ORIENTED ΓΛΩΣΣΑ ΤΗΣ ΟΠΟΙΑΣ Η ΔΟΜΗ ΕΠΙΤΡΕΠΕΙ ΤΗΝ ΨΕΥΔΟΠΑΡΑΛΛΗΛΗ ΕΚΤΕΛΕΣΗ ΔΙΕΡΓΑΣΙΩΝ ΣΤΗ ΛΙΣΤΑ ΣΥΜΒΑΝΤΩΝ. ΣΤΗ ΔΙΑΤΡΙΒΗ ΑΥΤΗ ΜΕΛΕΤΗΘΗΚΕ ΤΟ ΠΡΟΒΛΗΜΑ ΤΗΣΠΑΡΑΛΛΗΛΟΠΟΙΗΣΗΣ ΤΟΥ ΣΕΙΡΙΑΚΟΥ ΑΛΓΟΡΙΘΜΟΥ ΕΔΓ, ΠΟΥ ΕΙΝΑΙ ΕΝΣΩΜΑΤΩΜΕΝΟΣ ΣΕ ΓΛΩΣΣΕΣ ΑΝΩΤΕΡΟΥ ΕΠΙΠΕΔΟΥ ΟΠΩΣ Η SIMULA. ΑΜΦΙΣΒΗΤΕΙΤΑΙ ΤΟ ΕΠΙΧΕΙΡΗΜΑ ΠΡΟΗΓΟΥΜΕΝΩΝ ΕΡΕΥΝΗΤΩΝ, ΟΤΙ Η ΛΙΣΤΑ ΣΥΜΒΑΝΤΩΝ ΤΟΥ ΣΕΙΡΙΑΚΟΥ ΑΛΓΟΡΙΘΜΟΥ ΔΕΝ ΕΙΝΑΙ ΔΥΝΑΤΟΝ ΝΑ ΔΙΑΜΕΡΙΣΤΕΙ ΓΙΑ ΥΠΟΣΤΗΡΙΞΗ ΠΑΡΑΛΛΗΛΗΣ ΕΠΕΞΕΡΓΑΣΙΑΣ. ΚΑΤ' ΑΡΧΑΣ ΟΡΙΣΤΗΚΕ ΕΝΑ ΜΑΘΗΜΑΤΙΚΟ ΜΟΝΤΕΛΟ ΜΕ ΧΡΗΣΗ ΓΡΑΦΗΜΑΤΩΝ ΓΙΑ ΝΑ ΠΑΡΑΣΤΑΘΕΙ Η ΣΧΕΣΗ ΕΠΕΜΒΑΣΗΣ ΤΩΝ ΔΙΕΡΓΑΣΙΩΝ. ΣΤΗ ΣΥΝΕΧΕΙΑ ΟΡΙΣΤΗΚΕ ΤΟ ΔΙΤΤΟ ΠΡΟΒΛΗΜΑ ΤΟΥ ΑΜΟΙΒΑΙΟΥ ΑΠΟΚΛΕΙΣΜΟΥ ΔΙΕΡΓΑΣΙΩΝ ΕΠΕΜΒΑΣΗΣ ΚΑΙ ΤΩΝ ΚΡΙΣΙΜΩΝ (ΥΠΟ)ΠΕΡΙΟΧΩΝ, ΚΑΙ ΛΥΘΗΚΕ ΜΕ ΤΗΝ ΕΙΣΑΓΩΓΗ ΤΗΣ ΨΕΥΔΟΠΑΡΑΛΛΗΛΗΣ ΙΣΟΔΥΝΑΜΙΑΣ ΣΑΝ ΒΑΣΙΚΗΣ ΑΠΑΙΤΗΣΗΣ ΠΟΥ ΘΑ ΠΡΕΠΕΙ ΝΑ ΙΚΑΝΟΠΟΙΟΥΝ ΟΙ ΛΥΣΕΙΣ. ΔΙΕΡΕΥΝΗΘΗΚΕ Η ΕΠΙΔΡΑΣΗ ΤΗΣ ΕΠΕΜΒΑΣΗΣ ΣΤΟΝ ΠΑΡΑΛΛΗΛΙΣΜΟ ΤΩΝ ΔΙΕΡΓΑΣΙΩΝ ΚΑΙ ΟΡΙΣΤΗΚΑΝ Ο ΒΑΘΜΟΣ ΠΑΡΑΛΛΗΛΙΣΜΟΥ ΚΑΙ ΤΑ ΟΡΙΑ ΤΟΥ. ΑΝΑΠΤΥΧΘΗΚΕ ΤΟ ΝΕΟ ΠΑΚΕΤΟ ΠΑΡΑΛΛΗΛΗΣ ΕΔΓ P_SIMULATION, ΣΧΕΔΙΑΣΤΗΚΕ Ο ΧΡΟΝΟΠΡΟΓΡΑΜΜΑΤΙΣΤΗΣ ΚΑΙ Ο ΣΥΓΧΡΟΝΙΣΤΗΣ ΤΟΥ ΠΥΡΗΝΑ ΤΟΥ ΛΕΙΤΟΥΡΓΙΚΟΥ ΣΥΣΤΗΜΑΤΟΣ ΚΑΙ ΠΡΟΤΑΘΗΚΕ Η ΑΡΧΙΤΕΚΤΟΝΙΚΗ ΤΟΥ ΠΑΡΑΛΛΗΛΟΥ ΣΥΣΤΗΜΑΤΟΣ. ΤΕΛΟΣ, ΕΓΙΝΕ ΜΕΛΕΤΗ ΤΗΣ ΑΠΟΔΟΤΙΚΟΤΗΤΑΣ ΣΕ ΔΙΑΦΟΡΕΣ ΠΕΙΡΑΜΑΤΙΚΕΣ ΚΑΙ ΠΡΑΓΜΑΤΙΚΕΣ ΕΦΑΡΜΟΓΕΣ, ΟΙ ΟΠΟΙΕΣ ΕΠΑΛΗΘΕΥΣΑΝ ΤΗΝ ΟΡΘΟΤΗΤΑ ΤΟΥ ΣΧΕΔΙΑΣΜΟΥ ΚΑΙ ΤΗΝ ΑΝΑΜΕΝΟΜΕΝΗ ΥΨΗΛΗ ΑΠΟΔΟΤΙΚΟΤΗΤΑ ΤΟΥ ΣΥΣΤΗΜΑΤΟΣ.