Show simple item record

dc.contributor.advisorBondhugula, Uday
dc.contributor.authorBandishti, Vinayaka Prakasha
dc.date.accessioned2017-05-21T11:42:33Z
dc.date.accessioned2018-07-31T04:38:36Z
dc.date.available2017-05-21T11:42:33Z
dc.date.available2018-07-31T04:38:36Z
dc.date.issued2017-05-21
dc.date.submitted2013
dc.identifier.urihttp://etd.iisc.ac.in/handle/2005/2619
dc.identifier.abstracthttp://etd.iisc.ac.in/static/etd/abstracts/3407/G26301-Abs.pdfen_US
dc.description.abstractStencil computations are iterative kernels often used to simulate the change in a discretized spatial domain overtime (e.g., computational fluid dynamics) or to solve for unknowns in a discretized space by converging to a steady state (i.e., partial differential equations).They are commonly found in many scientific and engineering applications. Most stencil computations allow tile-wise concurrent start ,i.e., there exists a face of the iteration space and a set of tiling hyper planes such that all tiles along that face can be started concurrently. This provides load balance and maximizes parallelism. Loop tiling is a key transformation used to exploit both data locality and parallelism from stencils simultaneously. Numerous works exist that target improving locality, controlling frequency of synchronization, and volume of communication wherever applicable. But, concurrent start-up of tiles that evidently translates into perfect load balance and often reduction in frequency of synchronization is completely ignored. Existing automatic tiling frameworks often choose hyperplanes that lead to pipelined start-up and load imbalance. We address this issue with a new tiling technique that ensures concurrent start-up as well as perfect load balance whenever possible. We first provide necessary and sufficient conditions on tiling hyperplanes to enable concurrent start for programs with affine data accesses. We then discuss an iterative approach to find such hyperplanes. It is not possible to directly apply automatic tiling techniques to periodic stencils because of the wrap-around dependences in them. To overcome this, we use iteration space folding techniques as a pre-processing stage after which our technique can be applied without any further change. We have implemented our techniques on top of Pluto-a source-level automatic parallelizer. Experimental evaluation on a 12-core Intel Westmere shows that our code is able to outperform a tuned domain-specific stencil code generator by 4% to2 x, and previous compiler techniques by a factor of 1.5x to 15x. For the swim benchmark from SPECFP2000, we achieve an .improvement of 5.12 x on a 12-core Intel Westmere and 2.5x on a 16-core AMD Magny-Cours machines, over the auto-parallelizer of Intel C Compiler.en_US
dc.language.isoen_USen_US
dc.relation.ispartofseriesG26301en_US
dc.subjectStencil Computationsen_US
dc.subjectConcurrent Start-Upen_US
dc.subjectTiling Hyperplanesen_US
dc.subjectPeriodic Stencilsen_US
dc.subjectCompilers (Computer Programs)en_US
dc.subjectMultiprocessorsen_US
dc.subjectComputer Architectureen_US
dc.subjectParallelism (Computer Architecture)en_US
dc.subjectTiling Stencil Computationsen_US
dc.subjectAutomatic Parallelizersen_US
dc.subjectPluto-Source Level Automatic Parallelizeren_US
dc.subject.classificationComputer Scienceen_US
dc.titleTiling Stencil Computations To Maximize Parallelismen_US
dc.typeThesisen_US
dc.degree.nameMSc Enggen_US
dc.degree.levelMastersen_US
dc.degree.disciplineFaculty of Engineeringen_US


Files in this item

This item appears in the following Collection(s)

Show simple item record