Deadline Constrained Cyclic Scheduling on Pipelined Dedicated Processors Considering Multiprocessor Tasks and Changeover Times
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F08%3A03142089" target="_blank" >RIV/68407700:21230/08:03142089 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Deadline Constrained Cyclic Scheduling on Pipelined Dedicated Processors Considering Multiprocessor Tasks and Changeover Times
Original language description
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 timingconstraints. 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 fromBratley's scheduling problem 1|rj,~dj|Cmax and we suggest a solution based on ILP (Integer Linear Programming) that allows one to minimize the completion time.
Czech name
Cyklické rozvrhování na dedikovaných procesorech uvažující multiprocesorové úlohy a časy na změnu nastavení procesoru
Czech description
Tento článek se zabývá rozvrhováním výpočetních smyček prováděných na HW architekturách obsahující pipelinované dedikované jednotky (např. FPGA). Problém je řešen pomocí celočíselného lineárního programování a výsledky jsou ukázány jak na standardních testovacích instancích, tak i vybrané aplikaci.
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BB - Applied statistics, operational research
OECD FORD branch
—
Result continuities
Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2008
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Mathematical and Computer Modelling
ISSN
0895-7177
e-ISSN
—
Volume of the periodical
47
Issue of the periodical within the volume
9-10
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
18
Pages from-to
—
UT code for WoS article
000255511900011
EID of the result in the Scopus database
—