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:20260522T150116Z
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:Merijn Elwin Verstraaten, Ana Lucia Varbanescu, and Cees de La
 at (University of Amsterdam)\n\nIt is universally accepted that the perfor
 mance of graph algorithms is heavily dependent on the algorithm, the execu
 tion platform, and the structure of the input graph. This variability rema
 ins 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 algorithm, running on GPUs. W
 e first demonstrate the severity of this variability by presenting 32 vari
 ations of 5 implementation strategies for GPU-enabled BFS, and showing how
  selecting one single algorithm for the entire traversal can significantly
  limit performance.  To alleviate these performance losses, we propose to 
 mix-and-match, at runtime, different algorithms to compose the best perfor
 ming BFS traversal. Our approach is based on two novel elements: a predict
 ive model, based on a decision tree, which is able to dynamically select t
 he best performing algorithm for each BFS level, and a quick context switc
 h between algorithms, which limits the overhead of the combined BFS.\n\nWe
  demonstrate empirically that our dynamic switching BFS achieves better pe
 rformance, outperforming our non-switching implementations by 2x and exist
 ing state-of-the-art GPU BFS implementations by 3x. We conclude that mix-a
 nd-match BFS is a competitive approach for doing fast graph traversal, whi
 le being easily extended to include more BFS implementations and easily ad
 aptable to other types of processors or specific types of graphs.\n\nTag: 
 Architectures, Data Analytics, Graph Algorithms\n\nRegistration Category: 
 Workshop Reg Pass\n\nSession Chairs: Vito Giovanni Castellana (Pacific Nor
 thwest National Laboratory (PNNL)), John Feo (Pacific Northwest National L
 aboratory (PNNL)), and Antonino Tumeo (Pacific Northwest National Laborato
 ry (PNNL))\n\n
END:VEVENT
END:VCALENDAR