DESIGN OF HYBRID- CLUSTERING ALGORITHM FOR LOW POWER SCAN CHAINS

今日，掃描式(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 5