Share Email Print

Proceedings Paper

Systematic exploration of the space of Jacobi algorithms
Author(s): Hylke W. van Dijk; Ed F. A. Deprettere
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

The ordering of operations in the execution of Jacobi-type algorithms is not unique. Given a sequential imperative program specification of a Jacobi algorithm, there is a method of transformational reasoning to convert the program to any one of a set of input-output equivalent concurrent programs. The method explores associativity and (pseudo) commutativity properties in the algorithm to tune the program's critical path length to an optimal throughput in a desired parallel implementation. The method constructs a certain precedence graph in which vertices represent elementary transformation steps and edges expose step precedence relations. Every feasible cut-set of the precedence graph yields a dependence graph of a concurrent program which is input-output equivalent to the given one. Moreover, regular dependence graphs will be transformed into regular dependence graphs if the cut-set is chosen to keep that property invariant. The method has been successfully applied to time adaptive algorithms in which QR, inverse QR and SVD Jacobi algorithms play a crucial role. The time adaptive SVD algorithm will be used in this paper to illustrate the power of the method. Starting off with the well known cyclic by rows Kogbetliantz program, the transformations gradually decrease its critical path thereby providing various alternative concurrent programs with correspondingly increasing parallel implementation throughput.

Paper Details

Date Published: 28 October 1994
PDF: 15 pages
Proc. SPIE 2296, Advanced Signal Processing: Algorithms, Architectures, and Implementations V, (28 October 1994); doi: 10.1117/12.190851
Show Author Affiliations
Hylke W. van Dijk, Delft Univ. of Technology (Netherlands)
Ed F. A. Deprettere, Delft Univ. of Technology (Netherlands)

Published in SPIE Proceedings Vol. 2296:
Advanced Signal Processing: Algorithms, Architectures, and Implementations V
Franklin T. Luk, Editor(s)

© SPIE. Terms of Use
Back to Top