Size slicing: a hybrid approach to size inference in futhark

TY - GEN

T1 - Size slicing

T2 - ACM-SIGPLAN Workshop on Functional High-Performance Computing (FHPC) 2014

AU - Henriksen, Troels

AU - Elsman, Martin

AU - Oancea, Cosmin Eugen

N1 - Conference code: 3

PY - 2014/9/3

Y1 - 2014/9/3

N2 - We present a shape inference analysis for a purely-functional language, named Futhark, that supports nested parallelism via array combinators such as map, reduce, filter, and scan. Our approach is to infer code for computing precise shape information at run-time, which in the most common cases can be effectively optimized by standard compiler optimizations. Instead of restricting the language or sacrificing ease of use, the language allows the occasional shape-dynamic, and even shape-misbehaving, constructs. Inherently shape-dynamic code is treated with a fall-back technique that preserves, asymptotically, the number of operations of the program and that computes and returns the array's shape alongside with its value. This approach leads to a shape-dependent system with existentially-quantified types, where static shape inference corresponds to eliminating existential quantifications from the types of program expressions. We optimize the common case to negligible overhead via size slicing: a technique that separates the computation of the array's shape from its values. This allows the shape to be calculated in advance and to be used to instantiate the previously existentiallyquantified shapes of the value slice. We report negligible overhead, on several mini-benchmarks and three real-world applications. Copyright is held by the owner/author(s).

AB - We present a shape inference analysis for a purely-functional language, named Futhark, that supports nested parallelism via array combinators such as map, reduce, filter, and scan. Our approach is to infer code for computing precise shape information at run-time, which in the most common cases can be effectively optimized by standard compiler optimizations. Instead of restricting the language or sacrificing ease of use, the language allows the occasional shape-dynamic, and even shape-misbehaving, constructs. Inherently shape-dynamic code is treated with a fall-back technique that preserves, asymptotically, the number of operations of the program and that computes and returns the array's shape alongside with its value. This approach leads to a shape-dependent system with existentially-quantified types, where static shape inference corresponds to eliminating existential quantifications from the types of program expressions. We optimize the common case to negligible overhead via size slicing: a technique that separates the computation of the array's shape from its values. This allows the shape to be calculated in advance and to be used to instantiate the previously existentiallyquantified shapes of the value slice. We report negligible overhead, on several mini-benchmarks and three real-world applications. Copyright is held by the owner/author(s).

U2 - 10.1145/2636228.2636238

DO - 10.1145/2636228.2636238

M3 - Article in proceedings

SP - 31

EP - 42

BT - Proceedings of the 3rd ACM SIGPLAN workshop on Functional High-Performance Computing

PB - Association for Computing Machinery

Y2 - 1 September 2014

ER -