Systematic exploration of the space of Jacobi algorithms

Hylke W. van Dijk; Ed F. A. Deprettere

doi:10.1117/12.190851

28 October 1994 Systematic exploration of the space of Jacobi algorithms

Hylke W. van Dijk, Ed F. A. Deprettere

Proceedings Volume 2296, Advanced Signal Processing: Algorithms, Architectures, and Implementations V; (1994) https://doi.org/10.1117/12.190851
Event: SPIE's 1994 International Symposium on Optics, Imaging, and Instrumentation, 1994, San Diego, CA, United States

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.

Citation Download Citation

Hylke W. van Dijk and Ed F. A. Deprettere "Systematic exploration of the space of Jacobi algorithms", Proc. SPIE 2296, Advanced Signal Processing: Algorithms, Architectures, and Implementations V, (28 October 1994); https://doi.org/10.1117/12.190851

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available