Static Partitioning of Spreadsheets for Parallel Execution

Alexander Bock

doi:10.1007/978-3-030-05998-9_14

Static Partitioning of Spreadsheets for Parallel Execution

Alexander Bock

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-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 language	English
Title of host publication	Practical Aspects of Declarative Languages : 21th International Symposium, PADL 2019, Lisbon, Portugal, January 14-15, 2019, Proceedings
Editors	José J. Alferes, Moa Johansson
Number of pages	17
Publisher	Springer
Publication date	19 Dec 2018
Pages	221-237
ISBN (Print)	978-3-030-05997-2
ISBN (Electronic)	978-3-030-05998-9
DOIs	https://doi.org/10.1007/978-3-030-05998-9_14
Publication status	Published - 19 Dec 2018

Series	Lecture Notes in Computer Science
Volume	11372
ISSN	0302-9743

Keywords

Spreadsheets
Partitioning
Parallelism

Access to Document

10.1007/978-3-030-05998-9_14

static_partitioningSubmitted manuscript, 315 KB

P3: Popular parallel programming
Sestoft, P. (PI), Bock, A. A. (CoI) & Biermann, F. (CoI)
Independent Research Fund Denmark
01/02/2015 → 23/03/2019
Project: Research

Cite this

@inproceedings{d34d4733eb8549bb93a84553a070f3ea,

title = "Static Partitioning of Spreadsheets for Parallel Execution",

abstract = "Spreadsheets are popular tools for end-user development and complex odellingbut can suffer from poor performance. While end-users are usually domainexperts they are seldom IT professionals that can leverage today's abundantmulticore 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 acceleratingcomputation; 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.",

keywords = "Spreadsheets, Partitioning, Parallelism, Spreadsheets, Partitioning, Parallelism",

author = "Alexander Bock",

year = "2018",

month = dec,

day = "19",

doi = "10.1007/978-3-030-05998-9_14",

language = "English",

isbn = "978-3-030-05997-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "221--237",

editor = "Alferes, {Jos{\'e} J.} and Moa Johansson",

booktitle = "Practical Aspects of Declarative Languages",

address = "Germany",

}

Static Partitioning of Spreadsheets for Parallel Execution. / Bock, Alexander.
Practical Aspects of Declarative Languages: 21th International Symposium, PADL 2019, Lisbon, Portugal, January 14-15, 2019, Proceedings. ed. / José J. Alferes; Moa Johansson. Springer, 2018. p. 221-237 (Lecture Notes in Computer Science, Vol. 11372).

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

TY - GEN

T1 - Static Partitioning of Spreadsheets for Parallel Execution

AU - Bock, Alexander

PY - 2018/12/19

Y1 - 2018/12/19

N2 - Spreadsheets are popular tools for end-user development and complex odellingbut can suffer from poor performance. While end-users are usually domainexperts they are seldom IT professionals that can leverage today's abundantmulticore 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 acceleratingcomputation; 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.

AB - Spreadsheets are popular tools for end-user development and complex odellingbut can suffer from poor performance. While end-users are usually domainexperts they are seldom IT professionals that can leverage today's abundantmulticore 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 acceleratingcomputation; 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.

KW - Spreadsheets

KW - Partitioning

KW - Parallelism

KW - Spreadsheets

KW - Partitioning

KW - Parallelism

U2 - 10.1007/978-3-030-05998-9_14

DO - 10.1007/978-3-030-05998-9_14

M3 - Article in proceedings

SN - 978-3-030-05997-2

T3 - Lecture Notes in Computer Science

SP - 221

EP - 237

BT - Practical Aspects of Declarative Languages

A2 - Alferes, José J.

A2 - Johansson, Moa

PB - Springer

ER -

Static Partitioning of Spreadsheets for Parallel Execution

Abstract

Keywords

Access to Document

Fingerprint

Projects

P3: Popular parallel programming

Cite this