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

A Lower-Bound Algorithm for Minimizing Network Communication in Real-Time Systems

Cecilia Ekelin (Institutionen för datorteknik) ; Jan Jonsson (Institutionen för datorteknik)
International Conference on Parallel Processing, 2002. Proceedings. (0190-3918). (2002)
[Konferensbidrag, refereegranskat]

In this paper, we propose a pseudo-polynomial-time lower-bound algorithm for the problem of assigning and scheduling real-time tasks in a distributed system such that the network communication is minimized The key feature of our algorithm is translating the task assignment problem into the so called k-cut problem of a graph, which is known to be solvable in polynomial time for fixed k. Experiments show that the lower bound computed by our algorithm in fact is optimal in up to 89% of the cases and increases the speed of an overall optimization algorithm by a factor of two on average.

Denna post skapades 2013-01-15.
CPL Pubid: 170695


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för datorteknik (2002-2004)



Chalmers infrastruktur