Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

A look-ahead scheduler capable of trading scheduling complexity against application performance

 
: Poetschke, H.; Rosner, S.; Scholles, M.

European Association for Microprocessing and Microprogramming:
International Conference on Massively Parallel Computing Systems 1998. Preliminary proceedings
Colorado Springs, Colo., 1998
International Conference on Massively Parallel Computing Systems (MPCS) <3, 1998, Colorado Springs/Colo.>
Englisch
Konferenzbeitrag
Fraunhofer IMS, Außenstelle Dresden ( IPMS) ()
Kommunikation; Parallelverarbeitung; Rekonfigurierbarkeit; scheduling; Topologie

Abstract
Published scheduling algorithms have a fixed complexity. Hence, a range of different scheduling tools has to be implemented according to whether short scheduling times for prototyping or nearoptimal solutions for real-time computing are required. To overcome this obstacle, a new scheduling algorithm is proposed, which balances computational complexity against the quality of the schedule. This is achieved by evaluating the consequences of a scheduling decision for the next k scheduling steps. Comparisons with the iterative Declustering algorithm and the Dynamic Level list scheduler show that the length of a schedule can be considerably shortened even for a moderate number of look-ahead steps. The best improvements are obtained in the presence of strong resource contention, i.e. when hardware resources are maximally utilized. This observation is very promising for practical applications and may reduce the amount of hardware necessary for a real-time implementation of the application.

: http://publica.fraunhofer.de/dokumente/PX-22405.html