본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

배선 길이 최소화를 위한 그룹화된 스캔 체인 재구성 방법
A Grouped Scan Chain Reordering Method for Wire Length Minimization

이정환   (서강대학교 컴퓨터학과UU0000674  ); 임종석   (서강대학교 컴퓨터학과UU0000674  );
  • 초록

    대규모 VLSI 시스템을 설계하는 경우 스캔 플립플롭(이하 셀)을 채택한 스캔 테스트 방법을 사용하여 IC 칩의 테스트를 용이하게 한다. 이러한 경우 스캔체인에서의 스캔 셀들의 연결 순서는 물리적 설계과정인 셀들의 배치가 완료된 후 결정하여도 무방하다. 본 논문에서는 이러한 사실을 이용하여 스캔 셀간의 연결선의 길이가 작도록 이들의 순서를 조정하는 방법을 제안한다. 특히 본 논문에서 제안하는 방법은 스캔 셀들이 클럭 도메인별로 그룹화되어 있을 경우 이들의 순서를 결정하기 위하여 새롭게 제시되는 방법으로 기존의 재구성 방법에 비하여 약 13.6%의 배선길이를 절약할 수 있다. 또한, 스캔 셀 순서에 대한 여러 다양한 제약에 대하여 효율적으로 셀들의 순서를 재구성할 수 있다.


    In order to design a huge VLSI system, the scan testing methodology by employing scan flip-flops(cells) is a popular method to test those If chips. In this case, the connection order of scan cells are not important, and hence the order can be determined in the very final stage of physical design such as cell placement. Using this fact, we propose, in this paper, a scan cell reordering method which minimizes the length of wires for scan chain connections. Especially, our reordering method is newly proposed method in the case when the scan cells are grouped according to their clock domains. In fact, the proposed reordering method reduces the wire length about 13.6% more than that by previously proposed reordering method. Our method may also be applicable for reordering scan chains that have various constraints on the scan cell locations due to the chain grouping.


  • 참고문헌 (13)

    1. K. Nakaumra, et al. 'Scan path's Wire Length Minimization and Its Short Path Error Correction,' NEC Res. And Develop Vol. 38, No.1, pp. 22-27, Jan. 1997 
    2. Barbagallo, S. et al. 'Scan Insertion Criteria for Low Design Impact,' Proc. of 14th VLSI Test Symposium, pp. 26-31, 1996 
    3. J. Schmid & J. Knablein, 'Advanced Synchronous Scan Test Methodology for Multi Clock Domain ASICs,' Proc. of 17th VLSI Test Symposium, 1999 
    4. Freuer, M and C. Koo, 'Method for Rechaining shift Register Latches which Contain more than on Physical Book,' IBM Technical Disclosure Bulletin Vol. 25, No. 9, pp. 4818-4820, Fev. 1983 
    5. E. L. Lawler., J. K. Lensta., A. H. G. Rinnoy Kan., & D.B. Shmoys, eds., The Traveling Salesman Problem, John Wiley & Sons, 1985 
    6. S. Makar, 'A layout-Based Approach for Ordering Scan Chain Flip-Flops,' Proc. of ITC, 1998 
    7. M. Hirech, J. Beausang., & X, Gu. 'A New Approcah to Scan Chain Reordering Using Physical Design Information,' Proc. of ITC, 1998 
    8. D. S. Johnson, 'Local Optimization and the Traveling Salesman Problem,' in Proc. of the 17th Int'l Colloquium on Automata Languages and Programming, pp. 446-460, July 1990 
    9. S. Lin & B. W. Kernighan, 'An Effective Heuristic Algorithm for the Traveling Salesman Problem,' Operations Research 21, pp. 498-516, 1973 
    10. M. Abramovici, M. A. Breuer, & A. D. Friedman, Digital Systems Testing and Testable Design, IEEE Press, 1990 
    11. R. Aroa & A. Albicki, 'Computer-Aided Scan Path Design For Self-Testing Chips,' Proc. of 29th Midwest Symp. on Circuits and Systems, pp. 301-304, Aug 1987 
    12. K. D. Boese, A. B. Kahng., & S. Muddu. 'A New Adaptive Multi-Start Technique for Combinatorial Global Optimizations', Operations Research Letters, 16(2), Sept. 1994, pp. 101-113 
    13. M. R. Garey & D. S. Johnson, Computers and Intractability : A Guide to the Theory of NP-Completeness, W. H, Freeman, 1979 

 저자의 다른 논문

  • 임종석 (27)

    1. 1993 "한쪽으로 기운 허프만 트리에서의 효율적인 허프만 복호 기법" 한국통신학회논문지 = The journal of the Korean institute of communication science 18 (12): 1956~1969    
    2. 1994 "동시 미로 배선 방법에 의한 새로운 FPGA 배선 방법" 電子工學會論文誌. Jounnal of the Korea institute of telematics and electronics. A. A a31 (10): 119~131    
    3. 1995 "16:1 부분 표본 추출 블럭 정합 알고리즘과 이의 하드웨어 설계" 電子工學會論文誌. Journal of the Korea institute of telematics and electronics. B b32 (12): 1624~1634    
    4. 1995 "메탈-메탈 매트릭스 레이아웃 형태의 기능모듈 생성" 電子工學會論文誌. Jounnal of the Korea institute of telematics and electronics. A. A a32 (1): 206~221    
    5. 1996 "게이트 어레이 레이아웃 형태에서의 기능 모듈 편집기의 구현" 정보처리논문지 = The transactions of the Korea Information Processing Society 3 (5): 1240~1252    
    6. 1997 "Field programmable circuit board를 위한 위상 기반 회로 분할" 電子工學會論文誌. Journal of the Korean Institute of Telematics and Electronics. C c34 (2): 38~49    
    7. 1997 "이차원 트랙 할당에 의한 FPGA 상세 배선" 電子工學會論文誌. Journal of the Korean Institute of Telematics and Electronics. C c34 (10): 8~18    
    8. 1999 "한정된 그룹 이동에 의한 위상 기반 회로 분할 방법" 電子工學會論文誌. Journal of the Korean Institute of Telematics and Electronics. C c36 (1): 22~33    
    9. 1999 "다중칩 모듈 설계를 위한 Gridless 배선기" 電子工學會論文誌. Journal of the Korean Institute of Telematics and Electronics. C c36 (9): 28~43    
    10. 2000 "재구성 가능한 회로 보드를 위한 새로운 Quadratic Boolean Programming 수식에 의한 분할" 電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. SD, 반도체 37 (2): 65~77    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기