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

Direct link
Automated Recognition of Algorithmic Patterns in DSP Programs
2011 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudentuppsats (Examensarbete)
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, pages
2011. 152 p.
Keyword [en]
Automatic Parallelization, Algorithmic Pattern Recognition, Cetus, DSP, DSP Code Parallelization, Compiler Frameworks
National Category
Computer Science
Identifiers
urn:nbn:se:liu:diva-73934 (URN)LIU-IDA/LITH-EX-A—11/052—SE (ISRN)oai:DiVA.org:liu-73934 (OAI)
Subject / course
Master's programme in Computer Science
Presentation
2011-12-21, SE-581 83 LINKÖPING, Linköping, 13:15 (English)
Uppsok
Technology
Supervisors
Examiners
Available from2012-01-17 Created:2012-01-16 Last updated:2012-01-17Bibliographically approved

Open Access in DiVA

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

Search in DiVA

By author/editor
Shafiee Sarvestani, Amin
By organisation
PELAB - Programming Environment LaboratoryThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Totalt: 160 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
Totalt: 178 hits
ReferencesLink to record
Permanent link

Direct link