Spiral in scala: towards the systematic construction of generators for performance libraries
Spiral in scala: towards the systematic construction of generators for performance libraries
复制标题
scala 中的螺旋：面向性能库生成器的系统构建
DOI：
10.1145/2517208.2517228
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Markus Püschel
中科院分区：
文献类型：
--
作者：
Georg Ofenbeck;Tiark Rompf;A. Stojanov;Martin Odersky;Markus Püschel
高性能库的程序生成器是解决每一代新处理器移植和优化代码时反复出现的问题的一个有吸引力的解决方案，但迄今为止，这样的生成器很少。这不仅是由于设计的困难，而且是由于实际实现的困难，这通常会导致难以扩展、维护或重用的独立程序和脚本的临时集合。在本文中，我们询问是否需要以及需要哪些编程语言概念和功能来实现此类生成器的更系统的构建。我们提倡的系统方法从现有的生成器中推断：a）使用一种或多种特定于领域的语言（DSL）描述问题和算法知识，b）将优化和选择表达为DSL程序的重写规则，c）设计可配置为控制生成的代码类型和使用的数据表示的数据结构，d）使用自动调整来选择性能最佳的替代方案。作为案例研究，我们使用轻量级模块化分段 (LMS) 框架在 Scala 中实现了一个小型但具有代表性的 Spiral 子集。本文的第一个主要贡献是实现了 c)，使用类型类对分段决策进行抽象，即立即执行哪些计算部分以及为哪些部分生成代码。具体来说，我们将不同的复杂数据表示与不同的代码表示联合抽象，包括生成循环与标量替换展开的代码——这是一个至关重要且通常乏味的性能转换。第二个主要贡献是在 LMS 框架内提供对 a) 和 d) 的全面支持：我们扩展了 LMS 以支持不同 DSL 之间的转换以及通过搜索进行自动调整。
Program 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.