An enhanced static-list scheduling algorithm for temporal partitioning onto RPUs

• Type: Article in International Conference Proceedings Book
• Date: 2000

Authors

João M. P. Cardoso (Author) Other; Neto, HC (Author) Other

Conference proceedings International

Title: VLSI: SYSTEMS ON A CHIP

Pages: 485-496

IFIP 10th International Conference on Very Large Scale Integration (VLSI 99)

LISBON, PORTUGAL, DEC 01-04, 1999

Indexing

ISI Web of Knowledge - 3 Citations

Other information

Authenticus ID: P-001-29X

DOI: 10.1007/978-0-387-35498-9_43

Abstract (EN): This paper presents a novel algorithm for temporal partitioning of graphs representing a behavioral description. The algorithm is based on an extension of the traditional static-list scheduling that tailors it to resolve both scheduling and temporal partitioning. The nodes to be mapped into a partition are selected based on a statically computed cost model. The cost for each node integrates communication effects, the critical path length, and the possibility of the critical path to hide the delay of parallel nodes. In order to alleviate the runtime there is no dynamic update of the costs. A comparison of the algorithm to other schedulers and with close-to-optimum results obtained with a simulated annealing approach is shown. The presented algorithm has been implemented and the results show that it is robust, effective, and efficient, and when compared to other methods finds very good results in small amounts of CPU time.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 12