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:20181221T160904Z
LOCATION:C2/3/4 Ballroom
DTSTART;TZID=America/Chicago:20181113T083000
DTEND;TZID=America/Chicago:20181113T170000
UID:submissions.supercomputing.org_SC18_sess325_spost109@linklings.com
SUMMARY:Recursive Algebraic Coloring Engine
DESCRIPTION:ACM Student Research Competition, Poster\nTech Program Reg Pas
s, Exhibits Reg Pass\n\nRecursive Algebraic Coloring Engine\n\nAlappat\n\n
Many iterative numerical methods for sparse systems and building blocks of
sparse linear algebra are difficult to parallelize due to data dependenci
es. These may be loop-carried dependencies as they occur in solvers like G
auss-Seidel or write conflicts as in symmetric sparse matrix vector. Most
of the existing parallelization strategies suffer from low performance on
modern hardware, are matrix specific, or require tailored storage formats
.\n\nIn this poster, we introduce a novel recursive level based algorithm
called Recursive Algebraic Coloring (RAC), which achieves high hardware ef
ficiency on modern multi-core architectures and works with simple data for
mats like compressed row storage. Method is implemented in a library calle
d Recursive Algebraic Coloring Engine (RACE). Thorough performance analys
is shows that RACE outperforms traditional multicoloring methods and Intel
-MKL implementations with a factor of 2–2.5×. We are on par with Algebraic
Block Multicoloring for small matrices, while for large matrices we gain
a factor of 1.5–2×.
URL:https://sc18.supercomputing.org/presentation/?id=spost109&sess=sess325
END:VEVENT
END:VCALENDAR