Treffer: 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 a