DiscoPoP - Discovery of Potential Parallelism

Discopop sequential and parallel programm

DiscoPoP

Discovery of Potential Parallelism - A joint project of Technical University of Darmstadt and Iowa State University

DiscoPoP is a tool that helps software developers parallelize their programs with threads. It discovers potential parallelism in a sequential program and makes recommendations on how to exploit it using OpenMP.

Parallelism in a computer program is the ability to run it faster by using more than one processor at the same time. This becomes particularly relevant when there are no other optimization options left such as using a faster processor or algorithm. Given that technical constraints, in particular, power consumption, limit the speed of individual processors, parallelism is a powerful instrument to boost performance.

Functionality

The ability of compilers to automatically translate sequential programs into efficient parallel code is quite limited. Although auto-parallelization has been successfully applied in some cases such as loops that satisfy certain properties, no compiler exists yet that can effectively parallelize an arbitrarily structured program.

Because a compiler does not know the precise value of pointers and array indices that are computed at runtime, it may assume parallelism-preventing data dependences in places where they would never occur in practice. As a result, parallelization becomes too conservative.

With our parallelism discovery tool DiscoPoP, we aim to circumvent this problem. We abandon the idea of fully automatic parallelization and instead point the programmer to likely parallelization opportunities that we identify via dynamic dependence analysis.

In this way, we consider only data dependences that actually occur. From these dynamic dependences we derive possible parallel design patterns, which we propose to the programmer to parallelize their programs.

DiscoPoP Software

Download the latest version of DiscoPoP and also get to know the software through our detailed documentation. You can find the source on our GitHub repository.

The Team

Project Leaders

Felix Wolf

(Technical University of Darmstadt)

Ali Jannesari

(Iowa State University)

Current Developers

Lukas Rothenberger

Past Contributors

Mohammad Norouzi, Arya Mazaheri,
Rohit Atre, Michael Beaumont,
Daniel Fried, Wolfram Gottschlich,
Sergei Krestianskov, Zhen Li,
Nicolas Morew, Tuan dung Ngyen,
Zia Ul-Huda, Bo Zhao

Selected Publications

Below you find a list of selected publications

Overview

Mohammad Norouzi, Felix Wolf, Ali Jannesari: Automatic Construct Selection and Variable Classification in OpenMP. In Proc. of the International Conference on Supercomputing (ICS), Phoenix, AZ, USA, ACM, June 2019.

[PDF] [DOI] [BibTeX]

Further publications

Nicolas Morew, Mohammad Norouzi, Ali Jannesari, Felix Wolf: Skipping Non-essential Instructions Makes Data-Dependence Profiling Faster. In Proc. of the 26th Euro-Par Conference, Warsaw, Poland, volume 12247 of Lecture Notes in Computer Science, pages 3-17, Springer, August 2020.

[PDF] [DOI] [BibTeX]

Mohammad Norouzi, Qamar Ilias, Ali Jannesari, Felix Wolf: Accelerating Data-Dependence Profiling with Static Hints. In Proc. of the 25th Euro-Par Conference, Göttingen, Germany, Springer, August 2019.

[PDF] [DOI] [BibTeX]

Rohit Atre, Zia Ul Huda, Felix Wolf, Ali Jannesari: Dissecting Sequential Programs for Parallelization - An Approach Based on Computational Units. Concurrency and Computation: Practice and Experience, 31(5):1-12, March 2019.

[PDF] [DOI] [BibTex]

Zhen Li, Rohit Atre, Zia Ul Huda, Ali Jannesari, Felix Wolf: Unveiling Parallelization Opportunities in Sequential Programs. Journal of Systems and Software, 117:282–295, July 2016.

[PDF] [DOI] [BibTex]

Zia Ul Huda, Rohit Atre, Ali Jannesari, Felix Wolf: Automatic Parallel Pattern Detection in the Algorithm Structure Design Space. In Proc. of the 30th IEEE International Parallel and Distributed Processing Symposium (IPDPS), Chicago, USA, pages 43-52, IEEE Computer Society, May 2016.

[PDF] [DOI] [BibTeX]

Zhen Li, Ali Jannesari, Felix Wolf: An Efficient Data-Dependence Profiler for Sequential and Parallel Programs. In Proc. of the 29th IEEE International Parallel and Distributed Processing Symposium (IPDPS), Hyderabad, India, pages 484-493, IEEE Computer Society, May 2015.

[PDF] [DOI] [BibTeX]

Zia Ul Huda, Ali Jannesari, Felix Wolf: Using Template Matching to Infer Parallel Design Patterns. ACM Transactions on Architecture and Code Optimization, 11(4):64:1–64:21, January 2015.

[PDF] [DOI] [BibTeX]

Projects

Discopop is developed or used in the following projects:

Ongoing projects

National High Performance Computing Center for Computational Engineering Sciences (NHRC4CES) (DFG, 2021-2030)

As part of the Network for National High Performance Computing (NHR), RWTH Aachen University and TU Darmstadt combine their strengths in High Performance Computing (HPC) applications, algorithms and methods as well as in the efficient allocation and use of HPC hardware. As a joint NHR Center for Computational Engineering Sciences (NHR4CES), the two sites provide targeted support for engineering applications, especially with regard to complex flow scenarios, energy conversion, materials design, and engineering-oriented physics, chemistry, and life sciences. In this context, we aim to improve the performance and functionality of DiscoPoP with emphasis given to use cases in engineering applications.

Completed projects

Software-Factory 4.0 (LOEWE, 2018-2021)

The project Software-Factory 4.0 is a collaborative project funded by the German State of Hesse in the LOEWE program. The goal of the project is to explore new methods for the adaptation of legacy software to new requirements and technical advances. When software needs to be made faster, for example, to process bigger inputs in reasonable time, parallelization is often the only available option. To ease the parallelization process, this project aims to further improve DiscoPoP with emphasis given to its efficiency, scope, and degree of automation.

CAMSOD Project (Klaus Tschira Foundation, 2015–2019)

In this project, we developed methods that help software developers write correct and efficient parallel programs for shared-memory systems. Using the DiscoPoP technology, we created methods and tools for automated testing and correctness analysis. Furthermore, we explored techniques for finding performance bugs, in particular thread-level communication bottlenecks.