Cyklické rozvrhování na dedikovaných procesorech uvažující multiprocesorové úlohy a časy na změnu nastavení procesoru

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Deadline Constrained Cyclic Scheduling on Pipelined Dedicated Processors Considering Multiprocessor Tasks and Changeover Times

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Deadline Constrained Cyclic Scheduling on Pipelined Dedicated Processors Considering Multiprocessor Tasks and Changeover Times

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BB - Aplikovaná statistika, operační výzkum

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2008

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Mathematical and Computer Modelling

ISSN

0895-7177

e-ISSN

—

Svazek periodika

47

Číslo periodika v rámci svazku

9-10

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

18

Strana od-do

—

Kód UT WoS článku

000255511900011

EID výsledku v databázi Scopus

—