CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Laying Tiles Ornamentally: An approach to structuring container traversals

Nikita Frolov (Institutionen för data- och informationsteknik, Programvaruteknik (Chalmers))
Gothenburg : Chalmers University of Technology, 2016.
[Licentiatavhandling]

Having hardware more capable of parallel execution means that more program scheduling decisions have to be taken to utilize that hardware efficiently. To this end, compilers implement coarse-grained loop transformations in addition to traditionally used fine-grained instruction reordering. Implementors of embedded domain specific languages have to face a difficult choice: to translate operations on collections to a low-level language naively hoping that its optimizer will do the job, or to implement their own optimizer as a part of the EDSL.

We turn ourselves to the concept of loop tiling from the imperative world and find its equivalent for recursive functions. We show the construction of a tiled functorial map over containers that can be naively translated to a corresponding nested loop.

We illustrate the connection between untiled and tiled functorial maps by means of a type-theoretic notion of algebraic ornament. This approach produces an family of container traversals indexed by tile sizes and serves as a basis of a proof that untiled and tiled functorial maps have the same semantics.

We evaluate our approach by designing a language of tree traversals as a DSL embedded into Haskell which compiles into C code. We use this language to implement tiled and untiled tree traversals which we benchmark under varying choices of tile sizes and shapes of input trees. For some tree shapes, we show that a tiled tree traversal can be up to 50% faster than an untiled one under a good choice of the tile size.

Nyckelord: cache hierarchies, loop tiling, zippers, algebraic ornaments, parallelism,embedded domain-specific languages



Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2016-12-14. Senast ändrad 2016-12-14.
CPL Pubid: 246117

 

Läs direkt!

Lokal fulltext (fritt tillgänglig)


Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Programvaruteknik (Chalmers)

Ämnesområden

Informations- och kommunikationsteknik
Datavetenskap (datalogi)
Programvaruteknik

Chalmers infrastruktur

Examination

Datum: 2017-01-09
Tid: 14:00
Lokal: EC, EDIT-huset, Rännvägen 6, Chalmers
Opponent: Edwin Brady, University of St Andrews, Scotland, UK

Ingår i serie

Technical report L - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University 161L