Skip to main content
SpringerLink
Log in

A cyclic scheduling problem with an undetermined number of parallel identical processors

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

This paper presents two integer linear programming (ILP) models for cyclic scheduling of tasks with unit/general processing time. Our work is motivated by digital signal processing (DSP) applications on FPGAs (Field-Programmable Gate Arrays)—hardware architectures hosting several sets of identical arithmetic units. These hardware units can be formalized as dedicated sets of parallel identical processors. We propose a method to find an optimal periodic schedule of DSP algorithms on such architectures where the number of available arithmetic units must be determined by the scheduling algorithm with respect to the capacity of the FPGA circuit. The emphasis is put on the efficiency of the ILP models. We show the advantages of our models in comparison with common ILP models on benchmarks and randomly generated instances.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bonsma, E., Gerez, S.: 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

  2. Brucker, P., Kampmeyer, T.: Tabu search algorithms for cyclic machine scheduling problems. J. Sched. 8(4), 303–322 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  3. Celoxica Ltd.: Platform Developers Kit: Pipelined Floating-point Library Manual (2004). http://www.celoxica.com

  4. Dongen, V.H., Gao, G.R.: A polynomial time method for optimal software pipelining. Lect. Not. Comput. Sci. 634, 613–624 (1992)

    Google Scholar 

  5. Dupont de Dinechin, B.: Time-indexed formulations and a large neighborhood search for the resource-constrained modulo scheduling problem. In: MISTA’2007, 3rd Multidisciplinary International Scheduling Conference: Theory and Applications, Paris, August 2007

  6. Fan, K., Kublur, M., Park, H., Mahlke, S.: Increasing hardware efficiency with multifunction loop accelerators. In: CODES+ISSS ’06: Proceedings of the 4th International Conference on Hardware/Software Codesign and System Synthesis. ACM Press, New York (2006)

    Google Scholar 

  7. Fettweis, A.: Wave digital filters: theory and practice. Proc. IEEE 74(2), 270–327 (1986)

    Article  Google Scholar 

  8. Fimmel, D., Müller, J.: Optimal software pipelining under resource constraints. J. Found. Comput. Sci. 12(6) (2001)

  9. Franck, B., Neumann, K., Schwindt, C.: Truncated branch-and-bound, schedule-construction, and schedule-improvement procedures for resource-constrained project scheduling. OR Spectr. 23(3), 297–324 (2001)

    MATH  MathSciNet  Google Scholar 

  10. Hanen, C.: Study of a np-hard cyclic scheduling problem: The recurrent job-shop. Eur. J. Oper. Res. 72(1), 82–101 (1994)

    Article  MATH  Google Scholar 

  11. Hanen, C., Munier, A.: A study of the cyclic scheduling problem on parallel processors. Discrete Appl. Math. 57, 167–192 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  12. Heemstra, S.M., Gerez, S.H., Herrmann, O.E.: Fast prototyping of datapath-intensive architectures. IEEE Trans. Circuits Syst. I 39(5), 351–364 (1992)

    Article  MATH  Google Scholar 

  13. ILOG Inc.: CPLEX Version 9.1 (2005). http://www.ilog.com/products/cplex/

  14. Kazuhito, I., Lucke, E., Parhi, K.: ILP based cost-optimal DSP synthesis with module selection and data format conversion. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 6(4) (1999)

  15. Kum, K.-I., Sung, W.: Combined word-length optimization and high-level synthesis of digital signal processing systems. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 20(8), 921–930 (2001)

    Article  Google Scholar 

  16. Matoušek, R., Tichý, M., Pohl, A.Z., Kadlec, J., Softley, C.: Logarithmic number system and floating-point arithmetics on FPGA. In: International Conference on Field-Programmable Logic and Applications (FPL ’02), pp. 627–636 (2002)

  17. Munier, A.: The complexity of a cyclic scheduling problem with identical machines and precedence constraints. Eur. J. Oper. Res. 91(3), 471–480 (1996)

    Article  MATH  Google Scholar 

  18. Paulin, P., Knight, J., Girczyc, E.: Hal: A multi-paradigm approach to automatic data path synthesis. In: 23rd IEEE Design Automation Conf., pp. 263–270, Las Vegas, July 1986

  19. Rabaey, J.M., Chu, C., Hoang, P., Potkonjak, M.: Fast prototyping of datapath-intensive architectures. IEEE Des. Test 8(2), 40–51 (1991)

    Article  Google Scholar 

  20. Rau, B.R., Glaeser, C.D.: Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing. In: MICRO 14: Proceedings of the 14th annual workshop on Microprogramming, pp. 183–198, Piscataway, NJ, USA, 1981

  21. Sindorf, S.L., Gerez, S.H.: 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, Utrecht, The Netherlands, 2000

  22. Šůcha, P., Hanzálek, Z.: Deadline constrained cyclic scheduling on pipelined dedicated processors considering multiprocessor tasks and changeover times. Math. Comput. Model. 47(9–10), 925–942 (2008)

    MATH  Google Scholar 

  23. Šůcha, P., Hanzálek, Z., Heřmánek, A., Schier, J.: Scheduling of iterative algorithms with matrix operations for efficient FPGA design–implementation of finite interval constant modulus algorithm. J. VLSI Signal Process. 46(1), 35–53 (2007)

    Article  Google Scholar 

  24. Vesterbacka, M., Palmkvist, K., Sandberg, P., Wanhammar, L.: Implementation of fast dsp algorithms using bit-serial arithmetic. In: National Conference on Electronic Design Automation, Stockholm, March 1994

  25. West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice-Hall, Englewood Cliffs (2001)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Control Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague, Karlovo namesti 13, Prague 2, Czech Republic

    Přemysl Šůcha & Zdeněk Hanzálek

  2. Merica, Prokopa Holeho 748, 58001, Havlickuv Brod, Czech Republic

    Zdeněk Hanzálek

Authors
  1. Přemysl Šůcha
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zdeněk Hanzálek
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Přemysl Šůcha.

Additional information

This work was supported by the Ministry of Education of the Czech Republic under the Project 2C06017 and Research Programme MSM6840770038.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Šůcha, P., Hanzálek, Z. A cyclic scheduling problem with an undetermined number of parallel identical processors. Comput Optim Appl 48, 71–90 (2011). https://doi.org/10.1007/s10589-009-9239-4

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-009-9239-4

Keywords

Search

Navigation