Performance Analysis of a Large-Grain Dataflow Scheduling Paradigm

This paper describes and analyzes a paradigm for scheduling com-putations on a network of multiprocessors using large-grain dataj_ow scheduling at run time. The computations to be scheduled must fol-low a static flow graph, while the schedule itself will be dynamic (i.e., determined at run time). Many applications characterized by static flow exist, and they include real-time control and digital signal process-ing. With the advent of computer-aided software engineering (CASE) tools for capturing software designs in dataflow-like structures, macro-dataflow scheduling becomes increasingly attractive, if not necessary. For parallel implementations, using the macro-data]qow method allows the scheduling to be insulated from the application designer and en-ables the maximum utilization of available resources. Further, by allow-ing multitasking, processor utilizations can approach 100 percent while they maintain maximum speedup. Extensive simulation studies are per-formed on _-, 8-, and 16-processor architectures that reflect the effects of communication delays, scheduling delays, algorithm class, and mul-titasking on performance and speedup gains. 1