Parallelization of While Loops in Nested Loop Programs for Shared-Memory Multiprocessor Systems

S.J. Geuns, Marco Jan Gerrit Bekooij, T. Bijlsma, Henk Corporaal

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

14 Citations (Scopus)

Abstract

Many applications contain loops with an undetermined number of iterations. These loops have to be parallelized in order to increase the throughput when executed on an embedded multiprocessor platform. This paper presents a method to automatically extract a parallel task graph based on function level parallelism from a sequential nested loop program with while loops. In the parallelized task graph loop iterations can overlap during execution. We introduce the notion of a single assignment section such that we can exploit single assignment to overlap iterations of the while loop during the execution of the parallel task graph. Synchronization is inserted in the parallelized task graph to ensure the same functional behavior as the sequential nested loop program. It is shown that the generated parallel task graph does not introduce deadlock. A DVB-T radio receiver where the user can switch channels after an undetermined amount of time illustrates the approach.
Original languageUndefined
Title of host publicationDesign, Automation & Test in Europe Conference & Exhibition, DATE 2011
Place of PublicationUSA
PublisherIEEE Computer Society
Pages1-6
Number of pages6
ISBN (Print)978-1-61284-208-0
Publication statusPublished - 16 Mar 2011
Event2011 Design, Automation & Test in Europe Conference & Exhibition, DATE 2011 - Grenoble, France
Duration: 14 Mar 201118 Mar 2011

Publication series

Name
PublisherIEEE Computer Society
ISSN (Print)1530-1591

Conference

Conference2011 Design, Automation & Test in Europe Conference & Exhibition, DATE 2011
Abbreviated titleDATE
CountryFrance
CityGrenoble
Period14/03/1118/03/11

Keywords

  • METIS-278761
  • EWI-20437
  • IR-78154

Cite this

Geuns, S. J., Bekooij, M. J. G., Bijlsma, T., & Corporaal, H. (2011). Parallelization of While Loops in Nested Loop Programs for Shared-Memory Multiprocessor Systems. In Design, Automation & Test in Europe Conference & Exhibition, DATE 2011 (pp. 1-6). USA: IEEE Computer Society.
Geuns, S.J. ; Bekooij, Marco Jan Gerrit ; Bijlsma, T. ; Corporaal, Henk. / Parallelization of While Loops in Nested Loop Programs for Shared-Memory Multiprocessor Systems. Design, Automation & Test in Europe Conference & Exhibition, DATE 2011. USA : IEEE Computer Society, 2011. pp. 1-6
@inproceedings{b1af3f09c7c04d03a7c5c54036fe95f1,
title = "Parallelization of While Loops in Nested Loop Programs for Shared-Memory Multiprocessor Systems",
abstract = "Many applications contain loops with an undetermined number of iterations. These loops have to be parallelized in order to increase the throughput when executed on an embedded multiprocessor platform. This paper presents a method to automatically extract a parallel task graph based on function level parallelism from a sequential nested loop program with while loops. In the parallelized task graph loop iterations can overlap during execution. We introduce the notion of a single assignment section such that we can exploit single assignment to overlap iterations of the while loop during the execution of the parallel task graph. Synchronization is inserted in the parallelized task graph to ensure the same functional behavior as the sequential nested loop program. It is shown that the generated parallel task graph does not introduce deadlock. A DVB-T radio receiver where the user can switch channels after an undetermined amount of time illustrates the approach.",
keywords = "METIS-278761, EWI-20437, IR-78154",
author = "S.J. Geuns and Bekooij, {Marco Jan Gerrit} and T. Bijlsma and Henk Corporaal",
year = "2011",
month = "3",
day = "16",
language = "Undefined",
isbn = "978-1-61284-208-0",
publisher = "IEEE Computer Society",
pages = "1--6",
booktitle = "Design, Automation & Test in Europe Conference & Exhibition, DATE 2011",
address = "United States",

}

Geuns, SJ, Bekooij, MJG, Bijlsma, T & Corporaal, H 2011, Parallelization of While Loops in Nested Loop Programs for Shared-Memory Multiprocessor Systems. in Design, Automation & Test in Europe Conference & Exhibition, DATE 2011. IEEE Computer Society, USA, pp. 1-6, 2011 Design, Automation & Test in Europe Conference & Exhibition, DATE 2011, Grenoble, France, 14/03/11.

Parallelization of While Loops in Nested Loop Programs for Shared-Memory Multiprocessor Systems. / Geuns, S.J.; Bekooij, Marco Jan Gerrit; Bijlsma, T.; Corporaal, Henk.

Design, Automation & Test in Europe Conference & Exhibition, DATE 2011. USA : IEEE Computer Society, 2011. p. 1-6.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Parallelization of While Loops in Nested Loop Programs for Shared-Memory Multiprocessor Systems

AU - Geuns, S.J.

AU - Bekooij, Marco Jan Gerrit

AU - Bijlsma, T.

AU - Corporaal, Henk

PY - 2011/3/16

Y1 - 2011/3/16

N2 - Many applications contain loops with an undetermined number of iterations. These loops have to be parallelized in order to increase the throughput when executed on an embedded multiprocessor platform. This paper presents a method to automatically extract a parallel task graph based on function level parallelism from a sequential nested loop program with while loops. In the parallelized task graph loop iterations can overlap during execution. We introduce the notion of a single assignment section such that we can exploit single assignment to overlap iterations of the while loop during the execution of the parallel task graph. Synchronization is inserted in the parallelized task graph to ensure the same functional behavior as the sequential nested loop program. It is shown that the generated parallel task graph does not introduce deadlock. A DVB-T radio receiver where the user can switch channels after an undetermined amount of time illustrates the approach.

AB - Many applications contain loops with an undetermined number of iterations. These loops have to be parallelized in order to increase the throughput when executed on an embedded multiprocessor platform. This paper presents a method to automatically extract a parallel task graph based on function level parallelism from a sequential nested loop program with while loops. In the parallelized task graph loop iterations can overlap during execution. We introduce the notion of a single assignment section such that we can exploit single assignment to overlap iterations of the while loop during the execution of the parallel task graph. Synchronization is inserted in the parallelized task graph to ensure the same functional behavior as the sequential nested loop program. It is shown that the generated parallel task graph does not introduce deadlock. A DVB-T radio receiver where the user can switch channels after an undetermined amount of time illustrates the approach.

KW - METIS-278761

KW - EWI-20437

KW - IR-78154

M3 - Conference contribution

SN - 978-1-61284-208-0

SP - 1

EP - 6

BT - Design, Automation & Test in Europe Conference & Exhibition, DATE 2011

PB - IEEE Computer Society

CY - USA

ER -

Geuns SJ, Bekooij MJG, Bijlsma T, Corporaal H. Parallelization of While Loops in Nested Loop Programs for Shared-Memory Multiprocessor Systems. In Design, Automation & Test in Europe Conference & Exhibition, DATE 2011. USA: IEEE Computer Society. 2011. p. 1-6