×

Deadline constrained cyclic scheduling on pipelined dedicated processors considering multiprocessor tasks and changeover times. (English) Zbl 1144.90374

Summary: This paper presents a scheduling technique used to optimize computation speed of loops running on architectures that may include pipelined dedicated processors. The problem under consideration is to find an optimal periodic schedule satisfying the timing constraints. Motivated by FPGA (Field-Programmable Gate Array) architecture we formulate a problem of cyclic scheduling on one dedicated processor where tasks are constrained by the precedence delays. Further we generalize this result to the set of dedicated processors. We also show how the set of constraints in both problems can be extended by start time related deadlines, multiprocessor tasks, changeover times and minimization of data transfers. We prove that this problem is NP-hard by reduction from Bratley’s scheduling problem \(1|r_j,\tilde d_j|C_{\max}\) and we suggest a solution based on ILP (Integer Linear Programming) that allows one to minimize the completion time. Besides this, we suggest elimination of redundant constraints and binary variables in a integer linear programming model which leads to a speedup of the scheduling algorithm. Finally, experimental results are shown on an application of recursive least square filter and benchmarks.

MSC:

90B35 Deterministic scheduling theory in operations research
68M14 Distributed systems
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems

Software:

GLPK; Handel-C
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Hanen, C.; Munier, A., A study of the cyclic scheduling problem on parallel processors, Discrete Applied Mathematics, 57, 167-192 (1995) · Zbl 0830.68009
[2] S.L. Sindorf, S.H. Gerez, An integer linear programming approach to the overlapped scheduling of iterative data-flow graphs for target architectures with communication delays, in: PROGRESS 2000 Workshop on Embedded Systems, 2000, pp. 95-104; S.L. Sindorf, S.H. Gerez, An integer linear programming approach to the overlapped scheduling of iterative data-flow graphs for target architectures with communication delays, in: PROGRESS 2000 Workshop on Embedded Systems, 2000, pp. 95-104
[3] Munier, A., The complexity of a cyclic scheduling problem with identical machines and precedence constraints, European Journal of Operational Research, 91, 471-480 (1996) · Zbl 0924.90095
[4] Govindarajan, R.; Altman, E. R.; Gao, G. R., A framework for resource-constrained rate-optimal software pipelining, IEEE Transactions on Parallel and Distributed Systems, 7, 11, 1133-1149 (1996)
[5] Heřmánek, A.; Pohl, Z.; Kadlec, J., FPGA implementation of the adaptive lattice filter, (Field-Programmable Logic and Applications. Field-Programmable Logic and Applications, Lecture Notes in Computer Science, vol. 2778 (2003), Springer: Springer Berlin), 1095-1099
[6] Matoušek, R.; Tichý, M.; Pohl, Z.; Kadlec, J.; Softley, C., Logarithmic number system and floating-point arithmetics on FPGA, (Field-Programmable Logic and Applications: Reconfigurable Computing is Going Mainstream. Field-Programmable Logic and Applications: Reconfigurable Computing is Going Mainstream, Lecture Notes in Computer Science, vol. 2438 (2002), Springer: Springer Berlin), 627-636 · Zbl 1020.68798
[7] Celoxica Ltd., Platform Developers Kit: Pipelined Floating-Point Library Manual. URL http://www.celoxica.com; Celoxica Ltd., Platform Developers Kit: Pipelined Floating-Point Library Manual. URL http://www.celoxica.com
[8] Roy, B., Contribution de la théorie des graphes à l’étude de certains problèmes linéaires, Comptes Rendus Mathématique Académie des Sciences, Paris, 248, 2437-2439 (1959)
[9] R. Bartosinski, M. Daněk, P. Honzík, R. Matoušek, Dynamic reconfiguration in FPGA-based SoC designs, in: FPGA ’05: Proceedings of the 2005 ACM/SIGDA 13th International Symposium on Field-Programmable Gate Arrays, Monterey, CA, USA, 2005, pp. 274-274; R. Bartosinski, M. Daněk, P. Honzík, R. Matoušek, Dynamic reconfiguration in FPGA-based SoC designs, in: FPGA ’05: Proceedings of the 2005 ACM/SIGDA 13th International Symposium on Field-Programmable Gate Arrays, Monterey, CA, USA, 2005, pp. 274-274
[10] P. Šůcha, Z. Pohl, Z. Hanzálek, Scheduling of iterative algorithms on FPGA with pipelined arithmetic unit, in: 10th IEEE Real-Time and Embedded Technology and Applications Symposium, 2004, pp. 404-412; P. Šůcha, Z. Pohl, Z. Hanzálek, Scheduling of iterative algorithms on FPGA with pipelined arithmetic unit, in: 10th IEEE Real-Time and Embedded Technology and Applications Symposium, 2004, pp. 404-412
[11] A. Heřmánek, J. Schier, P. Šůcha, Z. Pohl, Z. Hanzálek, Optimization of finite interval CMA implementation for FPGA, in: IEEE Workshop on Signal Processing Systems, 2005, pp. 75-80; A. Heřmánek, J. Schier, P. Šůcha, Z. Pohl, Z. Hanzálek, Optimization of finite interval CMA implementation for FPGA, in: IEEE Workshop on Signal Processing Systems, 2005, pp. 75-80
[12] B.D. de Dinechin, Simplex scheduling: More than lifetime-sensitive instruction scheduling, in: Proceedings of the International Conference on Parallel Architecture and Compiler Techniques, 1994; B.D. de Dinechin, Simplex scheduling: More than lifetime-sensitive instruction scheduling, in: Proceedings of the International Conference on Parallel Architecture and Compiler Techniques, 1994
[13] M. Lam, Software pipelining: An effective scheduling technique for VLIW machines, in: PLDI ’88: Proceedings of the ACM SIGPLAN 1988 Conference on Programming Language Design and Implementation, 1988, pp. 318-328; M. Lam, Software pipelining: An effective scheduling technique for VLIW machines, in: PLDI ’88: Proceedings of the ACM SIGPLAN 1988 Conference on Programming Language Design and Implementation, 1988, pp. 318-328
[14] B.R. Rau, C.D. Glaeser, Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing, in: Proceedings of the 20th Annual Workshop on Microprogramming and Microarchitecture, 1981; B.R. Rau, C.D. Glaeser, Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing, in: Proceedings of the 20th Annual Workshop on Microprogramming and Microarchitecture, 1981
[15] Dongen, V. H.; Gao, G. R., A polynomial time method for optimal software pipelining, (Lecture Notes in Computer Science (1992), Springer-Verlag), 613-624
[16] Fimmel, D.; Müller, J., Optimal software pipelining under resource constraints, Journal of Foundations of Computer Science, 12, 6, 697-718 (2001) · Zbl 1319.68059
[17] Allan, V. H.; Jones, R. B.; Lee, R. M.; Allan, S. J., Software pipelining, ACM Computing Surveys, 27, 3, 367-432 (1995)
[18] Chao, L.-F.; LaPaugh, A.; Sha, E.-M., Rotation scheduling: A loop pipelining algorithm, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 16, 3, 229-239 (1997)
[19] Chrétienne, P., List schedules for cyclic scheduling, Discrete Applied Mathematics, 94, 1-3, 141-159 (1999) · Zbl 0932.68007
[20] Chrétienne, P., On Graham’s bound for cyclic scheduling, Parallel Computing, 26, 9, 1163-1174 (2000) · Zbl 0945.68012
[21] B.R. Rau, Iterative modulo scheduling: An algorithm for software pipelining loops, in: MICRO 27: Proceedings of the 27th Annual International Symposium on Microarchitecture, New York, NY, USA, 1994, pp. 63-74; B.R. Rau, Iterative modulo scheduling: An algorithm for software pipelining loops, in: MICRO 27: Proceedings of the 27th Annual International Symposium on Microarchitecture, New York, NY, USA, 1994, pp. 63-74
[22] J.M. Codina, J. Llosa, A. Gonzlez, A comparative study of modulo scheduling techniques, in: International Conference on Supercomputing, ICS, 2002, pp. 97-106; J.M. Codina, J. Llosa, A. Gonzlez, A comparative study of modulo scheduling techniques, in: International Conference on Supercomputing, ICS, 2002, pp. 97-106
[23] Kum, W. S.K.-I., Combined word-length optimization and high-level synthesis of digital signal processing systems, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 20, 8, 921-930 (2001)
[24] Kazuhito, I.; Lucke, E.; Parhi, K., ILP based cost-optimal DSP synthesis with module selection and data format conversion, IEEE Transactions on Very Large Scale Integration Systems, 6, 582-594 (1999)
[25] D. Fimmel, J. Müller, A flow graph formulation of optimal software pipelining, in: Proceedings of the Third International Conference on Parallel and Distributed Computing, Applications and Technologies PDCAT, 2002, pp. 422-429; D. Fimmel, J. Müller, A flow graph formulation of optimal software pipelining, in: Proceedings of the Third International Conference on Parallel and Distributed Computing, Applications and Technologies PDCAT, 2002, pp. 422-429
[26] Błazewicz, J.; Ecker, K.; Schmidt, G.; Wȩglarz, J., Scheduling Computer and Manufacturing Processes (2001), Springer-Verlag: Springer-Verlag Heidelberg, Germany · Zbl 0985.90033
[27] Ito, K.; Parhi, K. K., Determining the minimum iteration period of an algorithm, Journal of VLSI Signal Processing Systems, 11, 3, 229-244 (1995)
[28] Lenstra, J. K.; Kan, A. R.; Brucker, P., Complexity of machine scheduling problems, Annals of Operations Research, 343-362 (1977) · Zbl 0353.68067
[29] E.G.P. Paulin, J. Knight, Hal: A multi-paradigm approach to automatic data path synthesis, in: 23rd IEEE Design Automation Conf, Las Vegas, 1986, pp. 263-270; E.G.P. Paulin, J. Knight, Hal: A multi-paradigm approach to automatic data path synthesis, in: 23rd IEEE Design Automation Conf, Las Vegas, 1986, pp. 263-270
[30] P. Šůcha, Z. Hanzálek, Benchmarks for cyclic scheduling from class of digital signal processing algorithms, Tech. Rep., CTU FEL DCE, Prague. http://dce.felk.cvut.cz/sucha/articles/cyclicschedulingbenchmarks.pdf; P. Šůcha, Z. Hanzálek, Benchmarks for cyclic scheduling from class of digital signal processing algorithms, Tech. Rep., CTU FEL DCE, Prague. http://dce.felk.cvut.cz/sucha/articles/cyclicschedulingbenchmarks.pdf
[31] Williams, H. P., Model Building in Mathematical Programming (1999), John Wiley & Sons: John Wiley & Sons New York · Zbl 0384.90079
[32] A. Makhorin, GLPK (GNU Linear Programming Kit) Version 4.4. URL http://www.gnu.org/software/glpk/; A. Makhorin, GLPK (GNU Linear Programming Kit) Version 4.4. URL http://www.gnu.org/software/glpk/
[33] Celoxica Ltd. Handel-C Language Reference Manual. URL http://www.celoxica.com; Celoxica Ltd. Handel-C Language Reference Manual. URL http://www.celoxica.com
[34] Fettweis, A., Wave digital filters: Theory and practice, Proceedings of the IEEE, 74, 270-327 (1986)
[35] E. Bonsma, S. Gerez, A genetic approach to the overlapped scheduling of iterative data-flow graphs for target architectures with communication delays, in: ProRISC Workshop on Circuits, Systems and Signal Processing, 1997, pp. 75-84; E. Bonsma, S. Gerez, A genetic approach to the overlapped scheduling of iterative data-flow graphs for target architectures with communication delays, in: ProRISC Workshop on Circuits, Systems and Signal Processing, 1997, pp. 75-84
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.