Data-Parallel Spreadsheet Programming

Spreadsheets are used in industry and academia across all domains and their application ranges from simple accounting to sequencing of amino acids. Some businesses re-use and extend spreadsheets over years and not only complexity but also performance becomes a problem.

In the last two decades, parallel shared-memory multiprocessor computers have become abundant, but they remain notoriously difficult to program correctly. Therefore, it is often not possible for end-users to make full use of their parallel hardware. Declarative, functional programming languages are an alternative to imperative programming languages that makes programming shared-memory multiprocessors much easier: due to the absence of side effects in these languages, compilers and libraries can parallelize programs automatically. The formula language of spreadsheets is a declarative, first-order functional language and therefore potentially allows for an automatic parallelization of spreadsheet calculations.

This thesis explores the design space of automatically parallelizing spreadsheet recalculations. Often times, computations in spreadsheets are structured in a way that corresponds to declarative high-level programming on arrays. Therefore, the focus of this thesis lies on practical data-parallelism in a spreadsheet model of computations. This thesis makes the following contributions:
• we show how to automatically re-write high-level spreadsheet
structures into higher-order functional programs for parallel
execution;
• we contrast and combine our re-writing technique with a
recalculation algorithm that dynamically exploits dataflow
parallelism in spreadsheets;
• we describe a representation of two-dimensional arrays that
pragmatically caters to the needs of high-level array programming; and
• we explore a hypothetical approach to array fusion and laziness in a purely functional, strict spreadsheet language.