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

作者：Sucha Premysl^*; Hanzalek Zdenek

来源：Computational Optimization and Applications, 2011, 48(1): 71-90.

DOI：10.1007/s10589-009-9239-4

• Cyclic scheduling
• Multi-processor scheduling
• Digital signal processing applications

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.

• 出版日期2011-1