Using Template Matching to Infer Parallel Design Patterns
Open Access
- 9 January 2015
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Architecture and Code Optimization
- Vol. 11 (4) , 1-21
Abstract
The triumphant spread of multicore processors over the past decade increases the pressure on software developers to exploit the growing amount of parallelism available in the hardware. However, writing parallel programs is generally challenging. For sequential programs, the formulation of design patterns marked a turning point in software development, boosting programmer productivity and leading to more reusable and maintainable code. While the literature is now also reporting a rising number of parallel design patterns, programmers confronted with the task of parallelizing an existing sequential program still struggle with the question of which parallel pattern to apply where in their code. In this article, we show how template matching, a technique traditionally used in the discovery of sequential design patterns, can also be used to support parallelization decisions. After looking for matches in a previously extracted dynamic dependence graph, we classify code blocks of the input program according to the structure of the parallel patterns we find. Based on this information, the programmer can easily implement the detected pattern and create a parallel version of his or her program. We tested our approach with six programs, in which we successfully detected pipeline and do-all patterns.Keywords
This publication has 24 references indexed in Scilit:
- Integrating profile-driven parallelism detection and machine-learning-based mappingACM Transactions on Architecture and Code Optimization, 2014
- HarmonyACM SIGARCH Computer Architecture News, 2012
- HELIX2012
- Design patterns detection using SOP expressions for graphsACM SIGSOFT Software Engineering Notes, 2011
- A profile-based tool for finding pipeline parallelism in sequential programsParallel Computing, 2010
- Towards a holistic approach to auto-parallelizationACM SIGPLAN Notices, 2009
- Parallel-stage decoupled software pipelining2008
- Design Pattern Detection by Using Meta PatternsIEICE Transactions on Information and Systems, 2008
- Design pattern detection by template matching2008
- Function level parallelism driven by data dependenciesACM SIGARCH Computer Architecture News, 2007