Regular, shape-polymorphic, parallel arrays in Haskell
Regular, shape-polymorphic, parallel arrays in Haskell
复制标题
Haskell 中的规则、形状多态、并行数组
DOI：
10.1145/1863543.1863582
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
B. Lippmeier
中科院分区：
文献类型：
--
作者：
G. Keller;M. Chakravarty;Roman Leshchinskiy;S. Jones;B. Lippmeier
我们为Haskell中的常规多维阵列提供了一种新颖的方法。我们方法的主要亮点是（1）纯粹是功能性的，（2）通过形状多态性支持重复使用，（3）避免了不必要的中间结构，而不是依靠后续的环融合，并且（4）支持透明的并行性。
我们展示了如何使用类型类和类型的家庭将两种形式的形状多态性嵌入到Haskell的类型系统中。特别是，我们讨论了常规数组转换对较高等级的数组的概括，并引入了数组切片的类型安全规范。
我们讨论了三种标准阵列算法的方法的运行时性能。我们实现了与手写C代码相当的绝对性能。同时，我们的实施范围可达8个处理器内核。
We present a novel approach to regular, multi-dimensional arrays in Haskell. The main highlights of our approach are that it (1) is purely functional, (2) supports reuse through shape polymorphism, (3) avoids unnecessary intermediate structures rather than relying on subsequent loop fusion, and (4) supports transparent parallelisation.
We show how to embed two forms of shape polymorphism into Haskell's type system using type classes and type families. In particular, we discuss the generalisation of regular array transformations to arrays of higher rank, and introduce a type-safe specification of array slices.
We discuss the runtime performance of our approach for three standard array algorithms. We achieve absolute performance comparable to handwritten C code. At the same time, our implementation scales well up to 8 processor cores.