000201032 001__ 201032
000201032 005__ 20181203023555.0
000201032 0247_ $$2doi$$a10.1145/2517208.2517228
000201032 022__ $$a0362-1340
000201032 02470 $$2ISI$$a000338625500015
000201032 037__ $$aARTICLE
000201032 245__ $$aSpiral in Scala: Towards the Systematic Construction of Generators for Performance Libraries
000201032 260__ $$bAssoc Computing Machinery$$c2014$$aNew York
000201032 269__ $$a2014
000201032 300__ $$a10
000201032 336__ $$aJournal Articles
000201032 520__ $$aProgram generators for high performance libraries are an appealing solution to the recurring problem of porting and optimizing code with every new processor generation, but only few such generators exist to date. This is due to not only the difficulty of the design, but also of the actual implementation, which often results in an ad-hoc collection of standalone programs and scripts that are hard to extend, maintain, or reuse. In this paper we ask whether and which programming language concepts and features are needed to enable a more systematic construction of such generators. The systematic approach we advocate extrapolates from existing generators: a) describing the problem and algorithmic knowledge using one, or several, domain-specific languages (DSLs), b) expressing optimizations and choices as rewrite rules on DSL programs, c) designing data structures that can be configured to control the type of code that is generated and the data representation used, and d) using autotuning to select the best-performing alternative. As a case study, we implement a small, but representative subset of Spiral in Scala using the Lightweight Modular Staging (LMS) framework. The first main contribution of this paper is the realization of c) using type classes to abstract over staging decisions, i.e. which pieces of a computation are performed immediately and for which pieces code is generated. Specifically, we abstract over different complex data representations jointly with different code representations including generating loops versus unrolled code with scalar replacement-a crucial and usually tedious performance transformation. The second main contribution is to provide full support for a) and d) within the LMS framework: we extend LMS to support translation between different DSLs and autotuning through search.
000201032 6531_ $$aSynthesis
000201032 6531_ $$aAbstraction over Staging
000201032 6531_ $$aSelective Precomputation
000201032 6531_ $$aScalar Replacement
000201032 6531_ $$aData Representation
000201032 700__ $$uSwiss Fed Inst Technol, Dept Comp Sci, Zurich, Switzerland$$aOfenbeck, Georg
000201032 700__ $$0243345$$g185682$$uOracle Labs, Columbus, OH USA$$aRompf, Tiark
000201032 700__ $$uSwiss Fed Inst Technol, Dept Comp Sci, Zurich, Switzerland$$aStojanov, Alen
000201032 700__ $$0241835$$g126003$$aOdersky, Martin
000201032 700__ $$uSwiss Fed Inst Technol, Dept Comp Sci, Zurich, Switzerland$$aPueschel, Markus
000201032 773__ $$j49$$tAcm Sigplan Notices$$k3$$q125-134
000201032 909C0 $$xU10409$$0252187$$pLAMP
000201032 909CO $$pIC$$particle$$ooai:infoscience.tind.io:201032
000201032 917Z8 $$x166927
000201032 937__ $$aEPFL-ARTICLE-201032
000201032 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000201032 980__ $$aARTICLE