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:20210808T235336Z
LOCATION:Room C
DTSTART;TZID=America/Chicago:20210809T110000
DTEND;TZID=America/Chicago:20210809T111500
UID:icpp_ICPP 2021_sess136_dads_pap104@linklings.com
SUMMARY:Towards Faster Execution of Ensemble ML Bootstrap Based Techniques
DESCRIPTION:PDADS Workshop\n\nTowards Faster Execution of Ensemble ML Boot
strap Based Techniques\n\nGavirangaswamy, Gupta, Perovic, Saleh\n\nAlgorit
hms for ensemble methods (EM) based on bootstrap aggregation often perform
copious amount of redundant computations (RC) thus limiting their practic
ality. Given this constraint, we propose a framework that views these algo
rithms as a collection of computational units (cu), a tightly coupled set
of both mathematical operations and data. This view facilitates a reductio
n in RC (RRC), thereby allowing for faster execution plans. Inspired by th
e floor tiling approach in VLSI, we look to engineer solutions for RRC whi
le possibly reconfiguring the underlying computing system’s compiler techn
ology stack. We start by showing that under the assumption that the comput
ational system has unbounded but finite memory (i.e., the memory is large
enough to hold all intermediate values) and that each cu has a uniform cos
t, our approach reduces to a well-studied directed bandwidth problem for t
he directed acyclic graphs (DAGs). Next, we consider a more realistic scen
ario where the computing system has limited memory and concurrent executio
n while still assuming a uniform cost. Using a new notion of\n(𝑟,
𝑠) set cover of a DAG (nodes representing computational units and
edges representing their interdependencies) we formulate the problem of re
ducing redundant computational steps in EM as a variation of a directed ba
ndwidth problem. We show that the graph’s minimum bandwidth is closely rel
ated to memory requirements for studying RRC. Finally, our preliminary exp
erimental results are supportive of the proposed approach for RRC and prom
ising that it can be applied to a broader set of algorithms in decision sc
iences.
END:VEVENT
END:VCALENDAR