Документ взят из кэша поисковой машины. Адрес оригинального документа : http://fpga.parallel.ru/papers/levin.pdf Дата изменения: Thu Jun 19 11:10:00 2008 Дата индексирования: Mon Oct 1 19:57:23 2012 Кодировка:

.. - .. , . E-mail:levin@mvs.tsure.ru - . - . , . , . . , 60- , . , [1]. . , . , , . , ( ) [2]. , .


10 . , , . . . , . [3, 4, 2]. . [5, 6]. , , . . () , . (, ..) . , , , . , ( , ), . , . , , (, ).


, , [4]. ­ . , . . , , . , , [7]. , . , [7]. , , , , , [10, 11]. , , . : G=(X, AX),(Q, AQ),(Y, AY), (1)

X - , Y - , Q - . AX, AQ AY . u,v, AX, uX, vQ. u,v, Q, uQ vQ. u,v, Y, uQ, vY. , ( , )


, . . , - . , . , . . , . . , G, Pj, , a Pi b Pj, a, b, i j. , , , , Pi, . , . , , ( ) ( ). , , , . , - , . , , . .


- . - , - () , . , - - . , , , , , , . , - , . [16], Q, I , O , Q - , , , ( , ), , . I = I , I 2 ,...I n , I j 1 Q Aj . , O = O1 , O2 ,...On , i Q j . Ij , Aj . j , j . .1 .


1 x1 ... x1 x1 2 l

I1(t) I2(t) I3(t)

A A A

1

Q
+ +

B1

xl2

...

2 x2

2 x1

2

O1( t)

1 y1 y1 ... y1 l 2

3 3 xl3 ... x2 x1

3

*
. . .

. . .

*
+

+

B

2

nn xln ... x2 x1

In(t)

A

n

...

+

B

m

. . .

2 O2( t) y1 y

2 2

... yl2 ... yln

n Om(t) y1 y

n 2

.1. . , , , , . . , . Q, , , - . , 1 , 2 ,..., l , () . i = Q, X i , Yi X i = I (ti ), Yi = O(t i ). , , , . , 1 , 2 ,..., l , j = Q j , X j , Y Y = Y1 , Y2 ,...Yl ,
j

l

Q1 Q2 ... Qn ,

X = X 1 , X 2 ,... X l , j- j- , j- j- .


. X Y , , , . - , , , . , , , , , . G1 G2 G , a G1 b G2 . , G1, G2 , , , G1 G2 . G1 G2, , . , .. . K (G1 , G2 ) K (G2 , G1 ) . . . - . . , , gi: FR: (x,aX)i (x,aX)i+1, i=1, 2,..., N-1, (2) FW : (y,aY)i (y,aY)i+1, i=1, 2,..., N-1, (3)


i - i- ; aXi - i- ; yi - i- ; aYi - i- . , , , , .. , , . , , . G1 G2, , , a1 G1 , b2 G2 G1 G2, G1 G2 , < G1 , G2 > , < a1 , b2 > . . , b. , . , G1. b1 b2 ( G1 G2 ). < xb , b1 > < 1 , b2 > . .2.
1

xb b1
. . . . a1 . .

y

1,1

x1, x1,

xa
1 n

y1,

m

b x2,1 . . x2,n .

2

. a2 .

.

y2,

1 m

y2, ya

b x1 R xn . .
.

1

a1 G
1

G1

G2

. . ym

y1
.

ya N

a)

)

) ; ) .2. .


G1,G2,...Gn, i , Gi Gi +1 ( i Gi , - bi Gi +1 ), G1,G2,...Gn . 1 , , , , . .3.
x b1
a ,1

a1 G1 y1
,1 ,m

b2 x x
2 ,1 2 ,k

a2 G y2
,1 ,m

b3 .y .2 . x3
,1

a3 G y
3 3 ,1 3 ,m

x .y . .

n -1 n ,1 n ,k

bn G

an

y

a ,1 ,m

. x1 ,k . .

x1

x ... x

.y .1 .

. . .

2

x3 ,k . . .

. . .

n

.y .n .

yn

.3. , . i < a, b > , , 1 b1 , .. . , 2). , , , ( ), , (2) (3). ( ) i Gi bi + i Gi + i . i Gi b f ( i ) G f ( i ) . , , () . , . a j rj ,


( ) , .. . , b j w j , ( ) , .. . :
K = < R, Q,W > , R - ; Q - - ; W ­ .
R=
N ( A)

(4)



< a j , rj > ,

j =1

N(A) - A. :

W=


N ( B)

< bj , wj > ,

(5)

j =1

N(j) - . , , , . - () ,

Pi =

N

S
j =1

i, j

(6)

, a,b a Ski, b Skj, i j.


Sij . , , , , , . , Si,j Si, j =
K

g
k =1

i , j ,k

,

(7)

gi,j,k . gi,j,k . , . - . a,b Si,j, a gi,j,k b gi,j,k. , , , . gi,j,k Si,j , , , a,b , a qij-1p , b qijk. . Pi=i,j(Fi,j,k(gi,j,k)), (8)

Fi,j,k ­ , gi,j,k gi,j,k+1, i,j ­ , Si,j Si,j+1. F () . . Pm gi,n,k Si,n gi,m,k Si,m, k=1, 2,..., K n m, n=1, 2,..., N, m=1, 2,..., N , G Pi . Pi Pi=i(Fi(gi)). (9)


Pi -, , , - . - . , , - , , . . , , , . - , . , G G=(F(g)). . . 1)°
X=
N

xi
i =1

R = ,

- , ­ FR T X, (10) T - ti, i=1, 2,..., N, ti < ti+1. FR - rj t () x. , :


rj =

x1,1 x1, 2 x2,1 x2 , 2 & P (t = t1 ) & P(t = t2 ) ... . . x xm,1 m,2



x1, M x2 , M & P(t = t M ) = . xm , M



M

i =1



x1,i x2 ,i & P(t = ti ) .(11) . xm , i

P(t=ti) ­ , , t=ti . :

rj =


j =1

K



x1, j x2, j t j , . xm , j

(12)

"·" - , , t=tj xj. , . . 2)
Y=
k

yi
i =1

W=(NW, FW),

- , ­ FW TK Y. (13) y1, j K y 2, j wj = (14) t j . j =1 ... y m, j



3) , Q=(VQ, A). VQ - , NR, NW VOPQ


VQ = NR UVOPQ UNW, A :


(15) (16)





AK = AR UAQ UAW.

AR - , NR, - v VOPQ; AQ - , - p VOPQ, - q VOPQ; AW NW v VOPQ. RA RK, WA WK. , . , (, , ). , () NK, ­ AC. , , W={ NK1,AC1, NK2,AC2, ..., NKL,ACL}. . , , ( , ), , . , , . (


) , , . . ( ). , . , , ("") , . . t d1 d2, ( d1 FS b1= NK1, A1, d2 FS b2= NK2, A2, NK1 NK2). . wi Ki t1 d1, rj Kj t2 d2, d1 d2 , . FS d1 d2 b1= NK1, A1. , , , , .


, . . , ( ) ( ) . , , . , . , (). - . . , , . , , . , , , . FER FEW . - erC FER :

erc =

(
k =0

R

Drk

,c

)

tk =

A (
k =0 c

R

x

J k , ( k ,c )

)

t k = ar

( k ,c )

,

(17)


Drk,c ­ , ( =0,1,...,M-1) tk; k,) ­ , ( tk . , - ewC FEW :
ewc =

(
k =0

R

Dwk

,c

)

t k = aw

( k ,c )



tk ,

(18)

Dwk,c ­ , , tk; (k,) ­ , tk . GK. Kk= Rk,Qk,Wk,. Pk Pm , Dk,m, Dk,m Kk, Km. , , . Kk Tk ­ ti,k. - : , - . - . , . () . .. - , . : , ,


- [17], , . , . a b , . -, b , .. , a b. , , a b, -. , , . . .4 - . , () , , ­ (). K1 K2. . (). , , , , . () , () . ( ) , . , .


, .

R1 R2
1 3

R3
2

4 5

R
3

4

R5
4 5

W

5

Q5





K1




. . .

K2
K







. . .






1 2









3







4







5







.4 . . 1. .. . - .: , 1980. - 519 . 2. .., .. . // II-


« », , 1995. 3. . . // : , , , 2000. -2. - .18-21. 4. .., .., .., .., .. : . // . , 2004. - 1. - . 13-17. 5. .., .., .. . . / . .. - .: , 1990. 6. .. . - .: , 1999. 7. .. . - .: , 1986. - 286 c. 8. .. . - .: - , 1997. 9. .. . // . . . - .: - . , 2000. - .1. - . 242-255. 10. .. . - .: , 1987. 11. .. . - .: , 1991. - 345 . 12. Siegel L.J., Siegel H.J., Swain P.H. Performance Measures for Evaluation Algorithms for SIMD-Machines. // IEEE Trans. Software Eng. V. 8. - 4. - Pp. 319-331. 13. .., .., .. . // , 1989. 6. - C. 11-15. 14. .., .. : . // ­ , 1999. - 11. - .11-19. 15. . / . . II. - .: , 1991. - 376 c. 16. .., .., .. . // . 1991. - 2. - . 80-94. 17. .. . .: . , 1972. ­ 280 .