### Skapa referens, olika format (klipp och klistra)

**Harvard**

Frolov, N. (2016) *Laying Tiles Ornamentally: An approach to structuring container traversals*. Gothenburg : Chalmers University of Technology (Technical report L - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University, nr: 161L).

** BibTeX **

@book{

Frolov2016,

author={Frolov, Nikita},

title={Laying Tiles Ornamentally: An approach to structuring container traversals},

abstract={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.<br /><br />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 <em>tiled</em> functorial map over containers that can be naively translated to a corresponding nested loop.<br /><br />We illustrate the connection between <em>untiled</em> and tiled functorial maps by means of a type-theoretic notion of <em>algebraic ornament</em>. This approach produces an family of container traversals indexed by <em>tile sizes</em> and serves as a basis of a proof that untiled and tiled functorial maps have the same semantics.<br /><br />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.},

publisher={Institutionen för data- och informationsteknik, Programvaruteknik (Chalmers), Chalmers tekniska högskola,},

place={Gothenburg},

year={2016},

series={Technical report L - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University, no: 161L},

keywords={cache hierarchies, loop tiling, zippers, algebraic ornaments, parallelism,embedded domain-specific languages},

}

** RefWorks **

RT Dissertation/Thesis

SR Electronic

ID 246117

A1 Frolov, Nikita

T1 Laying Tiles Ornamentally: An approach to structuring container traversals

YR 2016

AB 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.<br /><br />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 <em>tiled</em> functorial map over containers that can be naively translated to a corresponding nested loop.<br /><br />We illustrate the connection between <em>untiled</em> and tiled functorial maps by means of a type-theoretic notion of <em>algebraic ornament</em>. This approach produces an family of container traversals indexed by <em>tile sizes</em> and serves as a basis of a proof that untiled and tiled functorial maps have the same semantics.<br /><br />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.

PB Institutionen för data- och informationsteknik, Programvaruteknik (Chalmers), Chalmers tekniska högskola,

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

LA eng

LK http://publications.lib.chalmers.se/records/fulltext/246117/246117.pdf

OL 30