BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:America/Chicago
X-LIC-LOCATION:America/Chicago
BEGIN:DAYLIGHT
TZOFFSETFROM:-0600
TZOFFSETTO:-0500
TZNAME:CDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0500
TZOFFSETTO:-0600
TZNAME:CST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20181221T160728Z
LOCATION:D172
DTSTART;TZID=America/Chicago:20181112T153000
DTEND;TZID=America/Chicago:20181112T155500
UID:submissions.supercomputing.org_SC18_sess168_ws_ia105@linklings.com
SUMMARY:Mix-and-Match: A Model-Driven Runtime Optimization Strategy for BF
 S on GPUs
DESCRIPTION:Workshop\nArchitectures, Data Analytics, Graph Algorithms, Wor
 kshop Reg Pass\n\nMix-and-Match: A Model-Driven Runtime Optimization Strat
 egy for BFS on GPUs\n\nVerstraaten, Varbanescu, de Laat\n\nIt is universal
 ly accepted that the performance of graph algorithms is heavily dependent 
 on the algorithm, the execution platform, and the structure of the input g
 raph. This variability remains difficult to predict and hinders the choice
  of the right algorithm for a given problem.\n\nIn this work, we focus on 
 a case study: breadth-first search (BFS), a level-based graph traversal al
 gorithm, running on GPUs. We first demonstrate the severity of this variab
 ility by presenting 32 variations of 5 implementation strategies for GPU-e
 nabled BFS, and showing how selecting one single algorithm for the entire 
 traversal can significantly limit performance.  To alleviate these perform
 ance losses, we propose to mix-and-match, at runtime, different algorithms
  to compose the best performing BFS traversal. Our approach is based on tw
 o novel elements: a predictive model, based on a decision tree, which is a
 ble to dynamically select the best performing algorithm for each BFS level
 , and a quick context switch between algorithms, which limits the overhead
  of the combined BFS.\n\nWe demonstrate empirically that our dynamic switc
 hing BFS achieves better performance, outperforming our non-switching impl
 ementations by 2x and existing state-of-the-art GPU BFS implementations by
  3x. We conclude that mix-and-match BFS is a competitive approach for doin
 g fast graph traversal, while being easily extended to include more BFS im
 plementations and easily adaptable to other types of processors or specifi
 c types of graphs.
URL:https://sc18.supercomputing.org/presentation/?id=ws_ia105&sess=sess168
END:VEVENT
END:VCALENDAR