臺灣博碩士論文加值系統

今日，掃描式(SCAN-BASED)架構的使用已被廣泛的使用於積體電路測試環境中。但是，在正反器(FLIP-FLOP)間大量的位元搬移與其內含值之轉換卻造成嚴重的功率消耗。掃描次序的排列(SCAN-BASED REORDERING)技術已被證實可有效的降低功率的耗損；然而此一技術卻會造成大量的接線，增加設計與生產成本。因此，在減低功\\\率耗損與減少接線長度之間的權衡問題，在近年電子電路測試的研究上十分受到重視；例如，應用分群技術(CLUSTERING TECHNIQUES)，於二維空間上，將正反器一一加以分群後，再做掃描次序的重排，可同時減少功率的消耗與接線的長度。在本論文中，我們提出了一個稱為ISAC(INTRINSIC STRUCTURE APPROXIMATION-BASED CLUSTERING)的混合式演算法。ISAC內含了OPTICS以及K-MEANS兩種演算法。一個幾何的証明已證實：近似圓形的群可涵蓋最多的點。因此，我們首先利用OPTICS取得正反器於電路上的內在分布結構，用以判別群數值K；再利用K-MEANS可形成密集的、圓形的群聚之特性，對正反器之幾何位置加以分群。以標準測試電路S9234為例，模擬結果證實，ISAC可有效降低功率及減少接線長度，最高可分別達到16.563%以及65.989%。

The use of scan-based architectures is wide-spreading in circuit testing processes nowadays, yet expensive in power consumption. Scan chain reordering techniques have been utilized for years to reduce power dissipation in traditional DfT (Design for Test); nevertheless, one of the main concerns, namely the length of scan routing, has received a plenty of attention for the reason of a tradeoff existing between power reduction and length reduction of wire connections. Hence, in this thesis, a hybrid clustering algorithm named ISAC (Intrinsic Structure Approximation-based Clustering) consisting of OPTICS and k-means is proposed. ISAC adopts information, obtained by OPTICS, from the intrinsic structure of the distribution associated with scan cells to determine the number of clusters generated by k-means in which k compact circle-like clusters are formed. A property of geometry has been proved that given a diameter, a circle-like cluster can cover the maximum area; thereby it might be able to contain as many cells as possible. Results from our quantitative simulations in the benchmark circuit s9234 have demonstrated the efficiency of ISAC in both power reduction and length saving; both reduced up to 16.563% and 65.989%, respectively.

CONTENTS

CHAPTER 1 INTRODUCTION 1
1.1 POWER CONSUMPTION DURING TESTING 1
1.2 MOTIVATION AND GOALS 3
1.3 THESIS ORGANIZATION 4

CHAPTER 2 RELATED WORKS 5
2.1 BACKGROUND 5
2.1.1 TERMINOLOGY 6
2.2 POWER DRIVEN CHAINING OF FLIP-FLOPS IN SCAN
ARCHITECTURES 7
2.2.1 POWER ESTIMATION FOR SCAN VECTORS 8
2.2.2 SCAN CELL ORDERING PROCEDURE 11
2.3 DESIGN OF ROUTING-CONSTRAINED LOW POWER SCAN CHAINS 15
2.3.1 CLUSTERING CELLS 16
2.3.2 SCAN CELL REORDERING WITHIN A CLUSTER 17
2.3.3 CLUSTER ORDERING 19
2.4 IMPROVED NEW CLUSTERING OPERATION 21
2.5 SUMMARY 23

CHAPTER 3 ISAC: INTRINSIC STRUCTURE APPROXIMATION-BASED
CLUSTERING 24
3.1 PROPERTY OF CLUSTERING SCAN CELLS 25
3.2 OPTICS (ORDERING POINTS TO IDENTIFY THE CLUSTERING
STRUCTURE) 27
3.2.1 DBSCAN (DENSITY-BASED SPATIAL CLUSTERING OF
APPLICATIONS WITH NOISE) 27
3.2.2 OPTICS ALGORITHM 30
3.3 K-MEANS CLUSTERING ALGORITHM 37
3.4 SUMMARY 39

CHAPTER 4 EXPERIMENTAL RESULTS 40
4.1 EXPERIMENT ENVIRONMENT AND PROCEDURE 40
4.2 SIMULATION RESULTS 42

REFERENCES 51

REFERENCES

[1] A. Crouch, “Design-for Test for Digital IC’s and Embedded Core Systems,” Prentice Hall, ISBN: 0-13-084827-1, 1999.
[2] P. Girard, “Survey of Low-Power Testing of VLSI Circuits,” IEEE Design & Test of Computers, vol. 19, no 3, pp. 82-92, May-June 2002.
[3] Y. Zorian, “A Distributed BIST Control Scheme for Complex VLSI Devices,” IEEE VLSI Test Symposium, pp. 4-9, 1993.
[4] S. Wang and S. Gupta, “DS-LFSR: A New BIST TPG for Low Heat Dissipation,” IEEE Intl. Test Conference(ITC), pp. 848-857, 1997.
[5] M.L. Bushnell and V.D. Agrawal, “Essentials of Electronic Testing,” Kluwer Academic Publishers, ISBN 0-7923-7991-8, 2000.
[6] A. Hertwig and H.J. Wunderlich, “Low Power Serial Built-In Self-Test,” IEEE European Test Workshop, pp. 49-53, 1998.
[7] Y. Bonhomme, P. Girard, C. Landrault and S. Pravossoudovitch, “Power Driven Chaining of Flip-Flops in Scan Architectures,” IEEE Intl. Test Conference (ITC), pp. 796-803, 2002.
[8] M. Ankerst, M.M. Breunig, H.P. Kriegel, J. Sander, “OPTICS: Ordering Points To Identify the Clustering Structure,” ACM SIGMOD Conference, pp. 49-60, 1999.
[9] J. Han, M. Kamber, “Data Mining: Concepts and Techniques,” Morgan Kaufmann, ISBN: 1558604898, 2000.
[10] V. Dabholkar, S. Chakrabarty, I. Pomeranze and S.M. Reddy, “Techniques for Reducing Power Dissipation During Test Application in Full Scan Circuits,” IEEE Trans. on CAD, vol. 17, no. 12, pp. 1325-1333, Dec. 1998.
[11] Y. Bonhomme, P. Girard, L. Guiller, C. Landrault and S. Pravossoudovitch, “Efficient Scan Chain Design for Power Minimization During Scan Testing Under Routing Constraint,” IEEE Intl. Test Conference (ITC), pp. 488-493, 2003.
[12] Y. Bonhomme, P. Girard, L. Guiller, C. Landrault and S. Pravossoudovitch, “ Design of Routing-Constrained Low Power Scan Chains,” IEEE Design, Automation and Test in Europe Conference and Exhibition (DATE’04), pp. 1530-1591, 2004.
[13] B. Pouya and A. Crouch, “Optimization Trade-offs for Vector Volumn and Test Power,” IEEE Intl. Test Conference (ITC), pp. 873-881, 2000.
[14] R. Sankaralingam, R. Oruganti and N. Touba, “Static Computation Techniques to Control Scan Vector Power Dissipation,” IEEE VLSI Test Symposium, pp.35-42, 2000.
[15] M. Ester, H.P. Kriegel, J.Sander, X. Xu, “A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise,” Intl. Conf. on Knowledge and Discovery and Data Mining (KDD’96), pp.226-231, 1996.
[16] N. Beckmann, H.P. Kriegel, R. Schneider, B. Seeger, “ The R*-tree: An Efficient and Robust Access Method for Points and Rectangles,” ACM SIGMOD Conference, pp. 322-331, 1990.