CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Effective Complexity Reduction for Optimal Scheduling of Distributed Real-Time Applications

Jan Jonsson (Institutionen för datorteknik)
Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, Austin, Texas, May 31 – June 5, 1999 p. 360–369. (1999)
[Konferensbidrag, refereegranskat]

The application of optimal search strategies to scheduling for distributed real-time systems is, in general, plagued by an inherent computational complexity. This has effectively prevented the integration of strategies such as branch-and-bound (B&B) in scheduling frameworks and tools used in practice today. To show that optimal scheduling is, in fact, a viable alternative for many real-time scheduling scenarios, we propose an approach that can reduce the average search complexity to levels comparable with that of a polynomial-time heuristic.Our approach is based on making intelligent choices in the selection of strategies for search tree vertex traversal and task deadline assignment. More specifically, we conjecture that effective complexity reduction is achieved by (i) traversing vertices in the search tree in a depth-first fashion and (ii) assigning local task deadlines that are non-overlapping fractions of the application end-to-end deadline.Through an extensive experimental study, we find that our approach contribute to reducing the average search complexity by several orders of magnitude for a frequently-used class of distributed real-time applications.

Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2011-04-14.
CPL Pubid: 139107


Institutioner (Chalmers)

Institutionen för datorteknik (1985-2001)


Informations- och kommunikationsteknik
Datavetenskap (datalogi)

Chalmers infrastruktur