[논문]특이치 분해를 위한 최적의 2차원 멀티코어 시스템 탐색

박용훈; 김철홍; 김종면

doi:10.9708/jksci.2014.19.9.021

특이치 분해를 위한 최적의 2차원 멀티코어 시스템 탐색
Exploration of an Optimal Two-Dimensional Multi-Core System for Singular Value Decomposition 원문보기

韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information, v.19 no.9, 2014년, pp.21 - 31

박용훈 (울산대학교 전기전자컴퓨터공학과) , 김철홍 (전남대학교 전자컴퓨터공학부) , 김종면 (울산대학교 전기전자컴퓨터공학과)

초록
AI-Helper

특이치 분해는 다양한 분야의 데이터 집단에서 고유한 특성을 찾는 특징 추출 분야에 많이 활용되고 있다. 하지만 특이치 분해의 복잡 행렬 연산은 많은 연산 시간을 요구한다. 본 논문에서는 특이치 분해의 대표적인 알고리즘인 one-sided block Jacobi를 고속 처리하기 위해 2차원 멀티코어 시스템을 이용하여 효율적으로 병렬 구현하고 성능을 향상시킨다. 또한, one-sided block Jacobi 알고리즘의 다양한 행렬 ($128{\times}128$, $64{\times}64$, $32{\times}32$, $16{\times}16$)을 서로 다른 2차원 PE 구조에 구현하고 성능 및 에너지를 분석함으로써 각 행렬에 대한 최적의 멀티코어 구조를 탐색한다. 더불어 동일한 행렬의 one-sided block Jacobi 알고리즘에 대해 선택된 멀티코어 구조와 상용 고성능 그래픽스 프로세싱 유닛 (GPU)과의 성능 비교를 통해 제안한 2차원 멀티코어 방법의 잠재 가능성을 확인한다.

Abstract ▼ AI-Helper

Singular value decomposition (SVD) has been widely used to identify unique features from a data set in various fields. However, a complex matrix calculation of SVD requires tremendous computation time. This paper improves the performance of a representative one-sided block Jacoby algorithm using a two-dimensional (2D) multi-core system. In addition, this paper explores an optimal multi-core system by varying the number of processing elements in the 2D multi-core system with the same 400MHz clock frequency and TSMC 28nm technology for each matrix-based one-sided block Jacoby algorithm ($128{\times}128$, $64{\times}64$, $32{\times}32$, $16{\times}16$). Moreover, this paper demonstrates the potential of the 2D multi-core system for the one-sided block Jacoby algorithm by comparing the performance of the multi-core system with a commercial high-performance graphics processing unit (GPU).

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

하지만 one-sided block Jacobi의 경우 선형의 PE 구조뿐만 아니라 직사각형 혹은 정사각형 형태의 PE 구조를 통해서 더욱더 성능을 향상시킬 수 있다. 따라서 본 논문에서는 one-sided block Jacobi 알고리즘의 다양한 행렬(128x128, 64x64, 32x32, 16x16)을 서로 다른 2차원 PE 아키텍처의 멀티코어 시스템에 병렬구현하고 그에 대한 성능 및 에너지 효율을 분석함으로써 각 행렬의 특이치 분해 알고리즘에 대한 최적의 멀티코어 구조를 탐색하고자 한다.
본 논문에서는 다양한 애플리케이션의 특징 추출에서 널리 사용되고 있는 특이치 분해 알고리즘인 one-sided bloc Jacobi를 가속화하기 위하여 2차원 멀티코어 시스템을 이용하여 병렬 구현하였다. 또한 one-sided block Jacobi 알고리즘의 다양한 행렬 구조를 서로 다른 2차원 PE 구조에 구현하고 성능 분석한 결과를 바탕으로 각 행렬에 대해 최적인 2차원 PE구조를 탐색하였다.
반면 멀티코어 시스템은 400MHz의 동작주파수로 동작한다. 상용 GPU와의 정확한 비교는 적정하지 않지만 본 절의 목적은 상용 GPU와의 비교를 통해 선택한 최적의 멀티코어 시스템의 잠재가능성을 알아보기 위함이다. 표 4는 서로 다른 행렬에 대해 상용 GPU와 멀티코어 시스템의 실행시간을 보여준다.

제안 방법

본 논문에서는 SIMD 기반 멀티코어 프로세서를 이용하여 one-sided block Jacobi 알고리즘의 성능을 가속화한다. 또한 one-sided block Jacobi 알고리즘의 다양한 행렬 구조(128x128, 64x64, 32x32, 16x16)를 서로 다른 형태의 2차원 PE 구조에 구현하고 성능 분석을 통해 최적의 PE구조를 선택한다. 또한 동일한 one-sided block Jacobi 알고리즘에 대해 선택한 멀티코어의 PE구조와 상용 고성능 그래픽스 프로세싱 유닛 (GPU)와 성능 비교를 통해 제안하는 멀티코어 프로세서에 대한 잠재가능성을 입증한다.
본 논문에서는 다양한 애플리케이션의 특징 추출에서 널리 사용되고 있는 특이치 분해 알고리즘인 one-sided bloc Jacobi를 가속화하기 위하여 2차원 멀티코어 시스템을 이용하여 병렬 구현하였다. 또한 one-sided block Jacobi 알고리즘의 다양한 행렬 구조를 서로 다른 2차원 PE 구조에 구현하고 성능 분석한 결과를 바탕으로 각 행렬에 대해 최적인 2차원 PE구조를 탐색하였다. 또한 선택된 멀티코어 시스템을 상용 고성능 GPU와의 성능 비교를 통해 선택된 멀티코어 시스템이 one-sided block Jacobi 알고리즘 처리에 대해 잠재 가능성이 있음을 보였다.
병렬 구조에서 가장 작은 값을 찾기 위해서는 PE 간의 데이터 전송을 이용해서 각 PE에 분산된 min 값을 모아야 한다. 본 논문에서 사용한 2차원 멀티코어 시스템에서는 비활성화 PE가 있는지를 확인하여 각 PE가 가지고 있는 min 값을 tolerance 값과 비교하여 더 작은 값이 있으면 알고리즘이 종료되도록 구현하였다.
본 논문에서는 SIMD 기반 멀티코어 프로세서를 이용하여 one-sided block Jacobi 알고리즘의 성능을 가속화한다. 또한 one-sided block Jacobi 알고리즘의 다양한 행렬 구조(128x128, 64x64, 32x32, 16x16)를 서로 다른 형태의 2차원 PE 구조에 구현하고 성능 분석을 통해 최적의 PE구조를 선택한다.
이를 해결하기 위해 선형 프로세싱 엘리먼트 (processing element, PE) 구조를 이용하여 one-sided Jacobi 알고리즘의 2개 열 단위를 각각의 PE에 맵핑해 병렬 처리가 가능하게 함으로써 성능을 향상시켰다[21]. 하지만 one-sided block Jacobi 알고리즘의 행렬 크기에 비해 사용가능한 PE 개수가 제한적이라는 단점이 있다.
표 2는 본 논문에서 사용한 2차원 멀티코어 모델의 파라미터를 보여준다. 특징 추출 분야에서 많이 사용되는 특이치 분해의 4가지 행렬(128x128, 64x64, 32x32 16x16)을 여러가지 형태의 2차원 멀티코어 구조에 병렬 구현하여 성능 및 효율을 분석한다.

대상 데이터

본 절에서는 선택된 멀티코어 시스템과 상용 고성능 GPU와의 성능 비교를 보여준다. 본 실험에서 사용된 GPU는 NVIDIA GTX 560으로 336개의 코어, 1GB 글로벌 메모리 및 48KB 공유 메모리를 가지고 있으며, 1,620MHz 동작주파수로 동작한다. 반면 멀티코어 시스템은 400MHz의 동작주파수로 동작한다.
One-sided block Jacobi 알고리즘의 4가지 행렬(128x128, 64x64, 32x32 16x16)에 대한 PE 구조별 시스템 면적 및 에너지 소비는 표 3에 기술되어 있다. 시스템 면적과 에너지를 구하기 위해 Synopsis사의 design compiler(DC)를 이용하였으며 TSMC 28nm 공정을 사용하였다. 시스템 면적은 PE 수의 증가에 따른 면적이외의 PE간의 와이어 등으로 인해 PE 개수가 2배씩 증가할 때 시스템 면적은 2배 이상 증가한다.

성능/효과

또한 one-sided block Jacobi 알고리즘의 다양한 행렬 구조(128x128, 64x64, 32x32, 16x16)를 서로 다른 형태의 2차원 PE 구조에 구현하고 성능 분석을 통해 최적의 PE구조를 선택한다. 또한 동일한 one-sided block Jacobi 알고리즘에 대해 선택한 멀티코어의 PE구조와 상용 고성능 그래픽스 프로세싱 유닛 (GPU)와 성능 비교를 통해 제안하는 멀티코어 프로세서에 대한 잠재가능성을 입증한다.
또한 one-sided block Jacobi 알고리즘의 다양한 행렬 구조를 서로 다른 2차원 PE 구조에 구현하고 성능 분석한 결과를 바탕으로 각 행렬에 대해 최적인 2차원 PE구조를 탐색하였다. 또한 선택된 멀티코어 시스템을 상용 고성능 GPU와의 성능 비교를 통해 선택된 멀티코어 시스템이 one-sided block Jacobi 알고리즘 처리에 대해 잠재 가능성이 있음을 보였다. 향후 본 논문에서의 멀티코어 모델을 FPGA 프로토타입 시스템에 구현하여 기능 및 성능을 재검증할 예정이다.
[transfer a, b, c] 함수의 경우는 PE 수가 2배씩 증가 할 때 일정한 수준으로 증가한다. 마지막으로 [transfer cs, sn] 함수는 cs와 sn 값을 분산된 열의 데이터를 가지고 있는 나머지 PE들에게 전달하는 기능으로써 PE 수가 2배씩 증가하면 사이클 수도 2배씩 증가하지만, 소요되는 연산량이 다른 함수보다 상대적으로 작기 때문에 전체 사이클 수에는 거의 영향을 미치지 않는다. 함수 중에서 [make a, b, c]와 [col-update] 함수가 가장 큰 사이클 수를 요구한다.

후속연구

또한 선택된 멀티코어 시스템을 상용 고성능 GPU와의 성능 비교를 통해 선택된 멀티코어 시스템이 one-sided block Jacobi 알고리즘 처리에 대해 잠재 가능성이 있음을 보였다. 향후 본 논문에서의 멀티코어 모델을 FPGA 프로토타입 시스템에 구현하여 기능 및 성능을 재검증할 예정이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	특이치 분해는 어떤 특징을 가지는가?	특이치 분해는 특이치 값의 특징인 유일성, 행렬의 일부분이 변해도 특이치는 크게 변하지 않는 시스템의 안정성, 그리고 행렬의 계수가 작은 근사 행렬로 쉽게 변환 할 수 있는 근사화의 특징을 가지고 있어[1-9] 다양한 분야의 특징 추출 연구에 많이 활용 되고 있다. 특이치 분해가 많이 활용되고 있는 분야로는 전력 전달, 영상 처리, 오디오 및 음성 처리, 패턴 인식, 머신 지능, 의학 영상 등이 있다[10]-[20].
	특이치 분해에 상당한 처리 시간이 요구되는 문제를 해결하기 위해 어떻게 하였는가?	이를 해결하기 위해 선형 프로세싱 엘리먼트 (processing element, PE) 구조를 이용하여 one-sided Jacobi 알고리즘의 2개 열 단위를 각각의 PE에 맵핑해 병렬 처리가 가능하게 함으로써 성능을 향상시켰다[21]. 하지만 one-sided block Jacobi 알고리즘의 행렬 크기에 비해 사용가능한 PE 개수가 제한적이라는 단점이 있다.
	특이치 분해가 많이 활용되는 분야는?	특이치 분해는 특이치 값의 특징인 유일성, 행렬의 일부분이 변해도 특이치는 크게 변하지 않는 시스템의 안정성, 그리고 행렬의 계수가 작은 근사 행렬로 쉽게 변환 할 수 있는 근사화의 특징을 가지고 있어[1-9] 다양한 분야의 특징 추출 연구에 많이 활용 되고 있다. 특이치 분해가 많이 활용되고 있는 분야로는 전력 전달, 영상 처리, 오디오 및 음성 처리, 패턴 인식, 머신 지능, 의학 영상 등이 있다[10]-[20]. 하지만 특이치 분해는 행렬식이나 고차 방정식 해법과 같은 복잡 행렬 연산을 요구하기 때문에 상당한 처리 시간이 요구된다.

참고문헌 (30)

E. Beltrami, "On bilinear functions," Journal of Mathematics, Vol. 11, pp. 98-106, 1873.
C. Jordan, "Memory on bilinear forms," Journal of Pure and Applied Mathematics, Vol. 19, pp. 35-54, 1874.
J. J. Sylvester, "A new proof that a general quadric may be reduced to its canonical form (that is, a linear function of squares) by means of a real orthogonal substitution," Messenger of Mathematics, Vol. 19, pp. 1-5, 1889.
E. Schmidt, "On the theory of linear and nonlinear integral equations," Journal of Mathematische Annalen, Vol. 65, pp. 370-399, 1907.
H. Weyl, "The asymptotic law granting the eigenvalues of linear partial differential equations with an application of the theory of black body radiation," Journal of Mathematische Annalen, Vol. 71, pp. 441-479, 1912.

상세보기
K. Fernando, H. Nicholson, "Identification of linear systems with input and output noise: the Koopmans-Levin method," IEE Proceedings. Control Theory and Applications, Vol. 132, pp. 30-36, 1985.

상세보기
Ake Bjorck, "A bidiagonalization algorithm for solving large and sparse ill-posed systems of linear equations," Journal of BIT Numerical Mathematics, Vol. 28, pp. 659-670, 1988.

상세보기
M. Darouach, M. Zasadzinski, S. J. Xu, "Full-order observers for linear systems with unknown inputs," IEEE Transaction on Automatic Control, Vol. 39, No. 3, pp. 606-609, March 1994.

상세보기
R. G. King, M. W. Watson, "System reduction and solution algorithm for singular linear difference systems under rational expectations," Journal of Computational Economics, Vol. 20, pp. 57-86, 2002.
A. Samui, S. R. Samantaray, "Wavelet singular entropy-based islanding detection in distributed generation," IEEE Transaction on Power Delivery, Vol. 28, No. 1, pp. 411-418, January 2013.

상세보기
W. Dong, G. Shi, and X. Li, "Nonlocal image restoration with bilateral variance estimation : a low-rank approach," IEEE Transactions on Image Processing, Vol. 22, No. 2, pp. 700-711, 2012.
F. G. Yan, M. Jin, X. Qiao, "Low-complexity DOA estimation based on compressed MUSIC and its performance analysis," IEEE Transactions on Signal Processing, Vol. 61, No. 8, pp 1915-1930, 2013.

상세보기
S. C. Chan, Y. J. Chu, Z. G. Zhang, K. M. Tsui, "A NEW variable regularized QR decomposition-based recursive least M-estimate algorithm-performance analysis and acoustic applications," IEEE Transactions on Audio, Speech, and Language Processing, Vol. 21, No. 5, pp. 907-922, May. 2013.

상세보기
A Rajwade, A Rangarajan, A Banerjee, "Image denoising using the higher order singular value decomposition," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 35, No. 4, pp. 849-862, April 2013.

상세보기
Shutao Li, Leyuan Fang, Haitao Yin, "An efficient dictionary learning algorithm and its application to 3-D medical image denoising," IEEE Transactions on Biomedical Engineering, Vol. 59, No. 2, pp. 417-427, February 2012.

상세보기
A. Jindal, Mingyan Liu, "Networked computing in wireless sensor networks for structural health monitoring," IEEE Transactions on Networking, Vol. 20, No. 4, pp. 1203-1216, August 2012.

상세보기
G. Tang, A. Nehorai, "Stability of low-rank matrix reconstruction: A constrained singular value view," IEEE Transactions on Information Theory Society, Vol. 58, No. 9, 2012.
G. H. Golub and C. Reinsch, "Singular value decomposition and least square solutions," Journal of Numerische Mathematik, Vol. 14, No. 5, pp. 403-420, Apr. 1970.

상세보기
J. Demmel, K. Veselic, "Jacobi's method is more accurate than QR," SIAM Journal on Matrix Analysis and Applications, Vol. 13, No. 4, pp. 1204-1245, 1992.

상세보기
B. A. Chartres, "Adaptation of the Jacobi method for a computer with magnetic-tape backing store," The Computer Journal, Vol. 5, No. 1, pp. 51-60, 1962.

상세보기
V. L. Charles, "The block Jacobi method for computing the singular value decomposition," Cornell University, 1985.
B. B. Zhou, R. P. Brent, M. Kahn, "A one-sided Jacobi algorithm for the symmetric eigenvalue problem," in Proc. of 3rd Parallel Computing Workshop, 1994.
B. B. Zhou, R. P. Brent, "A parallel ring ordering algorithm for efficient one-sided Jacobi SVD computations," Journal of Parallel and Distributed Computing, Vol. 42, No. 1, pp. 1-10, 1997.

상세보기
B. B. Zhou, R. P. Brent, "On parallel implementation of the one-sided Jacobi algorithmfor singular value decompositions," in Proceedings of Euromicro Workshop on Parallel and Distributed Processing, pp. 401-408, 1995.
Y. Takahashi, Y. Hirota, Y. Yamamoto, "Performance of the block Jacobi method for the symmetric eigenvalue problem on a modern massively parallel computer," in Proceedings of Algoritmy, pp. 151-160, 2012.
I, Bethune, J. M. Bull, N. J. Dingle, N. J. Higham, " Performance analysis of asynchronous Jacobi's method implemented in MPI, SHMEM and OpenMP," Manchster Institute for Mathematical Sciences School of Mathematics, 2012.
A. Gentile, D. S. Wills, "Portable video supercomputing," IEEE Transactions on Computers, Vol. 53, No. 8, pp. 960-973, 2004.

상세보기
S. M. Kang, J. M. Kim, "Multimedia extension instructions and optimal many-core processor architecture exploration for portable ultrasonic image processing," Journal of Korea Society Computer Institute, Vol. 17, No. 8, pp. 1-10, 2012.

원문보기 상세보기
J. Y. Kim. D. K. Shon, J. M. Kim, H. S. Jun "Parallel implementation and performance evaluation of the SIFT algorithm using a many-core processor," Journal of Korea Society Computer Institute, Vol. 18, No. 9, pp. 1-10, 2013.

원문보기 상세보기
J. S. Seo, M. S. Kang, C. H. Kim, J. M. Kim, "Design space exploration of embedded many-core processors for real-time fire feature extraction," Journal of Korea Society Computer Institute, Vol. 18, No. 10, pp. 1-12, 2013.

원문보기 상세보기

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증