о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 9 Vol.36 No.9 1999



ع׻ϵk-ѡ
ط¹ӱ
ժҪһmn(mk)ڡع׻һk-ѡ㷨ʱ临ӶΪO(log2m+logmlog2n+log3n)һlԪͬģһʱ临ӶΪO(log2()+log()log2n+log3n+log())Ĳk-ѡ㷨.ʱlO(nlog3n/log lognʱ临ӶΪO(log()).رأl=O(n1+)(ţ0Ϊʱ临ӶΪO(logn).ʱﵽļٱΪn/logn.
ؼʡ㷨 k-ѡ񣬿ع
ͼšTP301.6; TP338.6
k-SELECTION ON RECONFIGURABLE MESH
XU Yin-long, CHEN Guo-Liang, WAN Ying-Yu,and XIONG Shan
(National High Performance Computation Center,Department of Computer Science and Technology, University of Science & Technology of China,Hefei 230027)
AbstractA parallel algorithm of  reconfigurable mesh is proposed in this paper,which selects the k-th element in an mn(mk) matrix with sorted columns.It runs in time O(log2m+logmlog2n+log3n)Also proposed is a parallel algorithm that selects the k-th element in a general set with l elements on the same model.Its time complexity is O(log2()+log()log2n+log3n+log()).When lO(nlog3n/loglogn)it becomes O(log()).Especially when l=O(n1+)(ţ0 is a constant),it is O(logn) and the acceleration ratio of the algorithm in this situation is n/logn.
Key wordsparallel algorithm,k-selection,reconfiguration
1
νk-ѡǴһȫѡkСԪأǼΪkСԪ㷺Ӧüֵרѧߵע.ڴУ16ݻڸֲл£712ݶоɹ.
ȿǴѡ뼯Աʾ6ݵk-ѡ.ͳѧ˳ѧƵȷ46ʵʵӦ.һmn(mn).FredericksonJohnsonһʱ临ӶΪO(mlog(2n/m))Ĵ㷨.㷨ŵΪֹõĴ㷨.һmnо򣩣Shenȣ13EREW PRAMһʱ临ӶΪO(logmlogm(log logm+log(n/m))),ܲΪO(mlog())Ĳ㷨.ѡеͨŸӶȣ֪ûڷֲʽ洢Ļ۹ѡ.
ع׻ (reconfigurable mesh, RMESH)14һ߶̬ӵ׻䶯̬˽ṹԼڵλʱʵһͨţʹRMESHĳЩбPRAMҪõܣϽӲķٷչʹϵṹгƣѧߵȤ.һnԪHao12ݵڡRMESHϸʱ临ӶΪO(logn)ŵĲ㷨.
һmnڱмٶmkmkÿȡǰkмɣڴСΪRMESHһʱ临ӶΪO(log2m+logmlog\+2n+log3n)Ĳk-ѡ㷨mO(n)ΪøӶΪO(log3n)mO(nlogn)ʱO(log2m).k-ѡ㷨,nnRMESHһһlԪk-ѡĲ㷨ʱ临ӶΪO(log2()+log()log2n+log3n+log()).k,㷨ʱ临ӶΪO(log2()+log()log2n+log3n++klogk).lO(nlog3n/log logn)ʱʱ临ӶȱΪO(log()).رأl=O(n1+)ţ0Ϊʱ临ӶΪO(logn)ʱHao13ݵڡRMESHO(log n)ʱnԪصk-ѡȣﵽõĲЧ.ͬʱĴk-ѡ㷨ȣﵽļٱΪn/logn.ʵӦl=O(n1+)һֺܳ㷨кܺõʵ.
2ع׻(RMESH)
һĿع׻14ǽnųɡķ.ȫnһ״Ϊ(-1)(-1)һ𣬵ÿ4˿ڣ߽紦3Ľ2пأͼ1ʾ.Щؿ㷨ִйж̬óɿأ߷ֳһЩ໥.磬ÿϿУУɵõУУߣУУ໥ͬʱвͣͼ2ͼ3ʾ.

ͼ144 RMESH

ͼ2

ͼ3
RMESHϣͬһеĴͬʱϵݣͬһʱ䵥λֻһһд.еĴͬ.Ǽٶÿڵλʱûأ߶дһλݣһ߼ȣһϵݿڵλʱ(O(1)ӳģͣڸеĴ.
RMESHֶ̬仯˽ṹһ㷨Ĳͬ׶Σ߻ֳһЩͬṹߣӶﵽ㷨ЧĳЩ⣬ع׻бPRAMҪõ.磬ڡRMESHϣ121315ݣ
(1) ԪطֲһУһлԽϵĴÿһԪأڳʱڶ.ȻҲͿԽk-ѡ(m,n)-ѡ
(2) ݷֲһУһлԽϵĴÿһأڳʱǰ׺ͣ
(3) ÿһһԪأO(log logn)ʱnԪصСֵ;
(4) ÿһһԪأO(log logn)ʱnԪصǰ׺ͣڳʱ߼.
еͨŸӶȣʹڡRMESHnԪȴҪO()ʱ临Ӷ.
3Ȩֵ
ǸȨֵĶ弰RMESHȨֵ㷨һڽüȨֵk-ѡ.
A=(a0,a1,an-1)ΪһȫȡnԪ飨nԪ֮򣩣a0,a1,an-1еĽΪai0,ai1,ain-1.W:AR\++ΪһȨm(0mn-1)㣺
(1)
(2)
ǳaimΪAWļȨֵ4.
nԪ(a0,a1,an-1)ȷֲһRMESHϣÿһԪؼԪصȨ.еĴţͼ4ʾ.PiԪaiȨW(ai),RMESHʵֵȨֵ㷨Ļ.
0123
4567
891011
12131415

ͼ4
㷨1.Weightmedia
1. ai0,ai1,ain-1ֵڸСԪai(n-1)/2
2. ai(n-1)/2͵ÿPk(0kn-1,ki(n-1)/2P\-kԪakбȽ.ai(n-1)/2.>akڴPk0,ai(n-1)/2<ak1, ֵ2.
3. б0ĴϵԪأСai(n-1)/2Ȩ֮ͣΪsumLڴP0.
4. б1ĴϵԪأai(n-1)/2Ȩ֮ͣΪsumG, ڴP0.
5. P0Ƚϣ
(1)sumL+W(ai(n-1)/2)sumG,
(2)sumL<W(ai(n-1)/2)+sumG
 (I),(II)ai(n-1)/2ǼȨֵ.ͣ.
  (I)Сڵai(n-1)/2ԪصȨ̫Сڴai(n-1)/2б1ĴԪأҵֵת2.
 (II)ڵai(n-1)/2ԪصȨ̫ССai(n-1)/2б0ĴԪأҵֵת2.
㷨ȷԼ.Ϊʵ㷨WeightmediaǲHao12ݵڡRMESHʵֵʱ临ӶΪO(logn)ѡ㷨ѡȡֵ.㷨ĵ2RMESHϽO(1)ʱ.
ҪRMESHб0(1)ĴԪصȨͣȼٶ10ĴԪصȨΪ0ȻlogѭÿеȨ֮.һѭÿ߷ֳ/2ߣÿеĵ1ʼÿΪһߣÿϵĵ21͸ôԪصȨڵ1ԪصȨͲΪӦߵȨ.ڵiѭi-1ѭеÿһµߣڵ1ѭµߵȨ.log֮ÿеĵ1ϺиеȨ.RMESHϵĵ1logѭRMESHϵȨͣڴP0.
㷨Уÿִһε25һѭǽ迼ǰһѭеһԪأԵ25ѭlog.ÿε25ѭʱO(log).
ǵõµĶ.
1. nԪA=(a0,a1,,an-1)ȨW:AR+AȷֲڡRMESHϣPiԪaiȨW(ai)O(log2n)ʱAWļȨֵ.
4RMESHϵѡ㷨
4.1k-ѡ
Johnson  Mizoguchiף4üȨֵ󼯺X+Yϵk-ѡ.XYϣX+Y={x+y|xX,yY}.ͬ˼RMESHʵk-ѡĲ㷨.ڱǲÿеԪذ.
㷨Ļ˼ǣҵiеֵaiaiȨWaiΪiеԪظȻҵ(a0,a1,,an-1)ļȨֵaitдaitСڵaitԪظȫԪظ1/4kСڵaitԪ򶪵СڵaitԪأk<СڵaitԪ򶪵ڵaitԪأÿٶǰԪ1/4.ѭO(log(mn))֮һҵmnеĵkԪ.
һmnM=(mij)mniԪش洢ڡRMESHĵi.RMESHMk-ѡ㷨.
㷨2. 㷨 SelectMatrix
1. i=0,1,,n-1,ڵiLb(i)=0,Rb(i)=n-1;
2. i=0,1,,n-1,ڵiiеǰʣԪصֵmijiӶnԪA=(m1j1,m2j2,,mnjn,ji=(Lb(i)+Rb(i)),ȨW(miji)=Rb(i)-Lb(i)+1iеǰԪ.
3. AļȨֵmtjt(0tn-1),͵еĴ.
4. ÿ򣬿ڵiöַҵmtjtڵiеλ.ҵ±SiʹmtSimtjtmtSt+1.P(i)=Si+1, Q(i)=Si(i=0,1,,n-1).˵ mtjtСڵiеԪأSi+1=0miji;mtjtڵڵiԪأSi=n-1mi(s\-i+1).
5.  kP(i),Rb(i)=Q(i),i=0,1,2,,n-1,ת2
 kP(i),Lb(i)=P(i),i=0,1,2,,n-1),ת2
 ٣ڲmtjtǵkԪأ㷨ֹ.
2. һmnMiԪȫnnRMESHĵiУ㷨Select_MatrixO(log2m+logmlog2n+log3n)ʱMĵkСԪ.
֤.㷨ȷԼף4.ʱ临Ӷ.
1Ͳ2O(1)ʱ䣬3㷨1O(log2n)ʱ.4ÿ̨ϲеöַңmԪصĶֲO(logm)ʱ.5P(i)(Q(i)-1)õ4Ȩ͵㷨O(logn)ʱ䣬ˣÿִһβ25ѭO(logm+log2n)ʱ䣬25ִO(log(mn))=O(logm+logn).㷨ʱ临ӶΪ
O((logm+logn)(logm+log2n))=O(log2m+logmlog2n+log3n)
mO(nk)ʱkΪʽO(log3n).
mO(nlognʱlogmO(log2n)ʽO(log2m).
֤.
4.2һ㼯ϵk-ѡ
lԪؾȷֲRMESHϣÿкl/nԪ.ҪlԪеĵkСԪ.ΪÿϽl/nԪؽʱO(log()).
ȻеlԪؿһn㷨2kСԪʱO(log2()+log()log2n+log3n)õĶ3. 
3.lԪؾȷֲڡRMESHϣO(log2()+log()log2n+log3n+log())ʱkСԪ.
kl/nÿ̨ѡ㷨ѡǰkСԪȻǰkСԪ㷨ʱ临ӶȱΪO(log2()+log()log2n+log3n++klogk).lO(nlog3n/log logn)ʱ3еʱ临ӶΪO(log()).൱ÿľֲʱ.رأl=O(n1+)(ţ0Ϊʱ临ӶΪO(logn).ʱͬף13ݵڡRMESHO(logn)ʱnԪصk-ѡȣﵽõĲЧ.ͬʱĴ k-ѡ㷨ȣﵽļٱΪn/logn.ʵӦl=O(n1+)һֺܳǵ㷨кܺõӦüֵ.
5ʵ
ǲõ㷨ģ.Ծֲ㣨ȽϼӡˡȣͨŴм.ͼ5ÿԪظֱ61224£òͬСRMESHдﵽļٱ.ע⵽㷨ļٱȻn/logn(ΪRMESHĹģ).ͼ61212RMESH϶ԲͬԪõļٱ.ÿڲԪmı仯ԼٱӰ첻.ÿִ100ȡƽֵ.

ͼ5

ͼ6
6 ܽ
ڡĿع׻üȨֵ˼ʵmnk-ѡʱ临ӶΪO(log2m+logm log2n+log3n).ϵk-ѡ㷨һlԪk-ѡ㷨㷨ڡRMESHϵִʱΪO(log2()+log()log2n+log3n+log()).lO(nlog3n/log logn)ʱʱ临ӶΪO(log()).رأl=O(n1+)ţ0Ϊʱ临ӶΪO(logn).ʱﵽļٱΪn/logn.ͬף12ݵO(logn)ʱڡRMESHnԪصkѡ㷨ȣﵽõĲЧ.
עõҽίʿĿ9703825.
߼飺طУ19636ʦоΪۡ㷨.
¹У19386ڣʿʦоΪֲʽ㷨Ŵ㷨.
ӱ褣У19761ʿоҪоΪ㷨NPCʵ㷨.
ߵλйѧѧѧϵҸܼġϷʡ230027
ο
1Fussenegger F.Johnson D B.A Counting Approach to Lower Bounds for Selection Problems, J of ACM, 1979, 26(2): 540543
2Hyafil L. Bounds for selection, SIAM J Comput, 1976, 5(1): 104109
3Krkpartrick D G. A unified lower bound for selection and set partitioning problems. J of ACM, 1981, 28(1): 150165
4Johnson D B, Mizoguchi T. Selecting the k-th element in XY and X1+X2+Xn. SIAM J Comput, 1979, 7(2): 147153
5Frederickson G N, Johnson D B. Generalized selection and ranking: Sorted matrices.SIAM J Comput, 1984, 13(1): 1429
6Frederickson G N, Johnson D B. The complexity of selection and ranking in X+Y and matrices with sorted columns. J Comput & Sys Sci, 1982, 24(2): 197208
7¹. 㷨ѡ. Ϸ: йѧѧ磬 1990
(Chen Guoliang. Parallel Algorithms-Sorting and Selection(in Chinese). Hefei: The Press of Chinese University of Sciences & Technology Press,1990)
8¹.ƽѡ. оͷչ,198421(11):921
(Chen Guoliang. Balanced grouping selection network, Journal of Computer Research & Development(in Chinese), 198421(11): 921)
9¹. SIMDʵֵ˫ѡ㷨оͷչ1988,251:19
(Chen Guoliang, Shen Hong. Bitonic selection algorithms on SIMD machine. Computer Research & Development(in Chinese), 1988, 25(1): 19)
10 ¹ . й鲢ѡ㷨. ѧ,1988,11(1):1421
(Chen Guoliang, Wang Zhongliang. Parallel merging selection algorithm. Chinese Journal of Computers(in Chinese), 1988, 11(1): 1421)
11 ¹. ദϵķѡ㷨. оͷչ, 198825(8): 19
(Chen Guoliang, Liu Jun. Grouping selection algorithms on multiprocessor machine. Journal of Computer Research & Development(in Chinese), 198825(8): 19)
12 Hao E, Mackenzie P D, Stout Q F. Selection on the reconfigurable mesh. In: Proc Int'l Parallel Processing Symp, 1992, 3845
13 Shen H, Ramnath S. Optimal parallel selection in sorted matrices. Inform Process Lett 1996, 59(3): 117122
14 Miller R, Prasanna-Kumer V K, Reisis D I, Stout Q F. Parallel computations on reconfigurable meshes. IEEE Trans on Comput, 1993, 42(6): 678692
15 Nigam M, Sahni S. Sorting n numbers on nn reconfigurable meshes with buses.In: Proc Int'l Parallel Processing Symp, 1993, 174181
16 Ullman J D. Computational Aspects of VLSI. New York : Computer Science Press, 1984
ԭյڣ1998-11-30޸ĸյڣ1999-05-17.
