Back to search

National Technical University of Athens (NTUA)

Συστήματα παράλληλης επεξεργασίας

Abstract

dc:description

The 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

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/23696

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Theodoropoulos, Panagiotis; Θεοδωρόπουλος, Παναγιώτης. Συστήματα παράλληλης επεξεργασίας. National Technical University of Athens (NTUA), 2008. http://hdl.handle.net/10442/hedi/23696