Citation
Nadathur Rajagopalan Satish, Kaushik Ravindran, Kurt Keutzer. "A Decomposition-based Constraint Optimization Approach for Statically Scheduling Task Graphs with Communication Delays to Multiprocessors". 10th Conference of Design, Automation and Test in Europe (DATE-07), ACM Press, 57-62, April, 2007.

Abstract
We present a decomposition strategy to speed up constraint optimization for a representative multiprocessor scheduling problem. In the manner of Benders decomposition, our technique solves relaxed versions of the problem and iteratively learns constraints to prune the solution space. Typical formulations suffer prohibitive run times even on medium-sized problems with less than 30 tasks. Our decomposition strategy enhances constraint optimization to robustly handle instances with over 100 tasks. Moreover, the extensibility of constraint formulations permits realistic application and resource constraints, which is a limitation of common heuristic methods for scheduling. The inherent extensibility, coupled with improved run times from a decomposition strategy, posit constraint optimization as a powerful tool for resource constrained scheduling and multiprocessor design space exploration.

Electronic downloads

• http://doi.acm.org/10.1145/1266366.1266381

Citation formats

• HTML

  Nadathur Rajagopalan Satish, Kaushik Ravindran, Kurt
  Keutzer. <a
  href="http://www.gigascale.org/pubs/1028.html">A
  Decomposition-based Constraint Optimization Approach for
  Statically Scheduling Task Graphs with Communication Delays
  to Multiprocessors</a>, 10th Conference of Design,
  Automation and Test in Europe (DATE-07), ACM Press, 57-62,
  April, 2007.

• Plain text

  Nadathur Rajagopalan Satish, Kaushik Ravindran, Kurt
  Keutzer. "A Decomposition-based Constraint Optimization
  Approach for Statically Scheduling Task Graphs with
  Communication Delays to Multiprocessors". 10th Conference of
  Design, Automation and Test in Europe (DATE-07), ACM Press,
  57-62, April, 2007.

• BibTeX

  @inproceedings{SatishRavindranKeutzer07_DecompositionbasedConstraintOptimizationApproachFor,
      author = {Nadathur Rajagopalan Satish and Kaushik Ravindran
                and Kurt Keutzer},
      title = {A Decomposition-based Constraint Optimization
                Approach for Statically Scheduling Task Graphs
                with Communication Delays to Multiprocessors},
      booktitle = {10th Conference of Design, Automation and Test in
                Europe (DATE-07)},
      organization = {ACM Press},
      pages = {57-62},
      month = {April},
      year = {2007},
      abstract = {We present a decomposition strategy to speed up
                constraint optimization for a representative
                multiprocessor scheduling problem. In the manner
                of Benders decomposition, our technique solves
                relaxed versions of the problem and iteratively
                learns constraints to prune the solution space.
                Typical formulations suffer prohibitive run times
                even on medium-sized problems with less than 30
                tasks. Our decomposition strategy enhances
                constraint optimization to robustly handle
                instances with over 100 tasks. Moreover, the
                extensibility of constraint formulations permits
                realistic application and resource constraints,
                which is a limitation of common heuristic methods
                for scheduling. The inherent extensibility,
                coupled with improved run times from a
                decomposition strategy, posit constraint
                optimization as a powerful tool for resource
                constrained scheduling and multiprocessor design
                space exploration.},
      URL = {http://www.gigascale.org/pubs/1028.html}
  }
  

Posted by Kaushik Ravindran on 11 Jul 2007..

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.