search-icon
Paper
:
A Divide and Conquer Algorithm for DAG Scheduling Under Power Constraints
Event Type
Paper
Registration Categories
TP
Tags
Algorithms
Architectures
Memory
Networks
Parallel Programming Languages, Libraries, and Models
Power
Programming Systems
Scheduling
TimeWednesday, November 14th11:30am - 12pm
LocationC146
DescriptionWe consider the problem of scheduling a parallel computation–represented as a directed acyclic graph (DAG)–on a distributed parallel system with a global resource constraint–specifically a global power budget–and configurable resources, allowing a range of different power/performance tradeoffs. There is a rich body of literature on the independent problems of (1) scheduling DAGs and (2) scheduling independent applications under resource constraints. Very little, however, is known about the combined problem of scheduling DAGs under resource constraints. We present a novel approximation algorithm using a divide-and-conquer method for minimizing application execution time. We prove that the length of the schedule returned 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 implement and test our algorithm on simulations of real application DAGs. We find that our divide-and-conquer method improves performance by up to 75% compared to greedy scheduling algorithms.
Archive
Back To Top Button