Discovery of parallelism in sequential programs

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. DiscoPoP is open source and available for download at Github.

 

Selected Publications