Name
Abstract | ||
|---|---|---|
We present a SAT-based approach to the task and message allocation problem of distributed real-time systems with hierarchical architectures. In contrast to the heuristic approaches usually applied to this problem, our approach is guaranteed to find an optimal allocation for realistic task systems running on complex target architectures. Our method is based on the transformation of such scheduling problems into nonlinear integer optimization problems. The core of the numerical optimization procedure we use to discharge those problems is a solver for arbitrary Boolean combinations of integer constraints. Optimal solutions are obtained by imposing a binary search scheme on top of that solver. Experiments show the applicability of our approach to industrial-size task systems, which are mapped to heterogeneous hierarchical hardware architectures. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1109/IPDPS.2006.1639420 | IPDPS |
Keywords | Field | DocType |
hierarchical architecture,nonlinear integer optimization problem,realistic task system,integer constraint,numerical optimization procedure,sat-based approach,optimal approach,task allocation problem,message allocation problem,heterogeneous hierarchical hardware architecture,task system,optimal allocation,hardware architecture,hardware,cost function,network topology,distributed computing,job shop scheduling,real time systems,nonlinear programming,computability,distributed processing,scheduling problem,computer architecture,constraint optimization,integer programming,optimization problem,computer science,binary search | Metrical task system,Heuristic,Mathematical optimization,Job shop scheduling,Computer science,Parallel computing,Nonlinear programming,Integer programming,Solver,Binary search algorithm,Optimization problem,Distributed computing | Conference |
ISBN | Citations | PageRank |
1-4244-0054-6 | 3 | 0.43 |
References | Authors | |
11 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexander Metzner | 1 | 66 | 5.50 |
| Martin Fränzle | 2 | 786 | 61.58 |
| Christian Herde | 3 | 338 | 15.19 |
| Ingo Stierand | 4 | 62 | 41.67 |