Algorithm transformations for the data broadcast elimination method

VLSI technology has had tremendous success in revolutionizing computer desi gn with processor arrays. Local communication and interconnection is a cons traint that dictates the design of processor arrays. The shared bus and glo bal access to memory are now no longer used, since they lower the speed. Co nsequently, parallel algorithms must be designed according to these constra ints. One of the problems that must be resolved for the above mentioned constrain ts is data broadcast elimination. Algorithms must be transformed into a for m that uses data propagation instead of data broadcast. Here systems of affine recurrence equations are analyzed and data broadcast is defined in context of the definition of data dependence and affine recu rrence equations. A method for data broadcast elimination is introduced in [I] and expands the system of affine recurrence equations into new recurren ce equations, that define data propagation and eliminates the data dependen ces where data broadcast occurs. Parallel algorithms are usually given as a set of similar tasks repetitivel y performed on different data. The iteration form of presenting the algorit hms is most common. Several techniques are introduced to transform the algo rithm to a single assignment form of recurrence equations. Some improvements of these techniques are presented to make the application of the data broadcast elimination method easier and more straight forward. The presented techniques are classified as the transformation of iterative algorithms to a recurrence form, the transformation of recurrence form to a single assignment form, and fulfilling the index forms of the algorithms. A system of affine recurrence equations with the data broadcast property is always obtained by applying these procedures. The method of data broadcast elimination successfully transforms this system of affine recurrence equat ions into a system of uniform recurrence equations which can be used for pa rallel implementation on VLSI processor arrays.