Static Partitioning of Spreadsheets for Parallel Execution

Alexander Bock

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review

Abstract

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.
Original languageEnglish
Title of host publicationPractical Aspects of Declarative Languages : 21th International Symposium, PADL 2019, Lisbon, Portugal, January 14-15, 2019, Proceedings
EditorsJosé J. Alferes, Moa Johansson
Number of pages17
PublisherSpringer
Publication date19 Dec 2018
Pages221-237
ISBN (Print)978-3-030-05997-2
ISBN (Electronic)978-3-030-05998-9
DOIs
Publication statusPublished - 19 Dec 2018
SeriesLecture Notes in Computer Science
Volume11372
ISSN0302-9743

Keywords

  • Spreadsheets
  • Partitioning
  • Parallelism

Fingerprint

Dive into the research topics of 'Static Partitioning of Spreadsheets for Parallel Execution'. Together they form a unique fingerprint.

Cite this