Static Partitioning of Spreadsheets for Parallel Execution
- Alexander Bock
Research Output:
Conference Article in Proceeding or Book/Report chapter
Article in proceedings
Peer-review
Open access
Publication Information
Output type
Research Output:
Conference Article in Proceeding or Book/Report chapter
Article in proceedings
Peer-reviewHost publication Subtitle
21th International Symposium, PADL 2019, Lisbon, Portugal, January 14-15, 2019, ProceedingsOriginal language
EnglishPages from-to (Number of pages)
Pages 221-237 (17 pages)Publication milestones
- Published - 19/12/2018
Publication status
Published - 19/12/2018
Publisher
Springer, United States, GermanyBook series
- Book series name: Lecture Notes in Computer Science
Volume: 11372
ISSN: 0302-9743
ISBN (Print)
978-3-030-05997-2ISBN (Electronic)
978-3-030-05998-9Publication IDs
- Scopus: 85059670019
Host publication title
Practical Aspects of Declarative LanguagesHost publication editors
- José J. Alferes
- Moa Johansson
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.
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.
Publication metrics
PlumX, opens in new tab
Citations
2
Access to documents
Submitted manuscript, 315.28 KB