Accession Number : ADA181613

Title :   Transformation of Broadcasting Into Pipelining.

Descriptive Note : Research rept.,

Corporate Author : YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE

Personal Author(s) : Wong,Yiwan ; Delosme,Jean-Marc

PDF Url : ADA181613

Report Date : Jun 1987

Pagination or Media Count : 34

Abstract : A characteristic shared by many computation intensive algorithms is the repeated usage of a few data values in a sequence of computations. An efficient parallel implementation of these data dependences often requires the simultaneous transfer, or broadcasting, of the data values to all the processors that need them. Unfortunately, direct realization of this broadcasting operation on VLSI processor arrays, especially on systolic arrays, usually results in severe performance degradation. A technique for decomposing broadcasting dependences into propagation dependences at the algorithm level is presented in this paper. Such propagation dependences, when physically realized, result in pipelining. The determination of a feasible propagation scheme is formulated as a linear algebra problem. It is proven that all broadcastings can be decomposed into propagations and we propose a systematic method for finding such decompositions.

Descriptors :   *ALGORITHMS, *COMPUTATIONS, *PROCESSING EQUIPMENT, *COMPUTER ARCHITECTURE, ARRAYS, DEGRADATION, HIGH RATE, INTENSITY, LINEAR ALGEBRA, LINEARITY, OPERATION, PROPAGATION, RADIO BROADCASTING, SEQUENCES, SYNCHRONISM, TRANSFER, TRANSFORMATIONS

Subject Categories : Computer Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE