Identification of Suitable Parallelization Patterns for Sequential Programs

During the past decade, the degree of parallelism available in hardware has grown quickly and decisively. Unfortunately, transforming an existing sequential program into a parallel one is not an easy task. Although modern compilers are able to detect the parallelism available in simple loops, a wide range of sequential programs cannot profit from these strategies because such compilers may miss coarser-grained but sometimes more scalable parallelism. To strengthen programmer productivity, over the years software engineers created a comprehensive list of sequential design patterns. These patterns improve the quality, re-usability, and maintainability of the software. Similarly, to ease the burden of parallel programming, parallel design patterns have been introduced. These patterns provide reusable solutions for common problems and help avoid concurrency bugs such as deadlocks and data races, which are very difficult to locate. Although parallel patterns are helpful for programmers, much effort is still needed to find appropriate places to apply them in the software architecture. This problem is exacerbated if one’s job is to parallelize a sequential program written by someone else. A programmer or software architect needs to have deep knowledge of not only parallel patterns but also of the target program. Tools have been developed to identify parallel patterns in the data-dependence graphs of a sequential application but they usually support at most one or two parallel patterns. This dissertation presents a framework to automatically detect a much broader variety of parallel patterns in the algorithm structure design space of sequential applications. For the identification of parallel patterns, we analyze the dependence graphs of each region of the application under study. We use different novel approaches, such as template matching and regression analysis to detect parallel patterns in a region. Furthermore, code blocks in a region are classified according to the appropriate support structure of the detected pattern. This classification eases the transformation of a sequential application into its parallel version. Finally, we defined a metric that helps select the best suitable parallel pattern out of multiple patterns detected in the same region. We support the identification of six parallel patterns in the algorithm structure of sequential applications: pipeline, multi-loop pipeline, task parallelism, geometric decomposition, do-all and reduction. We successfully identified these patterns in applications from four different benchmark suites. We confirmed our results by comparing them with pre-existing parallel versions of these applications. We also implemented the detected patterns on our own in those cases where parallel implementations were not available and achieved considerable speedups