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:20210402T160544Z
LOCATION:Track 6
DTSTART;TZID=America/New_York:20201112T125000
DTEND;TZID=America/New_York:20201112T133000
UID:submissions.supercomputing.org_SC20_sess212_ws_llvmf107@linklings.com
SUMMARY:Deep Learning-Based Approximate Graph-Coloring Algorithm for Regis
 ter Allocation
DESCRIPTION:Workshop\n\nDeep Learning-Based Approximate Graph-Coloring Alg
 orithm for Register Allocation\n\nDas, Ahmad, Venkataramanan\n\nGraph-colo
 ring is an NP-hard problem which has a myriad of applications. Register al
 location, which is a crucial phase of a good optimizing compiler, relies o
 n graph coloring. Hence, an efficient graph-coloring algorithm is of param
 ount importance. In this work we try to ‘learn’ a good heuristic for color
 ing interference graphs that are used in the register allocation phase. We
  aim to handle moderate-sized interference graphs which have 100 nodes or 
 less. For such graphs we can get the optimal allocation of colors to the n
 odes. Such optimal coloring is then used to train our Deep Learning (DL) n
 etwork which is based on several layers of LSTM that output a color for ea
 ch node of the graph. However, the trained network may allocate the same c
 olor to the nodes connected by an edge resulting in an invalid coloring of
  the interference graph. Since it is difficult to encode constraints in an
  LSTM to avoid invalid coloring, we augment our deep learning network with
  a color correction phase that runs after the colors have been allocated b
 y the DL network. Thus, our algorithm is approximate or hybrid in nature c
 onsisting of a mix of a DL algorithm followed by a more traditional correc
 tion phase. The color correction phase handles the edges with invalid colo
 ring by first trying to reuse a color allocated to other nodes that are no
 t connected to the invalid nodes, failing which it adds a totally new colo
 r – thereby breaking the invalid allocation. Our experience with many grap
 hs shows that around 10%-30% edges may get an invalid coloring. We have tr
 ained our DL network using several thousand random graphs of varying spars
 ity(density). On application of our approximate algorithm to various popul
 ar graphs found in literature we see that our algorithm does very well whe
 n compared to the optimal coloring of these graphs. We have also run our a
 lgorithm against LLVM’s popular greedy register allocator (GRA) for severa
 l SPEC CPU 2017 benchmarks and notice that the approximate algorithm perfo
 rms on par or better than GRA for most of these benchmarks.\n\nRegistratio
 n Category: Workshop Reg Pass
END:VEVENT
END:VCALENDAR