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:20181221T160731Z
LOCATION:C146
DTSTART;TZID=America/Chicago:20181114T113000
DTEND;TZID=America/Chicago:20181114T120000
UID:submissions.supercomputing.org_SC18_sess183_pap547@linklings.com
SUMMARY:A Divide and Conquer Algorithm for DAG Scheduling Under Power Cons
 traints
DESCRIPTION:Paper\nAlgorithms, Architectures, Memory, Networks, Parallel P
 rogramming Languages, Libraries, and Models, Power, Programming Systems, S
 cheduling, Tech Program Reg Pass\n\nA Divide and Conquer Algorithm for DAG
  Scheduling Under Power Constraints\n\nDemirci, Marincic, Hoffmann\n\nWe c
 onsider the problem of scheduling a parallel computation–represented as a 
 directed acyclic graph (DAG)–on a distributed parallel system with a globa
 l resource constraint–specifically a global power budget–and configurable 
 resources, allowing a range of different power/performance tradeoffs. Ther
 e is a rich body of literature on the independent problems of (1) scheduli
 ng DAGs and (2) scheduling independent applications under resource constra
 ints. Very little, however, is known about the combined problem of schedul
 ing DAGs under resource constraints. We present a novel approximation algo
 rithm using a divide-and-conquer method for minimizing application executi
 on time. We prove that the length of the schedule returned by our algorith
 m is always within O(log n)-factor of the optimum that can be achieved wit
 h selection of configurations for the tasks. We implement and test our alg
 orithm on simulations of real application DAGs. We find that our divide-an
 d-conquer method improves performance by up to 75% compared to greedy sche
 duling algorithms.
URL:https://sc18.supercomputing.org/presentation/?id=pap547&sess=sess183
END:VEVENT
END:VCALENDAR