Static Partitioning of Spreadsheets for Parallel Execution

Spreadsheets are popular tools for end-user development and complex odelling
but can suffer from poor performance. While end-users are usually domain
experts they are seldom IT professionals that can leverage today's abundant
multicore architectures to offset such poor performance. We present an iterative, greedy algorithm for automatically partitioning spreadsheets into load-balanced, acyclic groups of cells that can be scheduled to run on shared-memory multicore processors. A big-step cost semantics for the spreadsheet formula language is used to estimate work and guide partitioning.
The algorithm does not require end-users to modify the spreadsheet in any way.
We implement three extensions to the algorithm for further accelerating
computation; two of which recognise common cell structures known as cell arrays that naturally express a degree of parallelism. To the best of our knowledge, no such automatic algorithm has previously been proposed for partitioning spreadsheets. We report a maximum 24-fold speed-up on 48 logical cores.