Citation
Nadathur 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), 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

• 01c_2_854.pdf · application/pdf · 126 kbytes

• HTML

  Nadathur Satish, Kaushik Ravindran, Kurt Keutzer. <a
  href="http://chess.eecs.berkeley.edu/pubs/226.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), 57-62,
  April, 2007.

• Plain text

  Nadathur 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), 57-62, April, 2007.

• BibTeX

  @inproceedings{SatishRavindranKeutzer07_DecompositionbasedConstraintOptimizationApproachFor,
      author = {Nadathur 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)},
      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://chess.eecs.berkeley.edu/pubs/226.html}
  }
  

Posted by Kaushik Ravindran on 9 May 2007.
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.