PIPELINING TECHNIQUE AND PIPELINED PROCESSES

摘要

A method of (and related apparatus for) pipelining the execution of selected operations in an n-dimensional array of processor cells having at least 2n nodes with at least one processor per node. Each processor cell includes memory means and a processor element for producing an output depending at least in part of data read from said memory means and instruction information supplied to the cell. Each processor cell is identified by an address in the array, which specifies the location of the processor cell within the dimensionality of the array. The array is operated so as to provide processing time slots during which the processor cells execute said operations and communications time slots during which the processors transmit information to each other. During each communications time slot, each processor can receive one bit of data from only one other processor (i.e., the preceding stage) along an edge dimension ''d'' of the n-cube; and each processor can transmit only one bit of data to only one other processor, along edge dimension d + 1. A data value for an element of an input data array is supplied to the memory of each node. Then for each of a series of successive time slots, each of a set of first processor cells executes said operation on a selected bit of the argument in the memory of its node, in accordance with a bit received from a first other processor cell, and transmits the result of said operation to a second other processor cell, until the final result appears at a predetermined node. The computation (i.e., selected operation) performed by the processors is identical for all processors, but may be conditional. Algorithms which can be converted into an appropriate form for pipelining in this fashion include those which (1) can be implemented by sending information along only one dimension in the array at a time and (2) send information along successive dimensions whose dimension numbers form an arithmetic sequence. Further, for an algorithm to be appropriate for (i.e., efficiently suited for) such pipelining, it must be possible to start performing the underlying computation without having all "M" bits of the data words available. A number of exemplary pipeline algorithms are disclosed, including addition of several terms in an array (i.e., sum reduction) and partial sum generation of the terms in an array (i.e., parallel prefix-sum).