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

박용훈; Cheol Hong Kim (김철홍); Jong Myon Kim (김종면)

Exploration of an Optimal Two-Dimensional Multi-Core System for Singular Value Decomposition

Journal of The Korea Society of Computer and Information
Abbr : JKSCI
2014, 19(9), pp.21-31
Publisher : The Korean Society Of Computer And Information
Research Area : Engineering > Computer Science

박용훈 ¹, Cheol Hong Kim ², Jong Myon Kim ¹

¹울산대학교
²전남대학교

Accredited

ABSTRACT

Singular value decomposition (SVD) has been widely used to identify unique features from adata set in various fields. However, a complex matrix calculation of SVD requires tremendouscomputation time. This paper improves the performance of a representative one-sided block Jacobyalgorithm using a two-dimensional (2D) multi-core system. In addition, this paper explores anoptimal multi-core system by varying the number of processing elements in the 2D multi-coresystem with the same 400MHz clock frequency and TSMC 28nm technology for each matrix-basedone-sided block Jacoby algorithm (128x128, 64x64, 32x32, 16x16). Moreover, this paper demonstrates the potential of the 2D multi-core system for the one-sided block Jacoby algorithmby comparing the performance of the multi-core system with a commercial high-performancegraphics processing unit (GPU).

KEYWORDS

Design space exploration, singular value decomposition, one-sided block Jacobi, two-dimensional multi-core system

Citation status

* References for papers published after 2023 are currently being built.

[journal] E. Beltrami / 1873 / On bilinear functions / Journal of Mathematics 11 : 98~106

[journal] C. Jordan / 1874 / Memory on bilinear forms / Journal of Pure and Applied Mathematics 19 : 35~54

[journal] J. J. Sylvester / 1889 / 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 19 : 1~5

[journal] E. Schmidt / 1907 / On the theory of linear and nonlinear integral equations / Journal of Mathematische Annalen 65 : 370~399

[journal] H. Weyl / 1912 / 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 71 : 441~479

[confproc] K. Fernando / 1985 / Identification of linear systems with input and output noise : the Koopmans-Levin method / IEE Proceedings. Control Theory and Applications 132 : 30~36

[journal] Åke Björck / 1988 / A bidiagonalization algorithm for solving large and sparse ill-posed systems of linear equations / Journal of BIT Numerical Mathematics 28 : 659~670

[journal] M. Darouach / 1994 / Full-order observers for linear systems with unknown inputs / IEEE Transaction on Automatic Control 39(3) : 606~609

[journal] R. G. King / 2002 / System reduction and solution algorithm for singular linear difference systems under rational expectations / Journal of Computational Economics 20 : 57~86

[journal] A. Samui / 2013 / Wavelet singular entropy-based islanding detection in distributed generation / IEEE Transaction on Power Delivery 28(1) : 411~418

[journal] W. Dong / 2012 / Nonlocal image restoration with bilateral variance estimation : a low-rank approach / IEEE Transactions on Image Processing 22(2) : 700~711

[journal] F. G. Yan / 2013 / Low-complexity DOA estimation based on compressed MUSIC and its performance analysis / IEEE Transactions on Signal Processing 61(8) : 1915~1930

[journal] S. C. Chan / 2013 / 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 21(5) : 907~922

[journal] A Rajwade / 2013 / Image denoising using the higher order singular value decomposition / IEEE Transactions on Pattern Analysis and Machine Intelligence 35(4) : 849~862

[journal] Shutao Li / 2012 / An efficient dictionary learning algorithm and its application to 3-D medical image denoising / IEEE Transactions on Biomedical Engineering 59(2) : 417~427

[journal] A. Jindal / 2012 / Networked computing in wireless sensor networks for structural health monitoring / IEEE Transactions on Networking 20(4) : 1203~1216

[journal] G. Tang / 2012 / Stability of low-rank matrix reconstruction: A constrained singular value view / IEEE Transactions on Information Theory Society 58(9)

[journal] G. H. Golub / 1970 / Singular value decomposition and least square solutions / Journal of Numerische Mathematik 14(5) : 403~420

[journal] J. Demmel / 1992 / Jacobi’s method is more accurate than QR / SIAM Journal on Matrix Analysis and Applications 13(4) : 1204~1245

[journal] B. A. Chartres / 1962 / Adaptation of the Jacobi method for a computer with magnetic-tape backing store / The Computer Journal 5(1) : 51~60

[thesis] V. L. Charles / 1985 / The block Jacobi method for computing the singular value decomposition / Cornell University

[confproc] B. B. Zhou / 1994 / A one-sided Jacobi algorithm for the symmetric eigenvalue problem / Proc. of 3rd Parallel Computing Workshop

[journal] B. B. Zhou / 1997 / A parallel ring ordering algorithm for efficient one-sided Jacobi SVD computations / Journal of Parallel and Distributed Computing 42(1) : 1~10

[confproc] B. B. Zhou / 1995 / On parallel implementation of the one-sided Jacobi algorithmfor singular value decompositions / Proceedings of Euromicro Workshop on Parallel and Distributed Processing : 401~408

[confproc] Y. Takahashi / 2012 / Performance of the block Jacobi method for the symmetric eigenvalue problem on a modern massively parallel computer / Proceedings of Algoritmy : 151~160

[report] I, Bethune / 2012 / Performance analysis of asynchronous Jacobi’s method implemented in MPI, SHMEM and OpenMP / Manchster Institute for Mathematical Sciences School of Mathematics

[journal] A. Gentile / 2004 / Portable video supercomputing / IEEE Transactions on Computers 53(8) : 960~973

[journal] 강성모 / 2012 / Multimedia Extension Instructions and Optimal Many-core Processor Architecture Exploration for Portable Ultrasonic Image Processing / 한국컴퓨터정보학회논문지 / 한국컴퓨터정보학회 17(8) : 1~10

[journal] 김재영 / 2013 / Parallel Implementation and Performance Evaluation of the SIFT Algorithm Using a Many-Core Processor / 한국컴퓨터정보학회논문지 / 한국컴퓨터정보학회 18(9) : 1~10

[journal] 서준상 / 2013 / Design Space Exploration of Embedded Many-Core Processors for Real-Time Fire Feature Extraction / 한국컴퓨터정보학회논문지 / 한국컴퓨터정보학회 18(10) : 1~12

This paper was written with support from the National Research Foundation of Korea.

KJCKorea
Journal Central

Journal of The Korea Society of Computer and Information 2023 KCI Impact Factor : 0.65