Distributed Control: Priority Scheduling for Single Source Shortest Paths Without Synchronization

Massively parallel computers provide unprecedented computing power that is only expected to grow. With great power comes great responsibility-parallel overheads may dominate and must be minimized. The synchronization overhead in particular is deeply rooted in the programming practice because it make...

Full description

Saved in:
Bibliographic Details
Main Authors: Zalewski, Marcin, Kanewala, Thejaka Amila, Firoz, Jesun Sahariar, Lumsdaine, Andrew
Format: Conference Proceeding
Language:English
Subjects:
Approximation algorithms
Computer architecture
Computers
Conferences
Decentralized control
HPC
Parallelism
Processor scheduling
Programming
Scheduling
SSSP
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Massively parallel computers provide unprecedented computing power that is only expected to grow. With great power comes great responsibility-parallel overheads may dominate and must be minimized. The synchronization overhead in particular is deeply rooted in the programming practice because it makes algorithms easier to design and implement. In the effort to eliminate it, we introduce the idea of distributed control where global synchronization is reduced to termination detection and each worker optimistically proceeds ahead, based on the local knowledge of the global computation. We propose a distributed priority scheduler to (approximately) prioritize useful work without synchronization, and we implement the single-source shortest paths (SSSP) algorithm using the scheduler. We show significant improvements over a previous implementation of SSSP using \Delta-\text{stepping} .
ISSN:2767-942X
DOI:10.1109/IA335182.2014.10612687