"Synchronization Architecture in Parallel Programming Models"

Dr. Arturo González-Escribano (PhD Thesis - European PhD)

Institute: Dpto. Informática, University of Valladolid
Supervisors:
- Dr. Valentín Cardeńoso-Payo (Dpto. Informática, University of Valladolid, Spain)
- Dr.ir. Arie J.C. van Gemund (ITS, Technical University Delft, The Netherlands)
Graduation committee:
- Dr. Casiano Rodríguez León (University of La Laguna, Spain) -- Committee president
- Dr. Diego Llanos Ferraris (University of Valladolid, Spain) -- Committee secretary
- Dr. Michael O'Boyle (The University of Edimburgh, Scotland, UK)
- Dr. Ben Juurlink (Delft University of Technology, The Netherlands)
- Dr. Julio Ortega Lopera (University of Granada, Spain)
Presentation date: Jul 29th, 2003
Grade: Summa cum laude (European PhD honourable mention)

Dissertation and presentation

WARNING: This section contains links to PostScript and PDF files that are covered by copyright. You may browse them at your convenience (in the same spirit as you may read a journal or a proceeding article in a public library). Retrieving, copying, or distributing these files, however, may violate the copyright protection law. We recommend that the user abides international law in accessing this directory.

Abstract

It is not yet clear what type of programming model is more convenient for nowadays and near future parallel computation frameworks. It will be highly interesting to find objective characteristics to evaluate or classify the potential benefits and drawbacks of a given model. We propose a new taxonomy criteria. Programming models can be classified in terms of their Synchronization Architecture, defined by the mechanisms which are provided for expressing synchronization/communication, and the structures that can be created by them. This dissertation includes a conceptual study of many well-known parallel programming models and paradigms to show how the synchronization structure is highly related to both: the analysis properties of a model, that lead to interesting software-engineering abilities, and the expressive power of the model, that leads to performance efficiency. Unfortunately, there exist a trade-off between these two important features. In our work we identify an important class of synchronization architectures, which obtain the most relevant analysis characteristics by introducing a light restriction on the expressive power. This is the class associated with nested-parallelism or series-parallel task graphs. We present a theoretical study based on task-graphs introducing methods to map known applications to this restricted synchronization class, and evaluating how much potential performance impact may impose such high-level transformations. The work is completed with an extensive experimental study including synthetic graphs, parallel application models, and real programs. We conclude that synchronization architecture is a key factor for the software engineering abilities and the expressive power inherent to a parallel programming model. Nested-parallelism presents a good trade-off between them, being a promising candidate for more portable and development-efficient parallel programming models.

Downloads

Table of Contents (PDF) -- 3 pages
Dissertation (ps.gz) -- 248 pages including table of contents, list of figures and list of tables
Presentation slides (PDF) -- 45 slides including layered elements and animated graphics

Arturo González Escribano <arturo@infor.uva.es>

Last modified: Nov, 2003