Abstract
In this paper, we focus on the resource-constrained modulo scheduling problem (RCMSP), a general periodic scheduling problem, abstracted from the problem solved by compilers when optimizing inner loops at instruction level for VLIW parallel processors. Heuristic solving scheme have been proposed since many years to solve this problem, among which the decomposed software pipeling method. In this method, a cyclic scheduling problem ignoring resource constraints is first considered and a so-called legal retiming of the operations is issued. Second, a standard acyclic problem, taking this retiming as input, is solved through list scheduling techniques. In this paper, we propose a novel hybrid approach, which uses the decomposed software pipeling method to obtain a good retiming. Then the obtained retiming is used to build an integer linear programming formulation of reduced size, which allows to solve it exactly. Experimental results show that a lot more problems are solved with this new approach. The gap to the optimal solution is less than 1 % on most of the tested problem instances and the method appears to be competitive with a recently proposed constraint programming algorithm (Bonfietti et al., Lect. Notes Comput. Sci. 6876:130–144, 2011).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
The resources are: Issue for the instruction issue width, MEM for the memory access unit, and CTL for the control unit. An artificial resource ALIGN is also introduced to satisfy some encoding constraints.
There are in our example, 10 classes of operations. ALU, MUL, MEM, and CTL correspond respectively to the arithmetic, multiply, memory, and control operations. The classes ALUX, MULX, and MEMX represent the operations that require an extended immediate operand. LDH, MULL, ADD, CMPNE, and BRF belong respectively to classes MEM, MUL, ALU, ALU and CTL.
References
Ayala, M., Artigues, C.: On integer linear programming formulations for the resource-constrained modulo scheduling problem. Technical Report 10393, LAAS-CNRS, Toulouse, France (2010)
Allan, V.H., Jones, R.B., Lee, R.M., Allan, S.J.: Software pipelining. ACM Comput. Surv. 27(3), 367–432 (1995)
Blachot, F., Dupont de Dinechin, B., Huard, G.: A heuristic for near-optimal software pipelining. In: Euro-Par 2006 Parallel Processing. Lecture Notes in Computer Science (2006)
Brucker, P., Drexl, A., Mohring, R., Neumann, K., Pesch, E.: Resource-constrained project scheduling: Notation, classification, models, and methods. Eur. J. Oper. Res. 112(1), 3–41 (1999)
Benabid, A., Hanen, C.: Decomposed software pipelining for cyclic unitary RCPSP with precedence delays. In: MISTA 09: Proceedings of the 4th Multidisciplinary International Scheduling Conference (2009)
Benabid, A., Hanen, C.: Modulo scheduling for unitary resource constrained cyclic problems. In: ROADEF (2009)
Benabid, A., Hanen, C.: Minimizing lateness for precedence graphs with constant delays on dedicated pipelined processors. In: ISCO: International Symposium on Combinatorial Optimization (2010)
Bonfietti, A., Lombardi, M., Benini, L., Milano, M.: A constraint based approach to cyclic rcpsp. In: Lee, J. (ed.) 17th International Conference on Principles and Practice of Constraint Programming, CP 2011. Lecture Notes in Computer Science, vol. 6876, pp. 130–144. Springer, Berlin (2011)
Christofides, N., Alvarez-Valdés, R., Tamarit, J.: Project scheduling with resource constraints: a branch and bound approach. Eur. J. Oper. Res. 29, 262–273 (1987)
Calland, P.-Y., Darte, A., Robert, Y.: Circuit retiming applied to decomposed software pipelining. IEEE Trans. Parallel Distrib. Syst. 9(1), 24–35 (1998)
Calland, P.-Y., Darte, A., Robert, Y.: Circuit retiming applied to decomposed software pipelining. IEEE Trans. Parallel Distrib. Syst. 9(1), 24–35 (1998)
Chaudhuri, S., Walker, R.A., Mitchell, J.E.: Analyzing and exploiting the structure of the constraints in the ILP approach to the scheduling problem. IEEE Trans. Very Large Scale Integr. Syst. 2, 456–471 (1994)
Dupont de Dinechin, B., Artigues, C., Azem, S.: Resource-constrained modulo scheduling. In: Artigues, C., Demassey, S., Néron, E. (eds.) Resource Constrained Project Scheduling: Models, Algorithms, Extensions and Applications, Control Systems, Robotics and Manufacturing Series, pp. 267–277. ISTE, New York (2008). ISBN 978-1-84821-034-9
Dupont de Dinechin, B.: From machine scheduling to vliw instruction scheduling. ST J. Res. 1, 2 (2004)
Darte, A., Huard, G.: Loop shifting for loop compaction. In: Lecture Notes in Computer Science, vol. 1863, pp. 415–431 (2000)
Darte, A., Huard, G.: Loop shifting for loop compaction. Int. J. Parallel Program. 28(5), 499–534 (2000)
Eichenberger, A., Davidson, E.S.: Efficient formulation for optimal modulo schedulers. In: SIGPLAN, PLDI’97 (1997)
Eichenberger, A., Davidson, E.S., Abraham, S.G.: Minimum register requirements for a modulo schedule. In: 27th Annual International Symposium on Microarchitecture (1994)
Faraboschi, P., Brown, G., Fisher, J.A., Desoli, G., Homewood, F.: Lx: a technology platform for customizable VLIW embedded processing. In: 27th Annual International Symposium on Computer Architecture, pp. 203–213 (2000)
Gondran, M., Minoux, M.: Graphes et algorithmes. Eyrolles, Paris (1985)
Gasperoni, F., Schwiegelshohn, U.: Generating close to optimum loop schedules on parallel processors. Parallel Process. Lett. 4, 391–403 (1994)
Hanen, C., Munier, A.: Cyclic scheduling on parallel processors: an overview. In: Chrétienne, P., Coffman, E.G., Lenstra, J.K., Liu, Z. (eds.) Scheduling Theory and Its Applications. Wiley, New York (1994)
Leiserson, C.E., Saxe, J.B.: Retiming synchronous circuitry. NASA STI/Recon Technical Report No. 89:17797 (1988)
Pritsker, A., Watters, L., Wolfe, P.: Multi-project scheduling with limited resources: a zero-one programming approach. Manag. Sci. 16, 93–108 (1969)
Ramakrishna Rau, B.: Dynamically scheduled VLIW processors. In: MICRO 26: Proceedings of the 26th Annual International Symposium on Microarchitecture, pp. 80–92. IEEE Computer Society Press, Los Alamitos (1993)
Ramakrishna Rau, B.: Iterative modulo scheduling: an algorithm for software pipelining loops. In: MICRO 27: Proceedings of the 27th Annual International Symposium on Microarchitecture, pp. 63–74. ACM, New York (1994)
Rajagopalan, S., Sharad, M.: Resource-Constrained Project Scheduling: Models, Algorithms, Extensions and Applications. CRC Press, Boca Raton (2002)
Sankaran, J., Bricker, D., Juang, S.: A strong fractional cutting-plane algorithm for resource-constrained project scheduling. Int. J. Ind. Eng. 6(2), 99–111 (1999)
Smelyanskiy, M., Mahlke, S., Davidson, E.S.: Probabilistic predicate-aware modulo scheduling. In: International Symposium on Code Generation and Optimization: Feedback-Directed and Runtime Optimization (2004)
Šůcha, P., Hanzàlek, Z.: A cyclic scheduling problem with an undetermined number of parallel identical processors. Comput. Optim. Appl. 48(1), 71–90 (2011)
Zinder, Y., Roper, D.: An iterative algorithm for scheduling unit-time operations with precedence constraints to minimise the maximum lateness. Ann. Oper. Res. 81, 321–340 (1998)
Acknowledgements
The authors wish to warmly thank Benoit Dupont de Dinechin for making the ST200 instances available and for his helpful advice on modulo scheduling. This work was partially supported by the GdR RO (Operations Research) of the CNRS.
Author information
Authors and Affiliations
Corresponding author
Appendix 1: Experimental result tables
Appendix 1: Experimental result tables
Rights and permissions
About this article
Cite this article
Ayala, M., Benabid, A., Artigues, C. et al. The resource-constrained modulo scheduling problem: an experimental study. Comput Optim Appl 54, 645–673 (2013). https://doi.org/10.1007/s10589-012-9499-2
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-012-9499-2