Powered by
7th ACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming (ARRAY 2021),
June 21, 2021,
Virtual, Canada
7th ACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming (ARRAY 2021)
Frontmatter
Welcome from the Chairs
Welcome to the Seventh ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming, held in association with PLDI 2021. Array-oriented programming offers a unique blend of programmer productivity and high-performance parallel execution. As an abstraction, it directly mirrors high-level mathematical constructions commonly used in many fields from natural sciences through engineering to financial modelling. As a language feature, it exposes regular control flow, exhibits structured data dependencies, and lends itself to many types of program analysis. Furthermore, many modern computer architectures, particularly highly parallel architectures such as GPUs and FPGAs, lend themselves to efficiently executing array operations. The ARRAY workshop series is intended to bring together researchers from many different communities, including language designers, library developers, compiler researchers, and practitioners, who are using or working on numeric, array-centric aspects of programming languages, libraries and methodologies from all domains: imperative or declarative; object-oriented or functional; interpreted or compiled; strongly typed, weakly typed, or untyped.
Principles
Towards Size-Dependent Types for Array Programming
Troels Henriksen and
Martin Elsman
(University of Copenhagen, Denmark)
We present a type system for expressing size constraints on array
types in an ML-style type system. The goal is to detect shape
mismatches at compile-time, while being simpler than full dependent
types. The main restrictions is that the only terms that can occur
in types are array sizes, and syntactically they must be variables
or constants. For those programs where this is not sufficient, we
support a form of existential types, with the type system
automatically managing the requisite book-keeping. We formalise a
large subset of the type system in a small core language, which we
prove sound. We also present an integration of the type system in
the high-performance parallel functional language Futhark, and show
on a collection of 44 representative programs that the restrictions
in the type system are not too problematic in practice.
@InProceedings{ARRAY21p1,
author = {Troels Henriksen and Martin Elsman},
title = {Towards Size-Dependent Types for Array Programming},
booktitle = {Proc.\ ARRAY},
publisher = {ACM},
pages = {1--14},
doi = {10.1145/3460944.3464310},
year = {2021},
}
Publisher's Version
Padding in the Mathematics of Arrays
Benjamin Chetioui, Ole Abusdal, Magne Haveraaen,
Jaakko Järvi, and Lenore Mullin
(University of Bergen, Norway; Western Norway University of Applied Sciences, Norway; University of Turku, Finland; SUNY Albany, USA)
Multi-dimensional array manipulation constitutes a core component of numerous
numerical methods, e.g. finite difference solvers of Partial Differential
Equations (PDEs). The efficiency of such computations is tightly connected to
traversing array data in a hardware-friendly way.
The Mathematics of Arrays (MoA) allows reasoning about array computations at a
high level and enables systematic transformations of array-based programs.
We have previously shown that stencil computations reduce to MoA's Denotational Normal Form (DNF).
Here we bring to light MoA's
Operational Normal Forms (ONFs) that allow for adapting array computations to
hardware characteristics. ONF transformations start from the DNF.
Alongside the ONF transformations, we extend MoA with rewriting rules
for padding. These new rules allow both a simplification of array
indexing and a systematic approach to introducing halos to PDE solvers.
Experiments on various architectures confirm the flexibility of the approach.
@InProceedings{ARRAY21p15,
author = {Benjamin Chetioui and Ole Abusdal and Magne Haveraaen and Jaakko Järvi and Lenore Mullin},
title = {Padding in the Mathematics of Arrays},
booktitle = {Proc.\ ARRAY},
publisher = {ACM},
pages = {15--26},
doi = {10.1145/3460944.3464311},
year = {2021},
}
Publisher's Version
Applications
Acceleration of Lattice Models for Pricing Portfolios of Fixed-Income Derivatives
Wojciech Michal Pawlak, Marek Hlava, Martin Metaksov, and
Cosmin Eugen Oancea
(SimCorp, Denmark; University of Copenhagen, Denmark)
This paper reports on the acceleration of a standard, lattice-based numerical algorithm that is widely used in finance for pricing a class of fixed-income vanilla derivatives.
We start with a high-level algorithmic specification, exhibiting irregular nested parallelism, which is challenging to map efficiently to GPU hardware. From it we systematically derive and optimize two CUDA implementations, which utilize only the outer or all levels of parallelism, respectively. A detailed evaluation demonstrates (i) the high impact of the proposed optimizations, (ii) the complementary strength and weaknesses of the two GPU versions, and that (iii) they are on average 2.4× faster than our well-tuned CPU-parallel implementation (OpenMP+AVX2) running on 104 hardware threads, and by 3-to-4 order of magnitude faster than an OpenMP-parallel implementation using the popular QuantLib library.
@InProceedings{ARRAY21p27,
author = {Wojciech Michal Pawlak and Marek Hlava and Martin Metaksov and Cosmin Eugen Oancea},
title = {Acceleration of Lattice Models for Pricing Portfolios of Fixed-Income Derivatives},
booktitle = {Proc.\ ARRAY},
publisher = {ACM},
pages = {27--38},
doi = {10.1145/3460944.3464309},
year = {2021},
}
Publisher's Version
Array Languages Make Neural Networks Fast
Artjoms Šinkarovs,
Hans-Nikolai Vießmann, and
Sven-Bodo Scholz
(Heriot-Watt University, UK; Radboud University Nijmegen, Netherlands)
Most implementations of machine learning algorithms are based on special-purpose frameworks such as TensorFlow or PyTorch. While these frameworks are convenient to use, they introduce multi-million lines of code dependency that one has to trust, understand and potentially modify. As an alternative, this paper investigates a direct implementation of a state of the art Convolutional Neural Network (CNN) in an array language. While our implementation requires 150 lines of code to define the special-purpose operators needed for CNNs, which are readily provided through frameworks such as TensorFlow and PyTorch, our implementation outperforms these frameworks by factors 2 and 3 on a fixed set of hardware — a 64-core GPU-accelerated machine; for a simple example network. The resulting specification is written in a rank-polymorphic data-parallel style, and it can be immediately leveraged by optimising compilers. Indeed, array languages make neural networks fast.
@InProceedings{ARRAY21p39,
author = {Artjoms Šinkarovs and Hans-Nikolai Vießmann and Sven-Bodo Scholz},
title = {Array Languages Make Neural Networks Fast},
booktitle = {Proc.\ ARRAY},
publisher = {ACM},
pages = {39--50},
doi = {10.1145/3460944.3464312},
year = {2021},
}
Publisher's Version
proc time: 1.09