On scheduling, granularity and state operations of hybrid data-driven/control-driven systems
Paraskevas Evripidou, Jean‐Luc Gaudiot · 1990
This dissertation addresses issues of scheduling, state-operations and actor granularity for data-driven and hybrid data-driven/control-driven systems. We propose block scheduling techniques for iterative algorithms and a graph-level priority mechanism for loop-based algorithms. A general framework has been developed for incorporating general purpose Input/Output operations in the dynamic data-flow environment. Variable resolution graphs are introduced which retain the dynamic data-flow principles of execution at the coarser level and employ control level at the finer level. We have also proposed and developed the Decoupled Graph Computation (DGC) model of execution and architecture. The block scheduling techniques enable the dynamic interpreter to unravel a block of n iterations instead of merely one and thus, exploit parallelism across successive iterations. A look-ahead estimator, based on the observed convergence rate of the algorithm, calculates the optimal block sizes at execution time. A graph-level priority scheduling mechanism has been developed that favors early iterations. This improves resource utilization and yields higher performance. The very asynchronous nature of the data-flow model of execution introduces conflicts when state tasks (such as I/O operations) must share common data objects. In order to execute I/O operations safely and in parallel, an algorithm to detect and classify cases of potential conflicts (hazards) has been developed. It is based upon localizing the effect of I/O operations by splitting the data-flow graph into two subgraphs: (a) the computation subgraph, and (b) the I/O subgraph. The scheme presented here enables the creation and interaction of both subgraphs, which in turn yields a deterministic execution. Furthermore, a distributed file-pointers scheme has been adopted that enables the parallel execution of I/O operations as permitted by data dependencies. We have also developed a hybrid multiprocessor architecture that combines the advantages of the dynamic data-flow principles of execution with those of the control-flow model of execution. Two major design ideas are utilized by the proposed model: decoupled execution of graph and computation operations, and variable-resolution actors. The independence of the two main units of the machine allows an efficient implementation of functional/data-flow principles with conventional, mature technology and reduces the latency penalty incurred due to the graph (overhead) operations. The compiler generates graphs with variable-sized actors that exploit locality and matches the characteristics of the application to the target machine. (Copies available exclusively from Micrographics Department, Doheny Library, USC, Los Angeles, CA 90089-0182.)