A fast approach to computing exact solutions to the resource-constrained scheduling problem

ABSTRACT

This article presents an algorithm that substantially reduces the computational effort required to obtain the exact solution to the Resource Constrained Scheduling (RCS) problem. The reduction is obtained by (a) using a branch-and-bound search technique, which computes both upper and lower bounds, and (b) using efficient techniques to accurately estimate the possible time-steps at which each operation can be scheduled and using this to prune the search space. Results on several benchmarks with varying resource constraints indicate the clear superiority of the algorithm presented here over traditional approaches using integer linear programming, with speed-ups of several orders of magnitude.

REFERENCES

• 1: BERKELAAR, M. 1997. lp solve version 2.1. ftp://ftp.es.ele.tue.nl/pub/lp solve.
• 2: Raul Camposano , Wayne H. Wolf, High-Level VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1991
• 3: Samit Chaudhuri , Robert A. Walker , John E. Mitchell, Analyzing and exploiting the structure of the constraints in the ILP approach to the scheduling problem, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.2 n.4, p.456-471, Dec. 1994 [doi>10.1109/92.335014]
• 4: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 5: EINDHOVEN DESIGN AUTOMATION GROUP WWW SERVER. 1994. Online Neat Sources: http://www.es.ele.tue.nl/neat (pre-release ed.). Eindhoven University of Technology.
• 6: GAJSKI, D., DUTT,N.,AND PANGRLE, B. 1986. Silicon compilation (tutorial). In Proceedings of the IEEE Custom Integrated Circuits Conference (May). IEEE Computer Society Press, Los Alamitos, Calif., pp. 102-110.
• 7: GEBOTYS,C.H.,AND ELMASRY, M. I. 1993. Global optimization approach for architectural synthesis. IEEE Trans. CAD 12, 9 (Sept.), 1266-1278.
• 8: HWANG,C.T.,LEE,T.H.,AND HSU, Y. C. 1991. A formal approach to the scheduling problem in high level synthesis. IEEE Trans. CAD 10, 4, 464-475.
• 9: M. Langevin , E. Cerny, A recursive technique for computing lower-bound performance of schedules, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.4, p.443-455, Oct. 1996 [doi>10.1145/238997.239002]
• 10: Youn-Long Lin, Recent developments in high-level synthesis, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.1, p.2-21, Jan. 1997 [doi>10.1145/250243.250245]
• 11: MCFARLAND, M., PARKER, A., AND CAMPOSANO, R. 1990. The high-level synthesis of digital systems. Proc. IEEE 78, 2 (Feb.), 301-318.
• 12: NARASIMHAN, M. 1998. Exact scheduling techniques for high-level synthesis. M.S. thesis, Louisiana State University.
• 13: NARASIMHAN, M., AND RAMANUJAM, J. 1997. The effect of tight partial schedule bounds and better heuristics on branch-and-bound solutions to scheduling. Tech. Rep. TR 97-07-01 (July 97, revised October 97), Louisiana State University.
• 14: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 15: PAULIN,P.,AND KNIGHT, J. 1989. Force-directed scheduling for the behavioral synthesis of ASIC's. IEEE Trans. CAD 8, 6 (June), 661-679.
• 16: RIM, M., AND JAIN, R. 1994. Lower bound performance estimation for the high-level synthesis scheduling problem. IEEE Trans. CAD 13, 4 (Apr.), 451-458.
• 17: ULLMAN, J. 1975. NP-complete scheduling problems. J. Comput. Syst. Sci. 10, 3 (June), 384-393.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Data-path design

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Hardware description languages; Optimization; Automatic synthesis
  B.m MISCELLANEOUS

General Terms:
Design, Experimentation

Keywords:
Design automation, enumeration, exact scheduling, high-level synthesis, lower and upper bounds, resource-constrained scheduling