An Approach To Program Representation OfThe R&F Systolic LU-factorizationAlgorithm
Michael P. Bekakos · WIT transactions on information and communication technologies · 1970
In this work, we view systolic algorithms as programs, each consisting of a multiple assignment statement that describes the algorithmic operation and the synchronous data movement between the nodes of the systolic architecture. We carry out the development of the LU-factorization algorithm for band matrices using the R&F technique (Bekakos and Evans [9], [2]) and applying for its design a traditional program development technique based on an invariant. INTRODUCTION One of the most significant fields in the area of parallel processing is that of systolic algorithms, which are usually illustrated by snapshots of nodes and lines, descriptions of processing at each node in the snapshot and data movement between nodes. A pictorial representation of an algorithm does not lead itself readily to a proof of correctness, although it suggests that it can be implemented on a VLSI chip. From all the above it becomes apparent that we do not attempt to propose a VLSI design methodology for systolic algorithms, because we do not consider many of the limitations that would be imposed by any real system. Although such a sort of proposal concerns a later stage in the design, through the use of a traditional program development technique, for the R&F method, a design methodology seems that could be derived mechanically. The primary contribution of this work is the representation of the R&F systolic LU-factorization algorithm by a program derived from an invariant. Transactions on Information and Communications Technologies vol 3, © 1993 WIT Press, www.witpress.com, ISSN 1743-3517 368 Applications of Supercomputers in Engineering SYSTOLIC ALGORITHM REPRESENTATION Multiple Assignment Statements Our program will make use of multiple assignment statements. A multiple assignment statement of the form, x,y:=f(x',y),g(x,y'), assigns f(x, y) and g(x ,y) to x, y, respectively, where x ,y are the values of x, y prior to the execution of the statement. We shall allow the right sides of assignments to be conditional expressions, e.g. 0, if a > 0 <:= i 1, if a < 0