This monograph evolved from my Ph. D dissertation completed at the Laboratory of Computer Science, MIT, during the Summer of 1986. In my dissertation I proposed a pipelined code mapping scheme for array operations on static dataflow architectures. The main addition to this work is found in Chapter 12, reflecting new research results developed during the last three years since I joined McGill University-results based upon the principles in my dissertation. The terminology dataflow soft ware pipelining has been consistently used since publication of our 1988 paper on the argument-fetching dataflow architecture model at McGill University [43]. In the first part of this book we describe the static data flow graph model as an operational model for concurrent computation. We look at timing considerations for program graph execution on an ideal static dataflow computer, examine the notion of pipe lining, and characterize its performance. We discuss balancing techniques used to transform certain graphs into fully pipelined data flow graphs. In particular, we show how optimal balancing of an acyclic data flow graph can be formulated as a linear programming problem for which an optimal solution exists. As a major result, we show the optimal balancing problem of acyclic data flow graphs is reduceable to a class of linear programming problem, the net work flow problem, for which well-known efficient algorithms exist. This result disproves the conjecture that such problems are computationally hard.

The book includes papers on massively parallel distributed memory and multithreaded architecture design, synchronization and pipelined design, and superpipelined data-driven VLSI processors. Other sections discuss stream data types, the development of well-structured software, and parallelization of dataflow programs.

Abstract: "An efficient static dataflow architecture based on an argument-fetching data-driven principle has recently been proposed (as reported by Dennis and Gao [5]). This architecture opens possibilities in combining the techniques of existing high-performance conventional pipelined architectures with the strengths of the dataflow model of parallel computation. The key feature is that data never 'flows' in the new architecture even though instruction scheduling remains data-driven. The new architecture answers some speculations about the efficiency of practical dataflow architectures -- data-driven instruction scheduling need not mean higher traffic due to data token flow in the processor architecture.

A detailed analysis based on simulation results is presented, focusing on two key architectural factors -- the fine-grain synchronization capacity and the scheduling mechanism for enabling instructions. On one hand, our results provide experimental evidence that software pipelining is an effective method for exploiting fine-grain parallelism in loops. On the other, the experiments have also revealed the (somewhat pessimistic) fact that even a fully software pipelined code may not achieve good performance if the overhead for fine-grain synchronization exceeds the capacity of the machine."