BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:America/New_York
X-LIC-LOCATION:America/New_York
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20210402T160554Z
LOCATION:Track 4
DTSTART;TZID=America/New_York:20201111T110000
DTEND;TZID=America/New_York:20201111T112000
UID:submissions.supercomputing.org_SC20_sess201_ws_ia104@linklings.com
SUMMARY:Accelerating Domain Propagation: an Efficient GPU-Parallel Algorit
 hm over Sparse Matrices
DESCRIPTION:Workshop\n\nAccelerating Domain Propagation: an Efficient GPU-
 Parallel Algorithm over Sparse Matrices\n\nSofranac, Gleixner, Pokutta\n\n
 Fast domain propagation of linear constraints has become a crucial compone
 nt of today’s best algorithms and solvers for mixed integer programming an
 d pseudo-boolean optimization to achieve peak solving performance. Irregul
 arities in the form of dynamic algorithmic behavior, dependency structures
 , and sparsity patterns in the input data make efficient implementations o
 f domain propagation on GPUs and, more generally, on parallel architecture
 s challenging. This is one of the main reasons why domain propagation in s
 tate-of-the-art solvers is single thread only. In this paper, we present a
  new algorithm for domain propagation which (a) avoids these problems and 
 allows for an efficient implementation on GPUs, and is (b) capable of runn
 ing propagation rounds entirely on the GPU, without any need for synchroni
 zation or communication with the CPU.  \n\nWe present extensive computatio
 nal results which demonstrate the effectiveness of our approach and show t
 hat ample speedups are possible on practically relevant problems: on state
 -of-the-art GPUs, our geometric mean speed-up for reasonably-large instanc
 es is around 10x to 20x and can be as high as 195x on favorably-large inst
 ances.\n\nRegistration Category: Workshop Reg Pass
END:VEVENT
END:VCALENDAR