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

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

0.00 Avg rating0 Votes
Article ID: iaor20111340
Volume: 48
Issue: 1
Start Page Number: 71
End Page Number: 90
Publication Date: Jan 2011
Journal: Computational Optimization and Applications
Authors: ,
Keywords: programming: integer
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.

Reviews

Required fields are marked *. Your email address will not be published.