Simple, Accurate, Analytical Time Modeling and Optimal Tile Size Selection for GPGPU Stencils

Nirmal Prajapati, Waruna Ranasinghe, Sanjay Rajopadhye, Rumen Andonov, Hristo Djidjev, Tobias Grosser

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

Stencil computations are an important class of compute and data intensive programs that occur widely in scientific and engineeringapplications. A number of tools use sophisticated tiling, parallelization, and memory mapping strategies, and generate code that relies on vendor-supplied compilers. This code has a number of parameters, such as tile sizes, that are then tuned via empirical exploration. We develop a model that guides such a choice. Our model is a simple set of analytical functions that predict the execution time of the generated code. It is deliberately optimistic, since tile sizes and, moreover, the optimistic assumptions are intended to enable we are targeting modeling and parameter selections yielding highly tuned codes. We experimentally validate the model on a number of 2D and 3D stencil codes, and show that the root mean square error in the execution time is less than 100 script, based on using our model, we are able to predict tile sizes that achieve a further improvement of 9% on average.
Original languageEnglish
Pages (from-to)163–177
Number of pages15
JournalACM Sigplan Notices
Issue number8
Publication statusPublished - 26 Jan 2017
Event22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming - Austin, United States
Duration: 4 Feb 20178 Feb 2017

Keywords / Materials (for Non-textual outputs)

  • analytical models
  • gpgpu
  • hybrid hexagonal classic tiling
  • performance prediction
  • polyhedral method
  • stencils


Dive into the research topics of 'Simple, Accurate, Analytical Time Modeling and Optimal Tile Size Selection for GPGPU Stencils'. Together they form a unique fingerprint.

Cite this