Abstract
dc:descriptionThe evolution of computer technology has been rapid over the past two decades. Equally striking, however, is the increase of needs in computing power. To meet the demanding and lengthy algorithms we introduce parallel processing. Parallel processing has been used for many years, mainly in the field of high performance computing, but interest in it has become even greater in recent years due to physical constraints that prevent further escalation of processors' frequency. Thus, it has recently become the dominant standard in computer architecture, mainly in the form of multicore processors. The coding of parallel programs is nonetheless significantly more difficult than that of the corresponding sequential, as the parallelism in the execution introduces several new categories of software errors. In addition, synchronization and communication costs between the parallel processes are usually the greatest obstacles in order to achieve good performance and decent acceleration from parallel programs. Finally, despite decades of work by researchers in the field of compilers, automatic parallelization of sequential programs had only limited success. The main parallel programming languages are explicitly parallel or, at best, partially driven, with the developer giving the compiler instructions for the parallelization of the code. The purpose of this thesis is the introduction and presentation to the developer of ways to facilitate programming in parallel processing systems and the efficient implementation of the respective mechanisms. The problem is approached from two different angles, giving the developer maximum flexibility in order to achieve the best results from the parallel program. The first approach is from the system level, in order to give the developer options for handwriting parallel code more easily and led to the implementation of the global semaphores mechanism. This mechanism has been implemented and ported to several different parallel programming environments, with the main being the parallel platforms PVM and MPI and is available as a C language library (runtime library) and some additional definitions files (include files). By using it, the parallel applications developer can address the problems of synchronizing parallel processes, mutual exclusion of critical sections and system resource allocation. The second approach is from the perspective of the compiler, so that a category of sequential algorithms can be automatically translated into equivalent parallel code and led to the implementation of the tool CRONUS. The CRONUS platform is an automated tool for the parallelization of general nested loops and is based on methods of computational geometry. Nested loops include complex loop bodies (assignments, conditionals, repetitions) and exhibit uniform dependencies through the body of the loop. The novelty of the CRONUS tool is twofold: firstly, it determines the optimal scheduling hyperplane using the QuickHull algorithm, which is more efficient than previously used methods and secondly, it implements a simple and efficient dynamic rule we call Successive Dynamic Scheduling (SDS), for the runtime scheduling of the loop iterations along the optimal hyperplane. This scheduling policy enhances data locality and improves the overall execution time. CRONUS provides an efficient runtime library, specifically designed to minimize the cost of communication and works both on shared memory and distributed memory systems. It uses two different models for data exchange and synchronization, with the first to rely solely on message passing calls, while the second combines the mechanism of global semaphores for synchronization and asynchronous message passing for data exchange. Finally, in real examples, it achieves significant speedups and performs much better than other similar tools of the literature.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2008
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Theodoropoulos, Panagiotis
- Θεοδωρόπουλος, Παναγιώτης
Subjects
dc:subject × 20- Παράλληλη επεξεργασία
- Καθολικός σηματοφορέας
- Φωλιασμένος βρόχος
- Διάνυσμα εξάρτησης
- ΟΜΟΙΟΜΟΡΦΕΣ ΕΞΑΡΤΗΣΕΙΣ
- Χώρος δεικτών και σημείο χώρου δεικτών
- Συστήματα κατανεμημένης μνήμης
- Χρονοδρομολόγηση
- Parallel processing
- Global semaphore
- Nested loops
- Dependence vector
- Uniform dependencies
- Index space and index point
- Distributed memory systems
- Scheduling
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/23696