poster

POSTER: Distributed Control: The Benefits of Eliminating Global Synchronization via Effective Scheduling

Authors:

Jesun Shariar Firoz,

Thejaka Amila Kanewala,

Marcin Zalewski,

Martina Barnas,

Andrew LumsdaineAuthors Info & Claims

ACM SIGPLAN Notices, Volume 52, Issue 8

Pages 441 - 442

https://doi.org/10.1145/3155284.3019036

Published: 26 January 2017 Publication History

Get Access

Abstract

In distributed computing, parallel overheads such as \emph{synchronization overhead} may hinder performance. We introduce the idea of \emph{Distributed Control} (DC) where global synchronization is reduced to \emph{termination detection} and each worker proceeds ahead optimistically, based on the local knowledge of the global computation. To avoid "wasted'' work, \DC relies on local work prioritization. However, the work order obtained by local prioritization is susceptible to interference from the runtime. We show that employing effective scheduling policies and optimizations in the runtime, in conjunction with eliminating global barriers, improves performance in two graph applications: single-source shortest paths and connected components.

References

[1]

http://hpx.crest.iu.edu/. Accessed: 2016-05--25.

Google Scholar

[2]

Graph500. http://www.graph500.org/, Aug. 2016. Accessed: 2016-05--31.

Google Scholar

[3]

J. J. Willcock, T. Hoefler, N. G. Edmonds, and A. Lumsdaine.ampp: A Generalized Active Message Framework. In phProce. 19th Int. Conf. on Parallel Architectures and Compilation Techniques, pages 401--410. ACM, 2010.

Digital Library

Google Scholar

[4]

M. Zalewski, T. A. Kanewala, J. S. Firoz, and A. Lumsdaine. Distributed Control: Priority Scheduling for Single Source Shortest Paths Without Synchronization. In phProc. of the Fourth Workshop on Irregular Applications: Architectures and Algorithms, pages 17--24. IEEE, 2014.

Digital Library

Google Scholar

Index Terms

POSTER: Distributed Control: The Benefits of Eliminating Global Synchronization via Effective Scheduling
1. Computing methodologies
  1. Distributed computing methodologies

Recommendations

POSTER: Distributed Control: The Benefits of Eliminating Global Synchronization via Effective Scheduling
PPoPP '17: Proceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

In distributed computing, parallel overheads such as \emph{synchronization overhead} may hinder performance. We introduce the idea of \emph{Distributed Control} (DC) where global synchronization is reduced to \emph{termination detection} and each worker ...
Optimal EREW parallel algorithms for connectivity, ear decomposition and st-numbering of planar graphs
IPPS '91: Proceedings of the Fifth International Parallel Processing Symposium

Parallel EREW deterministic algorithms for finding the connected components, ear decomposition and st-numbering of a planar graph are presented. The algorithms take O(log(n)) time with /sub log(n)///sup n+m/ processors. Previous results have the same ...
Fast Connected Components Algorithms for the EREW PRAM

We present fast and efficient parallel algorithms for finding the connected components of an undirected graph. These algorithms run on the exclusive-read, exclusive-write (EREW) PRAM. On a graph with n vertices and m edges, our randomized algorithm ...

Comments

Information & Contributors

Information

Published In

ACM SIGPLAN Notices Volume 52, Issue 8

PPoPP '17

August 2017

442 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/3155284

Editor:
Matthew Fluet

Issue’s Table of Contents

PPoPP '17: Proceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
January 2017
476 pages
ISBN:9781450344937
DOI:10.1145/3018743
General Chair:
Vivek Sarkar
Rice University, USA
,
Program Chair:
Lawrence Rauchwerger
Texas A&M University, USA

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 January 2017

Published in SIGPLAN Volume 52, Issue 8

Check for updates

Author Tags

Qualifiers

Poster

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
145
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Index Terms

Recommendations

POSTER: Distributed Control: The Benefits of Eliminating Global Synchronization via Effective Scheduling

Optimal EREW parallel algorithms for connectivity, ear decomposition and st-numbering of planar graphs

Fast Connected Components Algorithms for the EREW PRAM