Optimal mapping of systolic algorithms by regular instruction shifts

Author

Clauss, Philippe ; Perrin, Guy-René

Author_Institution

Robert Schuman Univ., Strasbourg, France

fYear

1994

fDate

22-24 Aug 1994

Firstpage

224

Lastpage

235

Abstract

This paper addresses the problem of determining efficient mappings of systems of affine recurrence equations into regular arrays, in a nearly space-optimal fashion. A new nonlinear allocation technique is presented: the Instruction Shift. It allows to synthesize planar regular arrays without increasing the initial linear schedule. This technique is illustrated with the LL^t Cholesky factorization

Keywords

computational geometry; distributed memory systems; equations; matrix algebra; optimisation; parallel algorithms; systolic arrays; Cholesky factorization; Instruction Shift; affine recurrence equations; distributed memory multiprocessors; geometric modelling; linear schedule; nonlinear allocation technique; optimal mapping; planar regular array synthesis; regular arrays; regular instruction shifts; systolic algorithms; Computer aided instruction; Concurrent computing; Data processing; Difference equations; Distributed computing; Integral equations; Processor scheduling; Scalability; Signal processing; Systolic arrays;

fLanguage

English

Publisher

ieee

Conference_Titel

Application Specific Array Processors, 1994. Proceedings. International Conference on

Conference_Location

San Francisco, CA

ISSN

1063-6862

Print_ISBN

0-8186-6517-3

Type

conf

DOI

10.1109/ASAP.1994.331801

Filename

331801