LiU Electronic Press
Download:
File size:
3890 kb
Format:
application/pdf
Author:
Shafiee Sarvestani, Amin (Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory) (Linköping University, The Institute of Technology)
Title:
Automated Recognition of Algorithmic Patterns in DSP Programs
Department:
Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory
Linköping University, The Institute of Technology
Publication type:
Student thesis
Language:
English
Level:
Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE credits
Undergraduate subject:
Master's programme in Computer Science
Uppsok:
Technology
Pages:
152
Year of publ.:
2011
URI:
urn:nbn:se:liu:diva-73934
Permanent link:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-73934
ISRN:
LIU-IDA/LITH-EX-A—11/052—SE
Subject category:
Computer Science
Keywords(en) :
Automatic Parallelization, Algorithmic Pattern Recognition, Cetus, DSP, DSP Code Parallelization, Compiler Frameworks
Abstract(en) :

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.

Presentation:
2011-12-21, SE-581 83 LINKÖPING, Linköping, 13:15 (English)
Supervisor:
Hansson, Erik (Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory)
Examiner:
Kessler, Christoph
Available from:
2012-01-17
Created:
2012-01-16
Last updated:
2012-01-17
Statistics:
177 hits
FILE INFORMATION
File size:
3890 kb
Mimetype:
application/pdf
Type:
fulltext
Statistics:
157 hits