uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Programming models based on data versioning for dependency-aware task-based parallelisation
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Scientific Computing. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computational Science.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Scientific Computing. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computational Science.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Scientific Computing. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computational Science.
2012 (English)In: Proc. 15th International Conference on Computational Science and Engineering, Los Alamitos, CA: IEEE Computer Society, 2012, p. 275-280Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Los Alamitos, CA: IEEE Computer Society, 2012. p. 275-280
National Category
Software Engineering
Identifiers
URN: urn:nbn:se:uu:diva-187446DOI: 10.1109/ICCSE.2012.45ISI: 000317475000038ISBN: 978-1-4673-5165-2 (print)OAI: oai:DiVA.org:uu-187446DiVA, id: diva2:574734
Conference
CSE 2012
Projects
eSSENCEUPMARCAvailable from: 2013-01-24 Created: 2012-12-06 Last updated: 2018-01-16Bibliographically approved
In thesis
1. Scientific Computing on Multicore Architectures
Open this publication in new window or tab >>Scientific Computing on Multicore Architectures
2014 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Computer simulations are an indispensable tool for scientists to gain new insights about nature. Simulations of natural phenomena are usually large, and limited by the available computer resources. By using the computer resources more efficiently, larger and more detailed simulations can be performed, and more information can be extracted to help advance human knowledge.

The topic of this thesis is how to make best use of modern computers for scientific computations. The challenge here is the high level of parallelism that is required to fully utilize the multicore processors in these systems.

Starting from the basics, the primitives for synchronizing between threads are investigated. Hardware transactional memory is a new construct for this, which is evaluated for a new use of importance for scientific software: atomic updates of floating point values. The evaluation includes experiments on real hardware and comparisons against standard methods.

Higher level programming models for shared memory parallelism are then considered. The state of the art for efficient use of multicore systems is dynamically scheduled task-based systems, where tasks can depend on data. In such systems, the software is divided up into many small tasks that are scheduled asynchronously according to their data dependencies. This enables a high level of parallelism, and avoids global barriers.

A new system for managing task dependencies is developed in this thesis, based on data versioning. The system is implemented as a reusable software library, and shown to be as efficient or more efficient than other shared-memory task-based systems in experimental comparisons.

The developed runtime system is then extended to distributed memory machines, and used for implementing a parallel version of a software for global climate simulations. By running the optimized and parallelized version on eight servers, an equally sized problem can be solved over 100 times faster than in the original sequential version. The parallel version also allowed significantly larger problems to be solved, previously unreachable due to memory constraints.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2014. p. 47
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1139
Keywords
multicore, scientific computing, shared memory parallelism, task-based programming, parallel programming model, task scheduling, data versioning
National Category
Software Engineering Computational Mathematics
Research subject
Scientific Computing
Identifiers
urn:nbn:se:uu:diva-221241 (URN)978-91-554-8928-1 (ISBN)
Public defence
2014-05-23, Room 2446, Polacksbacken, Lägerhyddsvägen 2, Uppsala, 10:15 (English)
Opponent
Supervisors
Projects
UPMARCeSSENCE
Available from: 2014-04-29 Created: 2014-03-26 Last updated: 2018-01-11Bibliographically approved
2. Advances in Task-Based Parallel Programming for Distributed Memory Architectures
Open this publication in new window or tab >>Advances in Task-Based Parallel Programming for Distributed Memory Architectures
2018 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

It has become common knowledge that parallel programming is needed for scientific applications, particularly for running large scale simulations. Different programming models are introduced for simplifying parallel programming, while enabling an application to use the full computational capacity of the hardware. In task-based programming, all the variables in the program are abstractly viewed as data. Parallelism is provided by partitioning the data. A task is a collection of operations performed on input data to generate output data. In distributed memory environments, the data is distributed over the computational nodes (or processes), and is communicated when a task needs remote data.

This thesis discusses advanced techniques in distributed task-based parallel programming, implemented in the DuctTeip software library. DuctTeip uses MPI (Message Passing Interface) for asynchronous inter-process communication and Pthreads for shared memory parallelization within the processes. The data dependencies that determine which subsets of tasks can be executed in parallel are extracted from information about the data accesses (input or output) of the tasks. A versioning system is used internally to represent the task-data dependencies efficiently. A hierarchical partitioning of tasks and data allows for independent optimization of the size of computational tasks and the size of communicated data. A data listener technique is used to manage communication efficiently.

DuctTeip provides an algorithm independent dynamic load balancing functionality. Redistributing tasks from busy processes to idle processes dynamically can provide an overall shorter execution time. A random search method with high probability of success is employed for locating idle/busy nodes.

The advantage of the abstract view of tasks and data is exploited in a unified programming interface, which provides a standard for task-based frameworks to decouple framework development from application development. The interface can be used for collaboration between different frameworks in running an application program efficiently on different hardware.

To evaluate the DuctTeip programming model, applications such as Cholesky factorization, a time-dependent PDE solver for the shallow water equations, and the fast multipole method have been implemented using DuctTeip. Experiments show that DuctTeip provides both scalability and performance. Comparisons with similar frameworks such as StarPU, OmpSs, and PaRSEC show competitive results.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2018. p. 42
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1621
Keywords
parallel programming, task-based programming, distributed memory system, scientific computing, hierarchical data, hierarchical tasks
National Category
Computer Systems
Identifiers
urn:nbn:se:uu:diva-338838 (URN)978-91-513-0209-6 (ISBN)
Public defence
2018-03-02, ITC/2446, ITC, Lägerhyddsvägen 2, Uppsala, 10:00 (English)
Opponent
Supervisors
Available from: 2018-02-09 Created: 2018-01-14 Last updated: 2018-03-08

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Zafari, AfshinTillenius, MartinLarsson, Elisabeth

Search in DiVA

By author/editor
Zafari, AfshinTillenius, MartinLarsson, Elisabeth
By organisation
Division of Scientific ComputingComputational Science
Software Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 1130 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf