A decomposition-based constraint optimization approach for statically scheduling task graphs with communication delays to multiprocessors

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.

REFERENCES

• 1: Edward Ashford Lee , David G. Messerschmitt, Static scheduling of synchronous data flow programs for digital signal processing, IEEE Transactions on Computers, v.36 n.1, p.24-35, Jan. 1987 [doi>10.1109/TC.1987.5009446]
• 2: Matthias Gries, Methods for evaluating and covering the design space during early design development, Integration, the VLSI Journal, v.38 n.2, p.131-183, December 2004 [doi>10.1016/j.vlsi.2004.06.001]
• 3: Yu-Kwong Kwok , Ishfaq Ahmad, Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Computing Surveys (CSUR), v.31 n.4, p.406-471, Dec. 1999 [doi>10.1145/344588.344618]
• 4: M. F. Tompkins, "Optimization Techniques for Task Allocation and Scheduling in Distributed Multi-Agent Operations," Master's thesis, Massachusetts Institute of Technology, Cambridge, MA, June 2003.
• 5: Lothar Thiele, Resource constrained scheduling of uniform algorithms, Journal of VLSI Signal Processing Systems, v.10 n.3, p.295-310, Aug. 1995 [doi>10.1007/BF02120034]
• 6: Yujia Jin , Nadathur Satish , Kaushik Ravindran , Kurt Keutzer, An automated exploration framework for FPGA-based soft multiprocessor systems, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084903]
• 7: J. Hooker and G. Ottosson, "Logic-Based Benders Decomposition," Dec 1999. http://www.citeseer.ist.psu.edu/hooker95logicbased.html.
• 8: G. C. Sih , E. A. Lee, A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures, IEEE Transactions on Parallel and Distributed Systems, v.4 n.2, p.175-187, February 1993 [doi>10.1109/71.207593]
• 9: "ILOG CPLEX v10.1." http://www.ilog.com/products/cplex/.
• 10: Tatjana Davidović , Teodor Gabriel Crainic, Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systems, Computers and Operations Research, v.33 n.8, p.2155-2177, August 2006 [doi>10.1016/j.cor.2005.01.005]
• 11: N. Een and N. Sörensson, "An Extensible SAT-solver {ver 1.2}," in Lecture Notes in Computer Science (E. Giunchiglia and A. Tacchella, eds.), vol. 2919 of SAT, pp. 502--518, Springer, 2003.
• 12: A. Gerasoulis and T. Yang, "A Comparison of Clustering Heuristics for Scheduling DAGs onto Multiprocessors," J. Parallel Distrib. Computing, vol. 16, pp. 276--291, Dec 1992.
• 13: L. Benini, D. Bertozzi, A. Guerri, and M. Milano, "Allocation and Scheduling for MPSoCs via Decomposition and No-Good Generation," in Principles and Practice of Constraint Programming, 11th International Conference, pp. 107--121, 2005.
• 14: Xilinx, Inc., Embedded Systems Tools Guide, Xilinx Embedded Development Kit, EDK version 6.3i ed., June 2004.
• 15: N. K. Bambha and S. S. Bhattacharyya, "System Synthesis for Optically Connected Multiprocessors on Chip," in In Proc. of the International Workshop for System on Chip, 2002.