D:\sbornik\...\STSAS.DVI


Mathematical Problems of Computer Science 23, 2004, 47{53.

On a Softwar e T ool for I mplementation of Systolic

Algor ithms in the Cluster E nvir onment ¤

E d m o n M. D a vt ya n

Institue for Informatics and Automation Problems of NAS of RA

e-mail edmon@ipia.sci.am

Abstract

In this paper a software tool SAS (Systolic Algorithm Simulator) is designed to
model the work of a one-dimensional systolic array of n cells on a homogenous com-
putational cluster of m ¿ n processors. As a result of the program execution, a
cluster-based programming module is obtained, where computational resourses of the
system are used in an e®ective way.

Refer ences

[1 ] E .D a vt ya n . On t h e Mo d e llin g o f On e Cla s s o f S ys t o lic S t r u c t u r e s o n a P C Clu s t e r . In
p r o c e e d in g s o f CS IT-2 0 0 3 , p p . 3 4 0 -3 4 4 .

[2 ] E d m o n M. D a vt ya n . On t h e Co n s t r u c t io n o f Clu s t e r S ys t o lic A r r a ys . TR A N S A CTION S
o f IIA P N A S R A ,Y e r e va n , 2 0 0 4 ( in t h is is s u e ) .

[3 ] P a r o s h A b d u la . D e c id a b le a n d U n d e c id a b le P r o b le m s in S ys t o lic Cir c u it V e r ī c a t io n .
A CM In t e r n a t io n a l W o r ks h o p o n Fo r m a l V L S I D e s ig n , Mia m i, Flo r id a , Ja n u a r y 1 9 9 1 .

[4 ] Âîåâîäèí Â.Â., Âîåâîäèí Âë.Â. Ïàðàëëåëüíûå âû÷èñëåíèÿ. - ÑÏá.: ÁÕ -
Ïåòåðáóðã, 2002. - 608 ñ.: ISBN 5-94157-160-7.

[5 ] Êîðíååâ Â. Ïàðàëëåëüíîå ïðîãðàììèðîâàíèå â MPI. Ìîñêâà-Èæåâñê:
Èíñòèòóò êîìïüþòåðíûõ èññëåäîâàíèé, 2003, 203 ñ.

[6 ] L . B o a s s o n , P . Ce g ie ls ki, I. Gu e s s a r ia n , Y u . Ma t iya s e vic h . W in d o w-A c c u m u la t e d S u b s e -
qu e n c e Ma t c h in g P r o b le m is L in e a r . CS IT Co n fe r e n c e 2 0 0 1 , Y e r e va n , A r m e n ia , S e p t e m -
b e r 1 7 -2 0 , p p . 7 4 -8 7 .

[7 ] m p ic h : h t t p :/ / www-u n ix.m c s .a n l.g o v/ m p i/ m p ic h

[8 ] m p ic h -g m : h t t p :/ / www.m yr i.c o m / s c s

¤This research is supported by INTAS - 0447, ISTC - 823 grants and 04.10.31 Target Program of RA.

4 7



4 8 On a Software Tool for Implementation of Systolic Algorithms in the Cluster Environment

Îɳëï»ñÇ ÙÇç³í³ÛñáõÙ ëÇëïáÉÇÏ ³É·áñÇÃÙÝ»ñÇ Çñ³Ï³Ý³óÙ³Ý
Íñ³·ñ³ÛÇÝ ·áñÍÇù³ÛÇÝ ÙÇçáóÇ Ù³ëÇÝ

¾. Ø. ¸³íÃÛ³Ý

²Ù÷á÷áõÙ

Øß³Ïí³Í ¿ SAS (Systolic Algorithm Simulator) Íñ³·ñ³ÛÇÝ ·áñÍÇù³ÛÇÝ ÙÇçáóÁ, áñÁ
ÙṻɳíáñáõÙ ¿ n »ñϳñáõÃÛáõÝ áõÝ»óáÕ Ùdzã³÷ ëÇëïáÉÇÏ ½³Ý·í³ÍÇ ³ß˳ï³ÝùÁ
m ¿ n åñáó»ëáñÝ»ñÇó µ³Õϳó³Í ѳٳë»é ѳßíáÕ³Ï³Ý Ïɳëï»ñÇ íñ³: Ìñ³·ñÇ
³ß˳ï³ÝùÇ ³ñ¹ÛáõÝùáõÙ ëï³óíáõÙ ¿ Ïɳëï»ñÇ íñ³ ³ß˳ïáÕ Íñ³·ñ³ÛÇÝ Ùá¹áõÉ, áñÁ
¿ý»ÏïÇí Ï»ñåáí ¿ û·ï³·áñÍáõ٠ѳٳϳñ·Ç ѳßíáÕ³Ï³Ý é»ëáõñëÝ»ñÁ: