Worst case analysis of decomposed software pipelining for cyclic unitary RCPSP with precedence delays. (English) Zbl 1280.68071
Summary: In this paper, we address a cyclic scheduling problem of finding a periodic schedule with minimal period for the unitary resource constrained cyclic scheduling problem. The main originality is in being able to cope with both precedence delays and complex resource settings which make the problem \(\mathcal{NP}\)-complete, in general.
A guaranteed approach, called Decomposed Software Pipelining, has been proposed by F. Gasperoni and U. Schwiegelshohn [“Generating close to optimum loop schedules on parallel processors”, Parallel Process. Lett. 4, No. 4, 391–403 (1994; doi:10.1142/S0129626494000363)], followed by the retiming method by P.-Y. Calland et al. [“Circuit retiming applied to decomposed software pipelining”, IEEE Trans. Parallel Distrib. Syst. 9, No. 1, 24–35 (1998; doi:10.1109/71.655240)] to solve the problem assuming parallel identical processors and ordinary precedence constraints. In this paper, an extension of this approach to unitary resource-constrained cyclic scheduling problems with precedence delays, is analyzed and its worst case performance ratio is provided.
A guaranteed approach, called Decomposed Software Pipelining, has been proposed by F. Gasperoni and U. Schwiegelshohn [“Generating close to optimum loop schedules on parallel processors”, Parallel Process. Lett. 4, No. 4, 391–403 (1994; doi:10.1142/S0129626494000363)], followed by the retiming method by P.-Y. Calland et al. [“Circuit retiming applied to decomposed software pipelining”, IEEE Trans. Parallel Distrib. Syst. 9, No. 1, 24–35 (1998; doi:10.1109/71.655240)] to solve the problem assuming parallel identical processors and ordinary precedence constraints. In this paper, an extension of this approach to unitary resource-constrained cyclic scheduling problems with precedence delays, is analyzed and its worst case performance ratio is provided.
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 90B35 | Deterministic scheduling theory in operations research |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68W25 | Approximation algorithms |
Keywords:
scheduling; cyclic scheduling; software pipelining; time-lags; precedence delays; resource constrained scheduling problem; approximated algorithm; list algorithmReferences:
| [1] | Alcaide, D., Chu, C., Kats, V., Levner, E., & Sierksma, G. (2007). Cyclic multiple-robot scheduling with time-window constraints using a critical path approach. European Journal of Operational Research, 177, 147–162. · Zbl 1111.90033 · doi:10.1016/j.ejor.2005.11.019 |
| [2] | Allan, V. H., Jones, R. B., Lee, R. M., & Allan, S. J. (1995). Software pipelining. ACM Computer Survey, 27(3), 367–432. · doi:10.1145/212094.212131 |
| [3] | Brucker, P., Drexl, A., Mohring, R., Neumann, K., & Pesch, E. (1999). Resource-constrained project scheduling: Notation classification, models, and methods. European Journal of Operational Research, 112(1), 3–41. · Zbl 0937.90030 · doi:10.1016/S0377-2217(98)00204-5 |
| [4] | Calland, P. Y., Darte, A., & Robert, Y. (1998). Circuit retiming applied to decomposed software pipelining. IEEE Transactions of Parallel Distribution Systems, 9(1), 24–35. · doi:10.1109/71.655240 |
| [5] | Chou, H. C., & Chung, C. P. (1992). Upper bound analysis of scheduling arbitrary delay instruction on typed pipelined processors. International Journal of High Speed Computing, 4(4), 301–312. · doi:10.1142/S0129053392000146 |
| [6] | Darte, A., & Huard, G. (2000). Loop shifting for loop compaction. International Journal of Parallel Programming, 28(5), 499–534. · doi:10.1023/A:1007506711786 |
| [7] | Dasdan, A., Irani, S., & Gupta, R. K. (1999). Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems. In Design automation conference (pp. 37–42). |
| [8] | Dupont de Dinechin, B., Artiques, C., & Azem, S. (2008). Resource constrained modulo scheduling. In C. Artigues et al. (Eds.), Resource-constrained project scheduling: models, algorithms, extensions and applications, control systems, robotics and manufacturing series (pp. 267–277) London: ISTE/Wiley. |
| [9] | Gasperoni, F., & Schwiegelshohn, U. (1994). Generating close to optimum loop schedules on parallel processors. Parallel Processing Letters, 4, 391–403. · doi:10.1142/S0129626494000363 |
| [10] | Hanen, C., & Munier, A. (1994). Cyclic scheduling on parallel processors: an overview. In Scheduling theory and its applications. New York: Wiley. · Zbl 0830.68009 |
| [11] | Huff, R. A. (1993). Lifetime-sensitive modulo scheduling. In Proceedings of the ACM SIGPLAN ’93 conference on programming language design and implementation (pp. 258–267). |
| [12] | Kats, V. & Levner, E. (2003). Polynomial algorithms for periodic scheduling of tasks on parallel processors. In L. Yang & M. Paprzycki (Eds.), Practical applications of parallel computing: advances in computation theory and practice (Vol. 12, pp. 363–370). Nova Science, Canada. |
| [13] | Lam, M. (1988). Software pipelining: an effective scheduling technique for vliw machines. SIGPLAN Notices, 23(7), 318–328. · doi:10.1145/960116.54022 |
| [14] | Leiserson, C. E., & Saxe, J. B. (1991). Retiming synchronous circuitry. Algorithmica, 6, 5–35. · Zbl 0708.94025 · doi:10.1007/BF01759032 |
| [15] | Levner, E., & Kats, V. (1998). A parametric critical path problem and an application for cyclic scheduling. Discrete Applied Mathematics, 87, 149–158. · Zbl 0906.68108 · doi:10.1016/S0166-218X(98)00054-7 |
| [16] | Levner, E., Kats, V., & de Pablo, D. A. L. (2007). Cyclic scheduling in robotic cells: an extension of basic models in machine scheduling theory. In E. Levner (Ed.), Multiprocessor scheduling: theory and applications. (pp. 001–020). I-Tech Education and Publishing: Vienna. |
| [17] | Llosa, J., González, A., Ayguadé, E., & Valero, M. (1996). Swing modulo scheduling: a lifetime-sensitive approach. In Proceedings of the conference on parallel architectures and compilation techniques (pp. 80–86), Boston. |
| [18] | Munier, A., Queyranne, M., & Schulz, A. S. (1998). Approximation bounds for a general class of precedence constrained parallel machine scheduling problems. In IPCO (pp. 367–382). · Zbl 0911.90215 |
| [19] | Proth, J. M., & Xie, X. (1995). Modélisation, analyse et optimisation des systèmes à fonctionnement cyclique. In Les réseaux de Petri pour la conception et la gestion des systèmes de production. Paris: Masson. |
| [20] | Rau, B. R. (1993). Dynamically scheduled VLIW processors. In MICRO 26: proceedings of the 26th annual international symposium on microarchitecture (pp. 80–92). Los Alamitos: IEEE Computer Society Press. |
| [21] | Rau, B. R. (1994). Iterative modulo scheduling: an algorithm for software pipelining loops. In MICRO 27: proceedings of the 27th annual international symposium on microarchitecture (pp. 63–74). New York: ACM. |
| [22] | Robert, Y., & Vivien, F. (2009), Introduction to scheduling. CRC: Boca Raton. |
| [23] | Wang, J., Eisenbeis, C., Jourdan, M., & Su, B. (1994). Decomposed software pipelining: a new perspective and a new approach. International Journal of Parallel Programming, 22(3), 351–373. · doi:10.1007/BF02577737 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
