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

Stanislav G. SEDUKHIN; Toshiaki MIYAZAKI; Kenichi KURODA

doi:10.1587/transinf.E93.D.534

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

Stanislav G. SEDUKHIN, Toshiaki MIYAZAKI, Kenichi KURODA

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E93-D No.3 pp.534-541

Publication Date: 2010/03/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.E93.D.534

Type of Manuscript: PAPER

Category: Computation and Computational Models

Cite this

Copy

Stanislav G. SEDUKHIN, Toshiaki MIYAZAKI, Kenichi KURODA, "Orbital Systolic Algorithms and Array Processors for Solution of the Algebraic Path Problem" in IEICE TRANSACTIONS on Information, vol. E93-D, no. 3, pp. 534-541, March 2010, doi: 10.1587/transinf.E93.D.534.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E93.D.534/_p

Copy

@ARTICLE{e93-d_3_534,
author={Stanislav G. SEDUKHIN, Toshiaki MIYAZAKI, Kenichi KURODA, },
journal={IEICE TRANSACTIONS on Information},
title={Orbital Systolic Algorithms and Array Processors for Solution of the Algebraic Path Problem},
year={2010},
volume={E93-D},
number={3},
pages={534-541},
abstract={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.},
keywords={},
doi={10.1587/transinf.E93.D.534},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - Orbital Systolic Algorithms and Array Processors for Solution of the Algebraic Path Problem
T2 - IEICE TRANSACTIONS on Information
SP - 534
EP - 541
AU - Stanislav G. SEDUKHIN
AU - Toshiaki MIYAZAKI
AU - Kenichi KURODA
PY - 2010
DO - 10.1587/transinf.E93.D.534
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E93-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2010
AB - 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.
ER -