Understanding priority-based scheduling of graph algorithms on a shared-memory platform

Serif Yesil, Azin Heidarshenas, Adam Morrison, Josep Torrellas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Many task-based graph algorithms benefit from executing tasks according to some programmer-specified priority order. To support such algorithms, graph frameworks use Concurrent Priority Schedulers (CPSs), which attempt - -but do not guarantee - -to execute the tasks according to their priority order. While CPSs are critical to performance, there is insufficient insight on the relative strengths and weaknesses of the different CPS designs in the literature. Such insights would be valuable to design better CPSs for graph processing. This paper addresses this problem. It performs a detailed empirical performance analysis of several advanced CPS designs in a state-of-the-art graph analytics framework running on a large shared-memory server. Our analysis finds that all CPS designs but one impose major overheads that dominate running time. Only one CPS - -the Galois system's obim - -typically imposes negligible overheads. However, obim's performance is input-dependent and can degrade substantially for some inputs. Based on our insights, we develop PMOD, a new CPS that is robust and delivers the highest performance overall.

Original languageEnglish (US)
Title of host publicationProceedings of SC 2019
Subtitle of host publicationThe International Conference for High Performance Computing, Networking, Storage and Analysis
PublisherIEEE Computer Society
ISBN (Electronic)9781450362290
DOIs
StatePublished - Nov 17 2019
Event2019 International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2019 - Denver, United States
Duration: Nov 17 2019Nov 22 2019

Publication series

NameInternational Conference for High Performance Computing, Networking, Storage and Analysis, SC
ISSN (Print)2167-4329
ISSN (Electronic)2167-4337

Conference

Conference2019 International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2019
CountryUnited States
CityDenver
Period11/17/1911/22/19

Keywords

  • Concurrent priority scheduling
  • Graphs
  • Memory hierarchy
  • Shared-memory multiprocessors

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications
  • Hardware and Architecture
  • Software

Fingerprint Dive into the research topics of 'Understanding priority-based scheduling of graph algorithms on a shared-memory platform'. Together they form a unique fingerprint.

Cite this