BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:America/Denver
X-LIC-LOCATION:America/Denver
BEGIN:DAYLIGHT
TZOFFSETFROM:-0700
TZOFFSETTO:-0600
TZNAME:MDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0600
TZOFFSETTO:-0700
TZNAME:MST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20200129T163557Z
LOCATION:505
DTSTART;TZID=America/Denver:20191118T145000
DTEND;TZID=America/Denver:20191118T150000
UID:submissions.supercomputing.org_SC19_sess128_ws_ia111@linklings.com
SUMMARY:iPregel: Strategies to Deal with an Extreme Form of Irregularity i
 n Vertex-Centric Graph Processing
DESCRIPTION:Workshop\n\niPregel: Strategies to Deal with an Extreme Form o
 f Irregularity in Vertex-Centric Graph Processing\n\nCapelli, Brown, Bull\
 n\nOver the last decade, the vertex-centric programming model has attracte
 d significant attention in the world of graph processing, resulting in the
  emergence of a number of  vertex-centric frameworks. Its simple programmi
 ng interface, where computation is expressed from a vertex point of view, 
 offers both ease of programming to the user and inherent parallelism for t
 he underlying framework to leverage.\n\nHowever, vertex-centric programs r
 epresent an extreme form of irregularity, both inter and intra core. This 
 is because they exhibit a variety of challenges from a workload that may g
 reatly vary across supersteps, through fine-grain synchronisations, to mem
 ory accesses that are unpredictable both in terms of quantity and location
 .\n\nIn this paper, we explore three optimisations which address these irr
 egular challenges; a hybrid combiner carefully coupling lock-free and lock
 -based combinations, the partial externalisation of vertex structures to i
 mprove locality and the shift to an edge-centric representation of the wor
 kload. We also assess the suitability of more traditional optimisations su
 ch as dynamic load-balancing and software prefetching.\n\nThe optimisation
 s were integrated into the iPregel vertex-centric framework, enabling the 
 evaluation of each optimisation in the context of graph processing across 
 three general purpose benchmarks common in the vertex-centric community, e
 ach run on four publicly available graphs covering all orders of magnitude
  from a million to a billion edges.\n\nThe result of this work is a set of
  techniques which we believe not only provide a significant performance im
 provement in vertex-centric graph processing, but are also applicable more
  generally to irregular applications.\n\nTag: Workshop Reg Pass, Algorithm
 s, Architectures, Irregular Applications\n\nRegistration Category: Worksho
 p Reg Pass, Algorithms, Architectures, Irregular Applications
URL:https://sc19.supercomputing.org/presentation/?id=ws_ia111&sess=sess128
END:VEVENT
END:VCALENDAR