Presentation
Understanding Priority-Based Scheduling of Graph Algorithms on a Shared-Memory Platform
SessionPartitioning & Scheduling
Event Type
Paper
TP
Memory
Performance
Resource Management
Scheduling
Task-based programming
TimeWednesday, 20 November 20192pm - 2:30pm
Location405-406-407
DescriptionMany task-based graph algorithms benefit from executing tasks according to some priority order. To support such algorithms, graph frameworks use Concurrent Priority Schedulers (CPSs), which attempt to execute the tasks according to 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 invaluable to design better CPSs for graph processing.
This paper 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' OBIM, typically imposes negligible overheads, but its performance is input-dependent and can melt down for some inputs. Based on these insights, we develop PMOD that is both robust and delivers the highest performance overall.
This paper 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' OBIM, typically imposes negligible overheads, but its performance is input-dependent and can melt down for some inputs. Based on these insights, we develop PMOD that is both robust and delivers the highest performance overall.
Download PDF
Archive
