Orbital Systolic Algorithms and Array Processors for Solution of the Algebraic Path Problem

Stanislav G. SEDUKHIN  Toshiaki MIYAZAKI  Kenichi KURODA  

IEICE TRANSACTIONS on Information and Systems   Vol.E93-D   No.3   pp.534-541
Publication Date: 2010/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E93.D.534
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computation and Computational Models
algebraic path problem,  orbital systolic algorithms,  array processors,  data manipulation,  

Full Text: PDF(631.9KB)>>
Buy this Article

The algebraic path problem (APP) is a general framework which unifies several solution procedures for a number of well-known matrix and graph problems. In this paper, we present a new 3-dimensional (3-D) orbital algebraic path algorithm and corresponding 2-D toroidal array processors which solve the nn APP in the theoretically minimal number of 3n time-steps. The coordinated time-space scheduling of the computing and data movement in this 3-D algorithm is based on the modular function which preserves the main technological advantages of systolic processing: simplicity, regularity, locality of communications, pipelining, etc. Our design of the 2-D systolic array processors is based on a classical 3-D2-D space transformation. We have also shown how a data manipulation (copying and alignment) can be effectively implemented in these array processors in a massively-parallel fashion by using a matrix-matrix multiply-add operation.