In: IEEE Transactions on Parallel and Distributed Systems, Vol. 1, No. 4, pages 470-485. 1990.
Abstract: The basic concept of pipelined data-parallel algorithms is introduced by contrasting the algorithms with other styles of computation. Pipelined data-parallel algorithms are a class of algorithms which use pipelined operations and data level partitioning to achieve parallelism. Applications which involve data parallelism and recurrence relations are good candidates for this kind of algorithm. An analytic model is presented for modeling pipelined data-parallel computation on multicomputers. The model uses timed Petri nets to describe data pipelining operations. As a case study, the model is applied to a pipelined matrix multiplication algorithm.
Keywords: pipelined data parallel algorithm; multicomputer; timed net; pipelined matrix multiplication algorithm.