Beyond Data Parallelism : Identifying parallel tasks in sequential programs

Zhen Li; Bo Zhao; Ali Jannesari; Felix Wolf

doi:10.1007/978-3-319-27140-8_39

Beyond Data Parallelism : Identifying parallel tasks in sequential programs

Zhen Li^*, Bo Zhao, Ali Jannesari, Felix Wolf

^*Corresponding author for this work

Not published at Aalto University

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

1 Citation (Scopus)

Abstract

Today, millions of legacy programs are awaiting their parallelization. For this reason, the automatic discovery of parallelism in sequential programs is now receiving considerable attention. However, past efforts mainly concentrated on data parallelism hidden inside loops. As programming models begin to support more irregular types of parallelism, centered around the notion of tasks in various forms, methods are needed to identify code sections that could potentially represent parallel tasks. In this paper, we present a novel approach to automatically finding parallel tasks in sequential programs. We first created a dynamic dependence graph, then isolated tasks, and finally produced a task graph according to the dependences we find. With the help of a source-to-source code translator, parallel code is automatically generated. We conducted a range of experiments to cover both tasks executing the same code and tasks executing different code. Results showed that our method achieved reasonable speedups on the test cases.

Original language	English
Title of host publication	Algorithms and Architectures for Parallel Processing - 15th International Conference, ICA3PP 2015, Proceedings
Editors	Albert Zomaya, Gregorio Martinez Perez, Kenli Li, Guojun Wang
Publisher	Springer
Pages	569-582
Number of pages	14
ISBN (Print)	9783319271392
DOIs	https://doi.org/10.1007/978-3-319-27140-8_39
Publication status	Published - 2015
MoE publication type	A4 Conference publication
Event	International Conference on Algorithms and Architectures for Parallel Processing - Zhangjiajie, China Duration: 18 Nov 2015 → 20 Nov 2015 Conference number: 15

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9531
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Conference on Algorithms and Architectures for Parallel Processing
Abbreviated title	ICA3PP
Country/Territory	China
City	Zhangjiajie
Period	18/11/2015 → 20/11/2015

Keywords

Computational unit
Data dependence
Parallel programming
Parallelism discovery
Task parallelism

Access to Document

10.1007/978-3-319-27140-8_39

Cite this

Li, Z., Zhao, B., Jannesari, A., & Wolf, F. (2015). Beyond Data Parallelism : Identifying parallel tasks in sequential programs. In A. Zomaya, G. M. Perez, K. Li, & G. Wang (Eds.), Algorithms and Architectures for Parallel Processing - 15th International Conference, ICA3PP 2015, Proceedings (pp. 569-582). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9531). Springer. https://doi.org/10.1007/978-3-319-27140-8_39

Li, Zhen ; Zhao, Bo ; Jannesari, Ali et al. / Beyond Data Parallelism : Identifying parallel tasks in sequential programs. Algorithms and Architectures for Parallel Processing - 15th International Conference, ICA3PP 2015, Proceedings. editor / Albert Zomaya ; Gregorio Martinez Perez ; Kenli Li ; Guojun Wang. Springer, 2015. pp. 569-582 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{5995a0711fe6433084a5fd0f7abde74a,

title = "Beyond Data Parallelism : Identifying parallel tasks in sequential programs",

abstract = "Today, millions of legacy programs are awaiting their parallelization. For this reason, the automatic discovery of parallelism in sequential programs is now receiving considerable attention. However, past efforts mainly concentrated on data parallelism hidden inside loops. As programming models begin to support more irregular types of parallelism, centered around the notion of tasks in various forms, methods are needed to identify code sections that could potentially represent parallel tasks. In this paper, we present a novel approach to automatically finding parallel tasks in sequential programs. We first created a dynamic dependence graph, then isolated tasks, and finally produced a task graph according to the dependences we find. With the help of a source-to-source code translator, parallel code is automatically generated. We conducted a range of experiments to cover both tasks executing the same code and tasks executing different code. Results showed that our method achieved reasonable speedups on the test cases.",

keywords = "Computational unit, Data dependence, Parallel programming, Parallelism discovery, Task parallelism",

author = "Zhen Li and Bo Zhao and Ali Jannesari and Felix Wolf",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP ; Conference date: 18-11-2015 Through 20-11-2015",

year = "2015",

doi = "10.1007/978-3-319-27140-8_39",

language = "English",

isbn = "9783319271392",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "569--582",

editor = "Albert Zomaya and Perez, {Gregorio Martinez} and Kenli Li and Guojun Wang",

booktitle = "Algorithms and Architectures for Parallel Processing - 15th International Conference, ICA3PP 2015, Proceedings",

address = "Germany",

}

Li, Z, Zhao, B, Jannesari, A & Wolf, F 2015, Beyond Data Parallelism : Identifying parallel tasks in sequential programs. in A Zomaya, GM Perez, K Li & G Wang (eds), Algorithms and Architectures for Parallel Processing - 15th International Conference, ICA3PP 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9531, Springer, pp. 569-582, International Conference on Algorithms and Architectures for Parallel Processing, Zhangjiajie, China, 18/11/2015. https://doi.org/10.1007/978-3-319-27140-8_39

Beyond Data Parallelism : Identifying parallel tasks in sequential programs. / Li, Zhen; Zhao, Bo; Jannesari, Ali et al.
Algorithms and Architectures for Parallel Processing - 15th International Conference, ICA3PP 2015, Proceedings. ed. / Albert Zomaya; Gregorio Martinez Perez; Kenli Li; Guojun Wang. Springer, 2015. p. 569-582 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9531).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - Beyond Data Parallelism : Identifying parallel tasks in sequential programs

AU - Li, Zhen

AU - Zhao, Bo

AU - Jannesari, Ali

AU - Wolf, Felix

N1 - Conference code: 15

PY - 2015

Y1 - 2015

N2 - Today, millions of legacy programs are awaiting their parallelization. For this reason, the automatic discovery of parallelism in sequential programs is now receiving considerable attention. However, past efforts mainly concentrated on data parallelism hidden inside loops. As programming models begin to support more irregular types of parallelism, centered around the notion of tasks in various forms, methods are needed to identify code sections that could potentially represent parallel tasks. In this paper, we present a novel approach to automatically finding parallel tasks in sequential programs. We first created a dynamic dependence graph, then isolated tasks, and finally produced a task graph according to the dependences we find. With the help of a source-to-source code translator, parallel code is automatically generated. We conducted a range of experiments to cover both tasks executing the same code and tasks executing different code. Results showed that our method achieved reasonable speedups on the test cases.

AB - Today, millions of legacy programs are awaiting their parallelization. For this reason, the automatic discovery of parallelism in sequential programs is now receiving considerable attention. However, past efforts mainly concentrated on data parallelism hidden inside loops. As programming models begin to support more irregular types of parallelism, centered around the notion of tasks in various forms, methods are needed to identify code sections that could potentially represent parallel tasks. In this paper, we present a novel approach to automatically finding parallel tasks in sequential programs. We first created a dynamic dependence graph, then isolated tasks, and finally produced a task graph according to the dependences we find. With the help of a source-to-source code translator, parallel code is automatically generated. We conducted a range of experiments to cover both tasks executing the same code and tasks executing different code. Results showed that our method achieved reasonable speedups on the test cases.

KW - Computational unit

KW - Data dependence

KW - Parallel programming

KW - Parallelism discovery

KW - Task parallelism

U2 - 10.1007/978-3-319-27140-8_39

DO - 10.1007/978-3-319-27140-8_39

M3 - Conference article in proceedings

AN - SCOPUS:84951827381

SN - 9783319271392

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 569

EP - 582

BT - Algorithms and Architectures for Parallel Processing - 15th International Conference, ICA3PP 2015, Proceedings

A2 - Zomaya, Albert

A2 - Perez, Gregorio Martinez

A2 - Li, Kenli

A2 - Wang, Guojun

PB - Springer

T2 - International Conference on Algorithms and Architectures for Parallel Processing

Y2 - 18 November 2015 through 20 November 2015

ER -

Li Z, Zhao B, Jannesari A, Wolf F. Beyond Data Parallelism : Identifying parallel tasks in sequential programs. In Zomaya A, Perez GM, Li K, Wang G, editors, Algorithms and Architectures for Parallel Processing - 15th International Conference, ICA3PP 2015, Proceedings. Springer. 2015. p. 569-582. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-27140-8_39

Beyond Data Parallelism : Identifying parallel tasks in sequential programs

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this