Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Near-optimal scheduling of synchronous data-flow graphs by exact calculation of inter-processor communication costs

: Rosner, S.; Scholles, M.; Forchel, D.


Hertzberger, B.; Sloot, P.:
High-performance computing and networking. International Conference and Exhibition 1997. Proceedings
Berlin: Springer, 1997 (Lecture Notes in Computer Science 1225)
ISBN: 3-540-62898-3
ISSN: 0302-9743
S.987-988 : Lit.
International Conference and Exhibition on High-Performance Computing and Networking (HPCN Europe) <1997, Wien>
Fraunhofer IMS, Außenstelle Dresden ( IPMS) ()
Kommunikation; Parallelverarbeitung; Rekonfigurierbarkeit; scheduling; Topologie

In this contribution we present an optimised method for mapping of data-flow graphs onto parallel processor networks. Its main advantage is the exact consideration of overhead times for data exchange within the network. Therefore, the well known Dynamic Level Scheduler has been extended by a software router which is capable of calculating communication costs for all commonly used network topologies. This task is based on a special minimal routing algorithm for reconfigurable processor networks. Comparisons between the original and our modified scheduling algorithm will show significant reduction of makespan. A possible integration of the algorithm in software environments for parallel processing will be demonstrated by means of the framework PTOLEMY.