Loop allocation scheme for multithreaded dataflow computers

The dataflow model of processing, in general, and recent direction to combine dataflow processing with control-flow processing, in particular, provide attractive alternatives to satisfy the computational demand of new applications, without experiencing the shortcomings of the traditional concurrent systems. This should motivate researchers to analyze the applicability of the familiar concepts within this new architectural framework-scheduling and load balancing. Run-time overhead of detection and allocation of dynamic parallelism in a program can easily offset the performance gain. However, the difficult task of accurate estimation of the run-time parallelism during the compile-time is a stumbling block to the static approach. As a compromise, we propose an allocation policy which detects dynamic parallelism for a selected group of program constructs during compile-time and allocates them to the estimated hardware resources in a staggered fashion. The proposed staggered scheme is simulated and its performance is compared against some other schemes proposed in the literature. It has been shown that the proposed scheme offers order of magnitude performance improvement over the cyclic distribution