Single Assignment C (SAC) The Compilation Technology Perspective

Single Assignment C (SaC) is a data parallel programming language that combines an imperative looking syntax, closely resembling that of C, with purely functional, state-free semantics. Again unlike the functional programming mainstream, that puts the emphasis on lists and trees, the focus of SaC as a data-parallel language is on (truly) multi-dimensional arrays. SaC arrays are not just loose collections of data cells or memory address ranges as in many imperative and object-oriented languages. Neither are they explicitly managed, stateful data objects as in some functional languages, may it be for language design or for performance considerations. SaC arrays are indeed purely functional, immutable, state-free, first-class values.

The array type system of SaC allows functions to abstract not only from the size of vectors or matrices but even from the number of array dimensions. Programs can and should be written in a mostly index-free style with functions consuming entire arrays as arguments and producing entire arrays as results. SaC supports a highly generic and compositional programming style that composes applications in layers of abstractions from universally applicable building blocks. The design of SaC aims at combining high productivity in software engineering of compute-intensive applications with high performance in program execution on today’s multi- and many-core computing systems.

These CEFP lecture notes provide a balanced introduction to language design and programming methodology of SaC, but our main focus is on the in-depth description and illustration of the associated compilation technology. It is literally a long way down from state-free, functional program code involving multi-dimensional, truly state-free arrays to efficient execution on modern computing machines. Fully compiler-directed parallelisation for symmetric multi-socket, multi-core, hyper-threaded server systems, CUDA-enabled graphics accelerators, workstation clusters or heterogeneous systems from a single architecture-agnostic source program adds a fair deal of complexity. Over the years, we have developed an intricate program transformation and optimisation machinery for this purpose. These lecture notes provide the first comprehensive presentation of our compilation technology as a whole.