uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Stencil Computation Auto-Tuning via Dataflow Graph Transformations
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology.
2015 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Fine-tuning of optimizations such as loop tiling and array padding is typically required in order to achieve good performance in memory-intensive numerical applications on current computer architectures. Auto-tuning techniques can automate this traditionally laborious task and achieve good performance, but the techniques have so far been application-specific and difficult to adapt to new applications. This thesis investigates developing a framework and language supporting a more general purpose auto-tuner. A high level language capable of expressing programs that deal with multi-dimensional arrays was created to serve as a program representation for use with the auto-tuner. The language is based on the dataflow model where a program is represented as a directed graph describing the flow of data between operations, and uses a novel iteration model based on a hierarchy of flows leading to simple representations of certain loop tiling and parallelization transformations. The iteration construct proved useful by allowing composition of tiling and parallelization transformations, but may not have been a good choice since it made it difficult to validate transformation opportunities. The auto-tuner was evaluated by applying it to a simple stencil computation program. It was confirmed that memory access optimizations do matter for parallel stencil computations on mainstream multicore architectures, and that the impact of optimizations is architecture-dependent. Auto-tuning was shown to be a useful strategy for applying a range of parameterized optimizations. The presented auto-tuner lacks an algorithm for identifying valid optimization opportunities, and must be told what transformations to apply and where to apply them. Still, the use of a high-level dataflow language did simplify auto-tuning by removing the need for writing a program-specific code generator.

Place, publisher, year, edition, pages
2015. , 69 p.
Series
UPTEC IT, ISSN 1401-5749 ; 15003
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:uu:diva-252358OAI: oai:DiVA.org:uu-252358DiVA: diva2:809843
Supervisors
Examiners
Available from: 2015-05-05 Created: 2015-05-05 Last updated: 2015-05-06Bibliographically approved

Open Access in DiVA

fulltext(2971 kB)179 downloads
File information
File name FULLTEXT02.pdfFile size 2971 kBChecksum SHA-512
42e4e982bbe3f89268b65f673dad78032f7324d1168b8ea7bcf270abbb09d49269217f62b8a0b68af8c899912b0684ac39eb6062437776697b386d1c58166029
Type fulltextMimetype application/pdf

By organisation
Department of Information Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 180 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

urn-nbn

Altmetric score

urn-nbn
Total: 1791 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf