Automated Recognition of Algorithmic Patterns in DSP Programs
Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
We introduce an extensible knowledge based tool for idiom (pattern) recognition in DSP(digital signal processing) programs. Our tool utilizesfunctionality provided by the Cetus compiler infrastructure fordetecting certain computation patterns that frequently occurin DSP code. We focus on recognizing patterns for for-loops andstatements in their bodies as these often are the performance criticalconstructs in DSP applications for which replacementby highly optimized, target-specific parallel algorithms will bemost profitable. For better structuring and efficiency of patternrecognition, we classify patterns by different levels of complexitysuch that patterns in higher levels are defined in terms of lowerlevel patterns.The tool works statically on the intermediate representation(IR). It traverses the abstract syntax tree IR in post-orderand applies bottom-up pattern matching, at each IR nodeutilizing information about the patterns already matched for itschildren or siblings.For better extensibility and abstraction,most of the structuralpart of recognition rules is specified in XML form to separatethe tool implementation from the pattern specifications.Information about detected patterns will later be used foroptimized code generation by local algorithm replacement e.g. for thelow-power high-throughput multicore DSP architecture ePUMA.
Place, publisher, year, edition, pages
2011. , 152 p.
Automatic Parallelization, Algorithmic Pattern Recognition, Cetus, DSP, DSP Code Parallelization, Compiler Frameworks
National CategoryComputer Science
IdentifiersURN: urn:nbn:se:liu:diva-73934ISRN: LIU-IDA/LITH-EX-A—11/052—SEOAI: oai:DiVA.org:liu-73934DiVA: diva2:478754
Subject / course
Master's programme in Computer Science
2011-12-21, SE-581 83 LINKÖPING, Linköping, 13:15 (English)