Premium
Scheduling Algorithms For Hierarchical Data Control Flow Graphs
Author(s) -
Potkonjak Miodrag,
Rabaey Jan M.
Publication year - 1992
Publication title -
international journal of circuit theory and applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.364
H-Index - 52
eISSN - 1097-007X
pISSN - 0098-9886
DOI - 10.1002/cta.4490200303
Subject(s) - computer science , scheduling (production processes) , probabilistic logic , subroutine , algorithm , fair share scheduling , mathematical optimization , distributed computing , quality of service , mathematics , computer network , artificial intelligence , operating system
New algorithms for the allocation, assignment and scheduling of a hierarchical data control flow graph (DCFG) with imposed timing constraints are presented. the hierarchical allocation environment performs a probabilistic search through the design space and converges towards a final solution by iteratively calling and interchanging resource utilisation information with the assignment and scheduling subroutines. The allocation, assignment and scheduling problem is posed in a such a way that the specific costs of all hardware elements are taken into account and simultaneously addressed. the proposed algorithms have novel constructive and rejectionless iterative improvement probabilistic components. The effectiveness of the algorithms is demonstrated with the aid of extensive experimental results. In addition to the standard benchmarks, we have studied a broad class of test examples of a very diverse nature, thus covering the global design space. We also discuss how min‐bound estimations are used to more easily and realistically assess the quality of the allocation, assignment and scheduling algorithms.