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:20260522T150123Z
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:Gökalp Demirci, Ivana Marincic, and Henry Hoffmann (University
  of Chicago)\n\nWe consider the problem of scheduling a parallel computati
 on–represented as a directed acyclic graph (DAG)–on a distributed parallel
  system with a global resource constraint–specifically a global power budg
 et–and configurable resources, allowing a range of different power/perform
 ance tradeoffs. There is a rich body of literature on the independent prob
 lems of (1) scheduling DAGs and (2) scheduling independent applications un
 der resource constraints. Very little, however, is known about the combine
 d problem of scheduling DAGs under resource constraints. We present a nove
 l approximation algorithm using a divide-and-conquer method for minimizing
  application execution time. We prove that the length of the schedule retu
 rned by our algorithm is always within O(log n)-factor of the optimum that
  can be achieved with selection of configurations for the tasks. We implem
 ent and test our algorithm on simulations of real application DAGs. We fin
 d that our divide-and-conquer method improves performance by up to 75% com
 pared to greedy scheduling algorithms.\n\nTag: Algorithms, Architectures, 
 Memory, Networks, Parallel Programming Languages, Libraries, and Models, P
 ower, Programming Systems, Scheduling\n\nRegistration Category: Tech Progr
 am Reg Pass\n\nSession Chair: Patrick S. McCormick (Los Alamos National La
 boratory (LANL))\n\n
END:VEVENT
END:VCALENDAR