о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999Vol.36No.6P.751-757



ά㷨
塡
ժҪ80ĩоһ·.ⷽ棬LeeKedem˿ԵĹһƿ.ǣĿǰûһЧƷ.УһеƷеͨ㷨ӦͼDG·ͿԻÿе.÷ά㷨ض㷨Ƴʱŵ.Ծ˺ʹݱհΪʾ˸÷Ӧ.
ؼʣSystolicУVLSIУԴ 
ţTP302.1TP338.7
SYNTHESIZING COMPUTATION-TIME OPTIMAL 
LINEAR PROCESSOR ARRAYS FOR SOME 
THREE-DIMENSIONAL ALGORITHMS
YANG Chao-FengHU Ming-Zeng
(Department of Computer Science and Engineering, Harbin Institute of Technology, Harbin 150001)
AbstractSince the late 1980s, one trend of research on processor arrays is to design linear processor arrays. Lee and Kedem did the pioneer's work in this field as they proposed a framework for designing linear arrays. Their framework consists of three parts: the first part is a linear array model; the second part uses pairs (H, S), whereH and S are vectors, to denote designs; and the third part is a group of necessary and sufficient conditions for pairs (H, S). Thus far, there are no practical design methodologies proposed in the literature. In the paper here, a design methodology is presented for three-dimensional algorithms. This methodology is based on two observations: first, given a three-dimensional algorithm, designers can directly determine several feasible pairs (H, S) by analyzing the longest path of the dependence graph (DG) of the algorithms; second, if the longest path satisfies a certain condition, one of these pairs (H, S) is computation-time optimal. In summary, this methodology can produce computation-time optimal design for some three-dimensional algorithms. Finally, the matrix multiplication and the transitive closure problem are taken as examples to illustrate the application of the methodology. 
Key wordssystolic array, VLSI, processor array, linear processor array
1
ڴ⣬źŴͼȣǺܺõĽ1.һֱƵǶάУ80ĩһƣǾУ2ݣνУһЩԪһάṹҪI/O˿.ͻŵ㣺ٽI/O˿ڣ临Եͣͨôɣ ûʱŤб(clock skew)⣬ʱͬ.ʵϣάкֻĽзϸ˵άά㷨άеӳ䣬άά㷨һάеӳ.пǶάеļչʵϣеҪѵض࣬˹ƼܣΪ轫㷨άӳ䣬˹Ա֤ӳȷԣҪ˵Ż.
LeeKedemϵͳƷ˿ԵĹ3ݣһеƿܣһеĽṹģԼһȷӦ.ǣûһЧϵͳƷ.
һƷһضά㷨Ƴʱŵ.ںģȼҪLeeKedemƿܣȻĵķʾ.
2еƿ
רĶPѭ㷨ȡ㷨е4ݣD().Ӷ㷨õռJDÿF̻.
D=(d1 d2  dk)
V1 V2  Vk
diViǶӦdiı.ע⣺kVidiظ.Ϊһжͬͬ.
LeeKedemһģͣ3(ͼ1)ģûͨԼϵͳеľֲ洢·ȻƣԤװݡų洢Ѱַ·ĸӵĿ߼ӶVLSIʵ.ҪصǣӦDеÿdi϶һ·AiVi벢д.ͼ1ֻ·(Ӧk)֮һͬߴңߴҵ.


biӦķλĴ.bi䳤
ͼ1ģ
LeeKedemеƹΪѰHSǽ㷨ӳ䵽ϣأI(J)HIʱڴԪSI.˵ͼ2УH=(1 2 7)S=(1 1 1 )I=(1 1 1)TʱHI=10ڴԪSI=3.



N=3ΪʱH=(1 2 7),S=(1 1 1)
ͼ2ݱհʱ-ӳͼ 
һ㷨ȷHSӦоȷˣ
PEM=max{SI|IJ}-min{SI|IJ}+1.
·AiӦdiλĴ鳤bi=|Hdi/Sdi|,Sdi>0,ң򣬴ҵ.
ʱT=max(HI|IJ)-min(HI|IJ)+1(ĺԳ1).ʵϣǿˮʱ(ʱ)ΪרͨӦĳϣʱʱڿˮʱ.
LeeKedem֤HSӦ㣺(i=1,2,...,k)
Hdi>0(1)
I1,I2, 
(2)
|HdI/Sdi|Ϊ0(3)
(I2-I1mdi ,m,
H(I2-I1)SdiS(I2-I1)Hdi(4)
(1)ʽҪI2I1I2ҪI1㣬ȷ.(2)ʽҪûͬһʱӳ䵽ͬһԪΪһԪһʱܴ̽һ.Ӧһһ·ñҪͬʱУͻ(4)ʽ֤˲.
ף5GPM(general parameter method)÷ʹһ鲻ͬĲHSǵȼ۵.
еĻǣһĲöٶԪ(H,S)ÿһ(H,S)(1)(4)ʽжǷУӶŽ.ǣ̵ļ㸴ԺܸߣԭжǷ(2)(4)ʽļΪҪö.лûЧƷ.ڱģһƷά㷨ض㷨Ƴʱŵ.
3HSȷ
1. (2)ʽ(1)(4)ʽ̺.
֤.÷֤.(2)ʽ㣬ôI2,I1H(I2-I1)=0S
(I2-I1)=0.Sdi0I2-I1=mdi0=H(I2-I1)=mHdiHdi=0(1)ʽ㣻I2
-I1mdiH(I2-I1)=0S(I2-I1)=0H(I2-I1)Sdi =0S(I2-I1)Hdi=0H(I2-I1)Sdi=S(I2-I1
)Hdi(4)ʽ.˼.֤.
ݸöжHSȷԽ(1)(3)(4)ʽ.
ĵķά㷨.ʵϣά㷨ԼϸΪά㷨٣ҿԽǷָΪһϵά.ά㷨Եõһ(3Ϊd1,d2,d3)㷨ϵϣ6,7ݣӶԽ3ϲͬ㷨Ϊ3ͬ.һͼHSӦر(4)ʽʣ3ʽ(ֱӦd1,d2,d3).
ģڶ2ȷHSķȻ֤һ㷨ɸ÷ȷHSʱŵ.
㷨ͼ(DG)ȼ۱ʾ8ݣһͼڵ㼯JI2diI1I2,I1 һӦdiı.㷨ʱDG··ΪN1d1+N2d2+N3d3 ,ôʱT=max(HI|IJ)-min(HI|IJ) =N1Hd1+N2Hd2+N3Hd3.ע⣺·ӦǼȨ·Ϊͬߵʱ䲻ͬȨͬ(ӦdiıߣȨΪHdi).ȷȨ·ķΪN1=max(C1|DG·C1d1+C2d2+C3d3)ͬN2ӦC2N3ӦC3N1d1+N2d2+N3d3ǼȨ·(ĳֵN1,N2,N3ͬ).
2. N=max(N1,N2,N3),ôӳ(H,S)ȷģHD = (1,2,N),SD =(1,1,-1).
֤.(1)(3)ʽȻ.֤(4)ʽDGеI2I1(I2-I1)ԱʾΪC1d1+C2d2+C3d3,C1,C2,C3.N1,N2,N3Ķ֪|C1|,|C2|,|C3|N.
d1(УC2,C3ͬʱΪ0,ȻI2-I1 =md1 ),Ҫ:

Ϊ|C2|NȺȻ.ͬd2,C1٣N+2)C3d3,-C2(N+1)(C1+C2),ʽĲȺų.֤.
Ϊ3DDP33ѡ.i=N1,N2,N3Сֵ±,j=
N1,N2,N3ֵ±꣬k=N1,N2,N3мֵ±꣬ȡD=(dj,dk,di)ôմDͶ2
ȷHSʱT=NiHdi+NjHdj+NkHdk=NiNj+Nj+2NkNLNS+3NL,NL=max
(N1,N2,N3),NS=min(N1,N2,N3).
֤N1,N2,N3ĳǱһ󣬼Nj=Nk=NL,NS=Ni ,ôʱŵ(3).㷨оˡݱհ桢·һϵ漰㷨.
1. (H ,-S )(H ,S )ʱոԵȼ۵.
֤.ֻ·ķߵϸ֤.
1.Sd1Sd2Sd3ķֻȫһ.
Hd1/Sd1=k1,Hd2/Sd2=k2,Hd3/Sd3=k3k1,k2,k3Ľ.
2. k1 k2 k3.
֤.÷֤k1=k2Hd1/Sd1=Hd2/Sd2Hd1Sd2=Hd2Sd1 .ȡI2I1 ,(I2-I1)=md2ô(I2-I1)md1.H(I2-I1)Sd1=Hmd2 Sd1 = mHd1 Sd2 = Smd2 Hd1 = S(I2-I1)Hd1(4)ʽ㣬.֤.
3. ʱTN1,N2,N3֮ټ֮.
֤.ʱT = N1Hd1+N2Hd2+N3Hd3 = N1k1Sd1+N2k2Sd2+N3k3Sd3.
(4)ʽ,ɵ3ʽ.
d1C2,C3ͬʱΪ0

ͬd2(C1,C3ͬʱΪ0)
C1(k1 - k2)Sd1C3(k2 - k3)Sd3(6)
d3(C1,C2ͬʱΪ0)
C1(k1 - k3)Sd1C2(k3 - k2)Sd2(7)
1Sd1,Sd2,Sd3ķֻȫһ
ȫk1 = min(k1,k2,k3)2,k1<k2 ,k1<k3.(5)ʽ|(k2-k1)Sd2|>N3|(k1-k3)Sd3|>N2.򣬸N1,N2,N3Ķ壬ȡC2 =(k1-k3)Sd3,C3 =(k2-k1)Sd2,ʹ(5)ʽ.|(k2-k1)Sd2|>N3(k2-k1)Sd2>0,(k2- k1)Sd2>N3k2Sd2>N3+k1Sd2ôTN1k1Sd1+ N2(N3+k1Sd2+1)+N3k3Sd3N1+N2N3+2N2+N3.
һΪΪSd3<0,k3<0,ֲk1<k2(2֪k1k2).ʽ(5), |(k2-k1)Sd2|>N3|(k1-k3)Sd3|>N2ۣ
|(k2-k1)Sd2|>N3ʱȫʱͬ.
|(k1-k3)Sd3|>N2(k1-k3)Sd3 <0,(k1-k3)Sd3<-N2k3Sd3>N2+k1Sd3,ôTN1k1Sd1+N2k2Sd2+N3(N2+k1Sd3+1)= N1k1Sd1+N2k2Sd2+N3N2+N3k1Sd3+N3,(עN3k1Sd3<0).
N1Sd1+N2Sd2 -N3Sd3,N1k1Sd1+N2k2Sd2N1k1Sd1+N2(k1+1)Sd2k1(N1Sd1+N2Sd2)+N2Sd2-k1N3Sd3+N2,,TN3N2+N2+N3.
-N3Sd3>N1Sd1+N2Sd2,ʽ(7),|(k1-k3)Sd1|>N2|(k3-k2)Sd2|>N1,|(k1-k3)Sd1|>N2,(k1-k3)Sd1>0k1-k3)Sd1>N2k1Sd1>N2+k3Sd1,ô,TN1(N2+k3Sd1+1) +N2k2Sd2+N3k3Sd3 = N1N2+N1+N2k2Sd2+k3(N1Sd1+N3Sd3),k3(N3Sd3+N1Sd1)>k3(-N2Sd2)N2,,T > N1N2+N1+N2k2Sd2+N2N1N2+N1+3N2.
֤øö.
ɶ3N1,N2,N3ĳǱһʱTNLNS+NL+NS.2ʱTNLNS+3NL,ƫС2NL.ͨNSĴСйأԶ2.ʵϣ3һޣһȡ磬N1=N2=N3ʱ2Ǿŵ.Ϊ2ʱŵ.
HSȷΪҵǵĻd1,d2,d3DGļȨ·i=N1,N2,N3Сֵ±,j =N1,N2,N3ֵ±꣬k =N1,N2,N3мֵ±꣬ȡD =(dj ,dk ,di)ȷH =(1 2 Nj)D-1, S =(1 1 -1)D-1.
4ʾ
(1)(NN)
㷨DGһ壬3Ϊd1=(1 0 0)T,d2=(0 1 0)T,d3=(0 0 1)T.·Ϊ(N-1)d1+(N-1)d2+(N-1)d3ȡD =(d1,d2,d3)D-1 ΪλH =(1 2 N-1)D-1 =(1 2 N-1)S =(1 1 -1)D-1 =(1 1 -1),ʱT=(N-1)+2(N-1)+(N-1)(N-1)= N2+N-3.ף3û֤ŵ.
(2)NNĴݱհ
ݱհϸӣдеϵͳƷΪʾʾ䴮㷨(Warshall-Floyd㷨)£
for k,i,j = 1 to N
Ci,j = Ci,jݡ(Ci,kݡ(Ck,j)
end-for
ֱ㷨õDGܲף9ݽͼ3(a)ͼ3(b)ͼ3(a)ÿһi-jƽĽṹͼ3(b)i-jƽĽṹ.ɴ˿ɼ5d1=(1 0 0)T,d2=(0 1 0)T,d3=(-1 -1 1)T,d4=(0 -1 1)T,d5=(-1 0 1)T.



ͼ3ݱհDG
ƹ£
Ϊd4=d1+d3,d5=d2+d3,ԽһDGͼ3(c)ڳһ(k=N)i-jƽһЩ(Ӱ)ǵǽd4,d5ֱd1+d3d2+d3Ӷʣd1,d2,d3.
·Ϊ:(1,1,1)T(1,N,1)T(N,N,1)T(1,1,N)T(N,1,N)T(N,N,N)T䳤Ϊ2(N-1)d1+2(N-1)d2+(N-1)d3N1=2(N-1),N2=2(N-1),N3=N-1.ô,i=3,j=1,k=2.

H =1 2 2(N-1)D-1 =(1 2 2N+1)
S =(1 1 -1)D-1 =(1 1 1) 
ʱT = 2(N-1)(N-1) + 2(N-1)2 + 2(N-1)= 2N2+ 2N - 4.
PEṹͼ43·A1,A2,A3,ֱӦd1,d2,d3.У·A1:b1 =|Hd1/Sd1|=1ң·A2:b2 =|Hd2 /Sd2|= 2ң·A3:b3 =|Hd3 /Sd3|= 2(N-1)ҵ.⣬PEڻӦһͼ2ʱӳͼ˸PEڸʱҪɵĲǿƻ.ϸڣĲ׸.


ͼ4ݱհPEṹ
5ܡ
һά㷨еƷ.һ㷨÷Ƴʱŵ.Ծ˺ʹݱհΪʾ˱ķʹ.
Ŀõҡƻ(Ŀ863-306-03-07-2).
߼飺壬У1971ʿоҪоΪܼ㡢ϵᡡ.
У19351ڣʿʦҪоΪܼ㡢ߡϵṹ.
ߵλ壨ҵѧѧ빤ϵ150001
ҵѧѧ빤ϵ150001
οף
1Kung H T.Why systolic architecture.Computer, 1982, 15(1): 3746
2Darte A,Risset T,Robert Y.Synthesizing systolic arrays: Some recent developments. In: Int'l Conf on Application Specific Array Processors. IEEE CS Press, 1991. 372386
3Lee P, Kedem Z M. Synthesizing linear array algorithms from nested for loop algorithms. IEEE Trans on Computers, 1988, 37(12): 15781598
4Banerjee U. An introduction to a formal theory of dependence analysis. Journal of Supercomputing, 1988, (2): 133149
5Ganapathy K,Wah B W.Optimal synthesis of algorithm-specific lower-dimensional processor arrays.IEEE Trans on Parallel and Distributed Systems, 1996, 7(4): 274287
6Tzen T H,Ni M.Dependence uniformization:A loop parallelization technique.IEEE Trans on Parallel and Distributed Systems,1993, 4(5): 547558
7Shang W, Chen Z. On uniformization of affine dependence algorithms. IEEE Trans on Computers, 1996, 45(7): 827839
8Kung S Y. VLSI Array Processors. Englewood Cliffs, NJ: Prentice-Hall , 1988. 110140
9Kung S Y, Lo S C, Lewis P S. Optimal systolic design for the transitive closure and the shortest path problems. IEEE Trans on Computers, 1987, C-36(5): 603614
ոڣ1998-08-18
޸ڣ1998-11-30
