Return to d'Auriol's Publication Page
Brian J. d'Auriol and Virendra C. Bhavsar, "Systolic and Wavefront Array Algorithms on Distributed Memory, Multiprocessor Computers", Proc. of Supercomputing Symposium '93-High Performance Computing: New Horizons (SS93), Calgary, Alberta, Canada, 6-9 June, 1993, L. Bauwens (ed), University of Calgary, Calgary, Alberta, pp. 47--54, June, 1993.
The issues of transforming systolic and wavefront algorithms to specific machine-dependent implementations are examined. A brief review of current research in this area indicates that there remain many open questions. A general purpose schema for such implementations which incorporates consistency, efficient use of resources, automatability and wide applicability is proposed. Such a schema is aimed at incorporating it into a compiler for these algorithms. Further, this schema is evaluated by considering a specific systolic algorithm (Weighted Levenshtein Distance) and its implementations. Comments are made about the suitability of the implementations and are accompanied by specific results from actual implementations. An example of actual implementations is given. This example demonstrates some of the potential hazards inherent in any implementation of systolic or wavefront arrays.
Full Paper (pdf: 107KB)