liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Automated Recognition of Algorithmic Patterns in DSP Programs
Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory. Linköping University, The Institute of Technology.
2011 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
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.

Place, publisher, year, edition, pages
2011. , 152 p.
Keyword [en]
Automatic Parallelization, Algorithmic Pattern Recognition, Cetus, DSP, DSP Code Parallelization, Compiler Frameworks
National Category
Computer Science
URN: urn:nbn:se:liu:diva-73934ISRN: LIU-IDA/LITH-EX-A—11/052—SEOAI: diva2:478754
Subject / course
Master's programme in Computer Science
2011-12-21, SE-581 83 LINKÖPING, Linköping, 13:15 (English)
Available from: 2012-01-17 Created: 2012-01-16 Last updated: 2012-01-17Bibliographically approved

Open Access in DiVA

fulltext(3890 kB)257 downloads
File information
File name FULLTEXT01.pdfFile size 3890 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
PELAB - Programming Environment LaboratoryThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 257 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 787 hits
ReferencesLink to record
Permanent link

Direct link