Paper Info
Title
A cyclic scheduling problem with an undetermined number of parallel identical processors
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.
Year
DOI
Venue
2011
10.1007/s10589-009-9239-4
Comp. Opt. and Appl.
Keywords
Field
DocType
Cyclic scheduling,Multi-processor scheduling,Digital signal processing applications
Digital signal processing,Fair-share scheduling,Scheduling (computing),Computer science,Parallel computing,Field-programmable gate array,Two-level scheduling,Integer programming,Rate-monotonic scheduling,Periodic graph (geometry)
Journal
Volume
Issue
ISSN
48
1
0926-6003
Citations 
PageRank 
References 
5
0.46
13
Authors
2
Name
Order
Citations
PageRank
sůcha přemysl17413.96
Zdenk Hanzálek2576.67