Maximum pipelining of array computation: A pipelined code mapping scheme for dataflow computers

Despite the attractive features of data flow computers, skepticism exists concerning their efficiency in handling arrays (vectors) in high performance scientific computation. This paper argues that massive parallelism in vector computation can be exploited effectively utilizing data flow principles. The key is to organize the data flow machine program graph such that array operations can be fully pipelined. Unlike in conventional pipelined vector processors, there is no requirement that the activities belonging to the same vector operation be continuously processed by one or a group of physically tightly-coupled function units in the processor. The applicative nature of the data flow graph model allows flexible scheduling of the execution of enabled instructions in the pipeline data flow programs. Accordingly, program transformation can be performed on the basis of both the global and local data flow analysis to generate efficient pipelined data flow machine code. As a result of such fine-grain parallelism embedded in a pipelined data flow machine program, the activities of many vector operations can overlap each other, performing operations on different elements of different arrays concurrently. A pipelined code mapping scheme for transforming array operations in high-level language programs into pipelined data flow machine programs is described. The paper shows that the optimal balancing for such data flow graphs can be formulated into certain linear programming problems which have efficient algorithmic solutions. The machine architecture support for efficient pipelining is briefly addressed.