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

Direct link
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.
UPTEC IT, ISSN 1401-5749 ; 15003
National Category
Engineering and Technology
URN: urn:nbn:se:uu:diva-252358OAI: oai:DiVA.org:uu-252358DiVA: diva2:809843
Available from: 2015-05-05 Created: 2015-05-05 Last updated: 2015-05-06Bibliographically approved

Open Access in DiVA

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

By organisation
Department of Information Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 118 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: 1584 hits
ReferencesLink to record
Permanent link

Direct link