Array Structures and Data-parallel Algorithms Array Structures and Data-parallel Algorithms
A sub-category of array gCDS is constructed preserved by exponentiation through isomorphisms relating higher-order objects to their local parts, which brings notions of data locality, synchronisation and denotational semantics in a uniied framework.
Abstract
We apply Brookes and Geva's theory of generalised concrete data structures and computational co-monads to the semantics of higher-order data-parallel functional languages. This yields a mathematical framework for describing the interaction between higher-order functions, explicitly distributed data and asyn-chronous algorithms. Concrete data structures (or CDS) allow the construction of several Cartesian closed categories, standard models for typed functional languages. Brookes and Geva have studied generalised CDSs and so-called parallel algorithms as meanings for lambda-calculus terms. An input-output function may correspond to many algorithms. Their construction is adapted to data-parallel functional languages through concrete array structures with explicit data layout. We construct a sub-category of array gCDS preserved by exponentiation through isomorphisms relating higher-order objects to their local parts. This formalism brings notions of data locality, synchronisation and denotational semantics in a uniied framework.