PRT Pattern Recognition Tool

by Amin Shafiee Sarvestani, Erik Hansson, Christoph Kessler

PRT is a generic tool for automated recognition of frequently occurring (mostly, loop-based) computational patterns in C programs in the scientific and engineering computing domain.
PRT is largely based on PARAMAT recognition technology and implemented in Java on top of the Cetus compiler framework.

PRT is extensible: Patterns and their recognition rules are formally described in XML format, which parameterize the generic pattern recognition tool. Hence, new patterns and recognition rules can be added incrementally by the user. Patterns are organized in a hierarchy that folds the syntactic variations of a computation and thus keeps the set of patterns and rules compact. The tool traverses the input source program's abstract syntax tree representation and matches patterns conservatively bottom-up. Recognized subtrees are annotated with a pattern instance, indicating the detected pattern (type of computation) and its parameters.

The main purpose of the PRT tool is to help in automatically porting sequential legacy C codes for execution on special, also parallel platforms. Currently PRT comes with about 100 pre-implemented patterns, mainly from the digital signal processing domain.

PRT has a backend that can either annotate the source code with recognized patterns as comments, or replace recognized code parts with calls to C functions that may contain parallel or platform-specific implementations. An initial C backend targeting the SkePU skeleton library for hybrid multicore CPU and GPU based systems is under development.

PRT is documented in Amin Shafiee Sarvestani's master thesis and in the IJPP article listed below. The PRT source code is publically available on this page. Documentation and further references are also given below.

• Download, Installation and Usage Guidelines
• PRT JavaDoc

References

• Amin Shafiee Sarvestani, Erik Hansson, Christoph Kessler: Extensible Recognition of Algorithmic Patterns in DSP Programs for Automatic Parallelization. Int. Journal of Parallel Programming, Nov. 2012. Springer, DOI 10.1007/s10766-012-0229-2.
• Christoph W. Kessler: Pattern-Driven Automatic Parallelization. Scientific Programming vol. 5(3), pp. 251-274, 1996.
• Amin Shafiee Sarvestani: Automated recognition of algorithmic patterns in DSP programs. Master Thesis LIU-IDA/LITH-EX-A--11/052--SE, Dept. of Information and Computer Science, Linköping University, Sweden, Dec. 2011.

---

This work on PRT was partly funded by SSF (project ePUMA, 2008-2011) and by SeRC (project OpCoReS, 2012).

Page responsible: Christoph Kessler
Last updated: 2015-05-29