Resource Considerations during Parallel Scheduling of Large Control Flow Dominated Applications

This paper presents a technique to determine the possible parallelism between different control-structures in large hierarchical Control- and Data-Flow Graphs (CDFGs). The technique is based on a hierarchical bottom-up heuristic, which after resolving data- and control-dependencies between control-structures, parallelizes selected control-structures , subject to minimizing resource consumption. The purpose of the technique is to be able to predict resource consumption and estimate execution time for large CDFGs. The technique has been tested on several CDFGs with up to 1442 nodes. The results indicate that the technique performs well; for one example it estimated a total speed-up of 44% at the expense of an estimated resource overhead of -0.1 and in general the speed-up ranges from 8% to 44%.