Name
Title | ||
|---|---|---|
Scheduling of tasks with precedence delays and relative deadlines framework for time-optimal dynamic reconfiguration of FPGAs |
Abstract | ||
|---|---|---|
This paper is motivated by existing architectures of field programmable gate arrays (FPGAs). To facilitate the design process we present an optimal scheduling algorithm using a very universal framework, where tasks are constrained by precedence delays and relative deadlines. The precedence relations are given by an oriented graph, where tasks are represented by nodes. Edges in the graph are related either to the minimum time or to the maximum time elapsed between the start times of the tasks. This framework is used to model the runtime dynamic reconfiguration, synchronization with an on-chip processor and simultaneous availability of arithmetic units and SRAM memory. The NPhard problem of finding an optimal schedule satisfying the timing and resource constraints while minimizing the makespan Cmax, is solved using two approaches. The first one is based on Integer Linear Programming and the second one is implemented as a Branch and Bound algorithm. Experimental results show the efficiency comparison of the ILP and Branch and Bound solutions. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1109/IPDPS.2006.1639388 | IPDPS |
Keywords | Field | DocType |
time-optimal dynamic reconfiguration,minimum time,optimal schedule,start time,bound algorithm,oriented graph,relative deadline,optimal scheduling algorithm,precedence relation,precedence delay,maximum time,bound solution,integer programming,np hard problem,computational complexity,linear programming,scheduling,design process,arithmetic,scheduling algorithm,fpga,algorithm design and analysis,chip,dynamic scheduling,high level synthesis,availability,process design,field programmable gate arrays,branch and bound,field programmable gate array,branch and bound algorithm,satisfiability,integer linear programming | Branch and bound,Algorithm design,Job shop scheduling,Computer science,Scheduling (computing),Parallel computing,Integer programming,Linear programming,Dynamic priority scheduling,Control reconfiguration,Distributed computing | Conference |
ISBN | Citations | PageRank |
1-4244-0054-6 | 4 | 0.43 |
References | Authors | |
24 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| sůcha přemysl | 1 | 74 | 13.96 |
| hanzalek zdeněk | 2 | 101 | 22.42 |