ѧ
JOURNAL OF SOFTWARE
1999ꡡ1011ڡVol.10No.111999



ڹϻֵĲв㷨
Ƶ¡׾
ժҪ´Ϸ߻ڹϻֵĲв㷨ļٱȵ;.ڴ˻ϣ˰عʶ·ϵĻ׶ϻַBFPOCbackword fault partitioning of output fan-in conesѸ÷BanejeeƼĻȳ׶ϻַTFPICtoword fault partitioning of input fan-out conesͳõĻڹ˳ĵȲַEDPFSequal distance partitioning of fault sequencesʵȽ.ڴģд£BFPOCȺַԵƣܻøߵļٱ.
ؼʡвɣϲУϻ֣׶ȳ׶ٱ.
ͼšTP338
A Parallel Test Generation Algorithm Based on Fault Partitioning
ZENG Zhi-deZENG Xian-jun
(Department of Computer ScienceNational University of Defense TechnologyChangsha410073)
Abstract In this paper, the authors analyze in theory how to increase the speed-up ratio of parallel test generation algorithm based on fault partitioning. The approach of backward fault partitioning of output fan-in cones (BFPOC) which combines the relevant fault recognition and shortest path sensitization, is presented. And BFPOC is compared via experiment with the approach of toward fault partitioning of input fan-out cones (TFPIC) proposed by Banejee and the general one, equal distance partitioning of fault sequence (EDPFS). The experimental results show that in large-scale parallel processing environment, BFPOC can reach higher speed-up ratio, obvious super to the other two approaches.
Key wordsParallel test generation, fault parallelism, fault partitioning, output fan-in cones, input fan-out cones, speed-up ratio.
дԸVLSIʱָһֿɹѡķ1.ģдMPP͹վȺWSGĹ㷺ãΪвɵʵṩõӲ.ǣҪѲԭڴд㷨ɿɲе㷨.
10ѧ߳˼ߵϵͳЧʵо2,3,˶в㷨оȺ˻ڹϲСʽСռ䲢Сܲк͵·еȶֲвɷҲһЩڲвɵԭϵͳ.磬ȳ׶Ե·ϽмĲϵͳ4ݡʽеϵͳ5ݡѲϰռ䲢еϵͳ6Լʱ·ֱ𰴹ϲУ7ݡռ䲢У8ݺͰ·У9ݵϵͳȵ.Щϵͳ벢дĴĿΪ516Сģ.ǵĹͬصǱȽӴ֮Ķ̬ƽ.֪ʵֶ̬ƽӴ֮ͨſΪ۵.ϲ֤ʵNĶ̬ƽͨſʱ临ΪON2.MPPϵͳN128ʵֶ̬ƽ߼ٱȿܻ.Ϊˣǽоص߾̬ƽϣԼMPPĲвϵͳͨſ߼ٱ.߼ԵĴСѱ·CUTԭеԳPOΪ׶P׶NвдŻ㷨Сݹַ10ݣյ˽ϺõЧ.ǣЩߺܶࡢȺıջ·ÿ׶·.ʱͼ·׶ֿ齫ͽ͵.ˣоMPPĻڹϾֵ̬Ĳв㷨.
1ڹϲеļٱ
mn׾aijΪCUTĹϼj=1,2,...,nCUTĿϼSFеn϶Ӧi=1,2,...,mSFȫԼSTеÿӦ.

ǵǰSFеnƽָNввɣϣȡߵļٱ.ʽ£
ѾaijоֳNmn/N׵bKili=1,2,...,ml=1,2,...,n/N(n/N+1K=1,2,...,N.ڴʱbKilаһЩȫУѹЩȫ֮i=1,2,...,mKmax{mK }=Mٱ
SPmtg+tf.mfs)/(M(tg+tf.mfp)).
(1)
ʽ(1)УMmtgΪһƽʱ䣬tfΪһģһƽʱ.CUTĸԼõĲɣTG͹ģ⣨FS㷨ϻ޹.mfsmfpֱΪڴкͲɻ£һƽҪģĹ.Ϊ˱ڷǼSTеmȫSFеnϣÿ붼n/mϣǿԵ
mfsnm+1/2m,
mfpnM+1/(2N.M),
SPNm2tg+tf.n+tf.n /M2tg.N+tf.n+tf.n.
(2)
ʽ(2)УֻMϻַй.ȻڶԣaijлʱʹMȡСֵSPΪֵɻߵļٱ.
 ڶSFʱaij֪ģȡ߼ٱȵĹϻֿɳΪѧ⣺ӾaijCNnѡȡʹMС.ģ˻𷨻Сݹַѽ.ǣڽйϻʱδSTaijδ֪ģʱò.ѸһҪʾ߼ٱȵĻ֣ʹÿֵõĹϼȫԼСMСĻ.ΪˣڽйϻʱֿǹϵĵȼԡԺͶ.
VLSIеĹϣÿϵȫԼԣԷΪȼ۹ϡعϺͶ.TT·ֱΪ̶ϦµȫԼ
TT£Ʀ,Ϊȼ۹ϣ
TT£TT¡١ӣƦ,Ϊعϣ
TT=ӣƦ,Ϊ.
Ȼ壬ɲڶ.ǵϵͳtest generation system,TGSCUTĿϱʱԵȼ۹ѽʶ͹鲢,ڻֹʱٿǵȼ۹.
Ϊʹв㷨ýϸߵļٱȣֹʱӦѭ3ԭ
(1) عȷͬһ
(2) ȷͬĴ
(3) عϼĸͬ.
23ֹϻַ
ԶعϺͶϵʶǹϻֵĹؼ.BFPOC(backword fault partitioning of output fan-in cones)ף1ƼTFPIC(toword fault partitioning of input fan-out cones)ͽϳõEDPFS(equal distance partitioning of fault sequences)бȽϣǵ,ַ.
2.1 ׶򻮷ַBFPOC
÷Ļ˼ǰعϵʶ·11ݵ˼..
(1) ܿϷ
蹦ܿs-a-0ϵΪks-a-1ϵΪk+1ݹܿĹܡԺ·˼룬ԼȳԴϴǣ
1 򣨻ǣ
 ͵ǵȳԴs-a-0϶kk+1s-a-1k+1k
 빲ii=12...Щs-a-0ǸԵȳԴs-a-0ֱk+2k+3k+4k+5...s-a-1k+1k.
2 루ǣ
 ͵뼰ȳԴs-a-1k+1ks-a-0kk+1
 빲ii=12...Щs-a-1ǸԵȳԴs-a-1ֱk+3k+2k+5k+4...s-a-0kk+1.
3 ǣ
ȳԴs-a-0kk+1s-a-1k+1k.
4 Գĸ
 ǣţͬһϷͬ루ǣţͬŵĶԳs-a-1ͬһ.
 Ի루ǣţͬһϷͬ򣨻ǣţͬŵĶԳs-a-0ͬһ.
5 ܿ
 Լ͵a/ͨ.ͬͨaȳԴs-a-0ks-a-1k+1ͨaȳԴs-a-0k+1s-a-1k˫ͨذͬԴ
 bi(i=1,2,...)ͬͨbiȳԴĹs-a-01Ϊk+i+1k+i+2ͨΪk+i+2k+i+1˫ͨذͬԴ.
(2) ·Ϸ
ӵĳPO1ʼ루PI׶ÿһܿ.ÿܿŵĻϣǵ뼰ȳԴĹϷ.·˼.
(3) ŷ㷨
1 ͬһֻһţͬϵŲص.ԭ򣬸׶֮乫Ĺֻһ.
2 Ϊⲻͬϵصŷ㷨£
 һ߷ڽΪϵţʹĳߵһѱȼ۹鲢.ġߡPIڲܿߺȳ1ȳԴȳ.
 ܿϷԭͬһĹϣСȡ룻ͬһĹϣԭŲ.
(4) 򣬱ͬһĹϹһعϼͬĹϵԺͶԣҪ뾫ȷȽϸӣܵǶԴ.
(5) ԭͬӦͬһͬӦͬĴǿǴƽеʱ.ʱӦʹͬĹͬ.
(6) ϻ־
1:ͼ1ĵ·ȼ۹鲢󣬹30ϣֹ򽫱Ϊ15飬.

ͼ1
0a01b02f0 34j0
5 6 c07 g08 d0 9 e0
10 h011 i012 k013 14 l0

30ϣATGTAϵͳ8.4ϱڲͬ.
2.2׶򻮷ַTFPIC
Ļ˼ǣһPIȳߣйصPO;߹ɵPIΪ׶Ĺϣշֳ飬ÿһҲһعϼ.׶֮ĹҲֻһ.Ȼ
CUT=2*PI.
ѹʱȻѭ1ԭ.
2.3CUTϱй˳ĵȲַEDPFS
CUTϱй˳򰴹ܿ鼶ӵ͵УÿܿĹϰ01Ϻ01Уϸ񰴶˺˳.νȲָԴĿNΪCUTnϷֳNݣÿݺn/N(n/N)+1еii=1,2,...,NֵõĹΪ
j*N+i, j=0,1,2,...,j*N+in.
Ŀﵽ16ʱ˳Ȳ֣԰Ѿܿ롢ϷָͬĴ뾭ȼ۹鲢֮ͬһܿУţµĹϴ󲿷ǶϵĹ.Ǹ÷ҲȽЧҪԭ.
3ʵ
3.1 ʵ1
ڵ̨SUN ULTRA2Ͻһйģϵͳһģ256Ĳв.ϵͳ޻ݲģʽɲ룬ͬʱģйϸ.ôϵͳISCAS-85ֵ·ģ3ַֻЧ.ֱΪ41664256ʱ,ɵļٱȺ͹ϸʽڱ1.ΪʹٱȵıȽԺҪ󵥻СõĹϸӦͬ.1ͷ2õԤʱ٣ɲ迼.ɵĹϸǰѸɵĲ뼯йģõģõǲ벢СϴĿٹģⷽ12.
1

·
ƻ
41664256
ٱȹϸ(%)ٱȹϸ(%)ٱȹϸ(%)ٱȹϸ(%)
C135512.8398.837.3699.3218.6799.3253.6299.51
22.5098.086.9599.1414.1399.2647.5299.26
32.6198.276.0698.8316.3499.4446.4799.26
C190812.9799.297.1299.2917.3299.1536.9599.34
22.4999.154.6999.2412.6899.0630.5499.15
32.5199.016.2699.0113.6599.0634.2299.06
C267013.0295.6510.2795.6527.5495.6549.5295.72
22.0095.475.6595.5112.4395.5833.0595.58
32.7595.518.7395.5124.9195.5140.6295.65
C354012.8696.149.8596.1920.0296.1937.8996.25
22.7296.147.5896.169.0496.2215.6896.22
33.0696.037.7196.1616.8496.1929.9696.16
C531512.9098.9110.7998.9420.0898.9637.7298.96
23.0898.809.1798.7812.0198.9423.5798.94
32.8298.758.3298.9414.6098.9632.7098.96
C755213.2598.357.5198.3616.9298.3640.6398.36
23.2998.285.4998.349.7698.3624.5798.36
32.9598.336.8798.3616.4998.3332.6098.36

3.2 ʵ2
ATGTAϵͳһ25000šǧߵASIC·÷1йϻ֣ģ4вɺ͹ģЧ.ڱ2УTGʱΪSUN20CPU룬FSʱΪSUN4CPU. 
2

TG/FSʽ볤ʱ(s)ٱȣϸ %
TGFS
4 00018 53217 3131.064 1021.096.65
44*1 00019 4094 4623.8815 8324.0596.75

3.3  
1ͱ2ݣԵóн.
(1) ƽ4£3ַЧ̫.
(2) ﵽ16ʱ1ļٱڷ2ͷ3ﵽĹϸ뵥ʱͬף3ݣȷ2ͷ3ԺһЩ.2ף1Ƽķ.ǵʵǣϴʱ籾ķ1ȷ3Ч.
(3) 16ISCAS-85·ȡԼٱȣֱб0.20.7֮䣩Ч.رǴΪ256ʱƽٱȴﵽ42÷Դģвɽ.
(4) 2˵1ʱ·ͬЧ.TGFSΪɢϵϵͳ4õļٱֱбʵ1. 
ĿоõȻѧ.
߼飺Ƶ,1941,,ҪоΪϵͳݴ.
׾,1966,ʿ,ڣҪоΪϵͳCAD.
ߵλѧѧϵɳ410073
ͨѶϵ:Ƶ£ɳ410073ѧѧϵ
ο
1Banerjee P. Parallel algorithm for VLSI. Computer-Aided Design. Englewood Cliffs, NJ: Prentice-Hall,Inc., 1994
2ҳϣ棬Ӧ.һڵ·ṹĲԲϵͳSABATPG.йѧ(A),1993,23(2):189196
(Li Zhong-cheng, Pan Yu-qi, Min Ying-hua. A structure analysis based test generation systemSABATPG. Science in China (series A), 1993,23(2):189196)
3Ƶ.ASICɺͿɲԷϵͳATGTA.ѧ1998215448455
(Zeng Zhi-de. ASIC test generation and testability analysis systemATGTA. Chinese Journal of Computers, 1998215448455)
4Patil S, Banerjee P. Performance trade-offs in a parallel test generation fault simulation environment. IEEE Transactions on Computer-aided Design Integrated Circuits Systems, 1991,10(12):15421558
5Chandra S J, Patel J H. Test generation in a parallel processing environment. In: Lopresti P V ed. Proceedings of the International Conference on Computer Design (ICCD'88). Rye Brook, NY: IEEE C, IEEE CAS and IEEE ED, 1988. 1114
6Patil S, Banerjee P. A parallel branch and bound approach to test generation. IEEE Transactions on Computer-aided Design Integrated Circuits Systems, 1990,9(3):313322
7Agrawal P, Agrawal V D, Villodo J. Sequential Circuit Test Gineration on a Distributed System. In: Newton A R ed. Proceedings of the 30th Design Automation Conference (DAC'93). Anaheim: ACM/IEEE, 1993. 337341
8Ramkumar B, Banerjee P. ProperTest: portable parallel test generation for sequential circuits. In: Jones I K ed. Proceedings of the International Conference Computer-aided Design (ICCAD'92). Washington D.C: Computer Society Press, 1992. 220223
9Chan T. Distributed automatic test pattern generation. In: Tsai Y T ed. Proceedings of the Application Specific Integrated Circuits Conference (ASIC'92). Rochester, NY: IEEE Rochester Section, 1992. 385388
10Tao Jing, Zeng Zhi-de. A network partitioning algorithm for parallel test generation in VLSI circuit. In: Yang Shu-zi ed. Proceedings of the 4th International Conference on CAD/CG. Wuhan: SPIE(USA), 1995. 645650
11Ƶ.ϵͳɲ.ɳѧѧ磬1992
(Zeng Zhi-de. Testing and Testability for Digital Systems. Changsha: National University of Defense Technology Press, 1992)
12ʤƵ.ϵ·ģٷоʵ.ȫ10CAD & CGļ.ܹ˾231998. A-1A-5
(Liu Sheng-li, Zeng Zhi-de. The research and realization of accelerating fault simulation for combinational circuits. In: Proceedings of the 10th Chinese CAD/CG Conference. Beijing: Institute No.23 of China Aerospace Corporation, 1998. A-1A-5)
1998-08-24յԭ,1998-12-01յ޸ĸ
