본 논문에서는 단일 명령어, 다중 데이터 처리 기반의 매니코어 프로세서를 이용하여 높은 계산량이 요구되는 차감 클러스터링 알고리즘을 병렬 구현하고 성능을 향상시킨다. 또한 차감 클러스터링 알고리즘을 위한 최적의 매니코어 프로서서 구조를 선택하기 위해 다섯 가지의 프로세싱 엘리먼트 (processing element, PE) 구조 (PEs=16, 64, 256, 1,024, 4,096)를 모델링하고, 각 PE구조에 대해 실행시간 및 에너지 효율을 측정한다. 두 가지 의료 영상 및 각 영상의 세 가지 해상도(($128{\times}128$, $256{\times}256$, $512{\times}512$)를 이용하여 모의 실험한 결과, 모든 경우에 대해 PEs=4,096구조에서 최고의 성능 및 에너지 효율을 보였다.
본 논문에서는 단일 명령어, 다중 데이터 처리 기반의 매니코어 프로세서를 이용하여 높은 계산량이 요구되는 차감 클러스터링 알고리즘을 병렬 구현하고 성능을 향상시킨다. 또한 차감 클러스터링 알고리즘을 위한 최적의 매니코어 프로서서 구조를 선택하기 위해 다섯 가지의 프로세싱 엘리먼트 (processing element, PE) 구조 (PEs=16, 64, 256, 1,024, 4,096)를 모델링하고, 각 PE구조에 대해 실행시간 및 에너지 효율을 측정한다. 두 가지 의료 영상 및 각 영상의 세 가지 해상도(($128{\times}128$, $256{\times}256$, $512{\times}512$)를 이용하여 모의 실험한 결과, 모든 경우에 대해 PEs=4,096구조에서 최고의 성능 및 에너지 효율을 보였다.
This paper implements and improves the performance of high computational subtractive clustering algorithm using a single instruction, multiple data (SIMD) based many-core processor. In addition, this paper implements five different processing element (PE) architectures (PEs=16, 64, 256, 1,024, 4,096...
This paper implements and improves the performance of high computational subtractive clustering algorithm using a single instruction, multiple data (SIMD) based many-core processor. In addition, this paper implements five different processing element (PE) architectures (PEs=16, 64, 256, 1,024, 4,096) to select an optimal PE architecture for the subtractive clustering algorithm by estimating execution time and energy efficiency. Experimental results using two different medical images and three different resolutions ($128{\times}128$, $256{\times}256$, $512{\times}512$) show that PEs=4,096 achieves the highest performance and energy efficiency for all the cases.
This paper implements and improves the performance of high computational subtractive clustering algorithm using a single instruction, multiple data (SIMD) based many-core processor. In addition, this paper implements five different processing element (PE) architectures (PEs=16, 64, 256, 1,024, 4,096) to select an optimal PE architecture for the subtractive clustering algorithm by estimating execution time and energy efficiency. Experimental results using two different medical images and three different resolutions ($128{\times}128$, $256{\times}256$, $512{\times}512$) show that PEs=4,096 achieves the highest performance and energy efficiency for all the cases.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 매니코어 프로세서 상에서 차감 알고리즘을 병렬 구현하여 성능을 향상시킨다. 또한, 본 논문에서는 차감 클러스터링 알고리즘을 위한 최적의 매니코어 프로세서 구조를 탐색하기 위해 총 다섯 가지 PE 구조(PEs=16, 64, 256, 1,024, 4,096)에 대해 실행시간, 시스템 이용률 및 에너지 효율을 측정하였으며, 각 실험은 동일한 28nm 테크놀로지와 1 GHz의 동작 주파수를 사용하였다.
본 논문에서는 매니코어 프로세서를 이용하여 높은 연산량을 요구하는 차감 클러스터링 알고리즘을 병렬 구현하고 성능을 향상시켰다. 또한 차감 클러스터링 알고리즘을 위한 최적의 매니코어 프로서서 구조를 탐색하기 위해 다섯 가지 PE 구조(PEs=16, 64, 256, 1,024, 4,096)를 모델링하고 이에 대한 실행시간, 시스템 이용률 및 에너지 효율을 측정하였다.
본 절에서는 제안하는 매니코어 프로세서와 현재 널리 사용되고 있는 상용 고성능 GPU(NVIDIA Geforce GTX 560)와의 성능을 비교한다. 상용 GPU와의 정확한 비교는 적정하지 않지만 본 절의 목적은 상용 GPU와의 비교를 통해 선택한 최적의 매니코어 프로세서의 잠재가능성을 알아보기 위함이다. 성능 비교를 위해 256×256 크기의 의료영상을 사용하였으며 동일한 클러스터 추정 알고리즘 구현하여 실행시간을 측정하였다.
제안 방법
테일러급수를 이용한 지수함수 결과는 입력 x와 차수 n 의 범위에 따라 큰 영향을 미친다. 따라서 본 논문에서는 식(6)과 같이 matlab에서 제공하는 exp함수의 결과와 테일러급수를 이용한 지수함수 결과와의 오차율을 구하여 적절한 입력 값과 차수 값을 구한다.
표 3은 성능 분석을 위해 모델링된 매니코어 프로세서의 시스템 파라미터로써 각 실험은 다섯 가지의 PE 구조 (PEs=16, 64, 256, 1024, 4096)에 대해 28nm 테크놀로지와 1GHz 클록 주파수를 사용하여 수행하였다. 또한 두 개의 의료영상, 각 영상마다 세 개의 해상도(128x128, 256x256, 512x512) 이용하여 성능을 분석하였다. 매니코어 프로세서 상에서 차감 클러스터링 알고리즘을 수행하기 위한 각 PE의 로컬 메모리 크기는 식 7과 같이 정의한다.
또한, 본 논문에서는 차감 클러스터링 알고리즘을 위한 최적의 매니코어 프로세서 구조를 탐색하기 위해 총 다섯 가지 PE 구조(PEs=16, 64, 256, 1,024, 4,096)에 대해 실행시간, 시스템 이용률 및 에너지 효율을 측정하였으며, 각 실험은 동일한 28nm 테크놀로지와 1 GHz의 동작 주파수를 사용하였다. 또한 두 개의 의료영상, 세 가지 해상도(128x128, 256x256, 512x512)해상도 및 클러스터 개수를 달리하여 성능을 분석하였다.
본 논문에서는 매니코어 프로세서를 이용하여 높은 연산량을 요구하는 차감 클러스터링 알고리즘을 병렬 구현하고 성능을 향상시켰다. 또한 차감 클러스터링 알고리즘을 위한 최적의 매니코어 프로서서 구조를 탐색하기 위해 다섯 가지 PE 구조(PEs=16, 64, 256, 1,024, 4,096)를 모델링하고 이에 대한 실행시간, 시스템 이용률 및 에너지 효율을 측정하였다. 두 가지 의료영상 및 각 영상마다 3가지 해상도 (128x128, 256x256, 512x512)를 사용하여 모의 실험한결과, PEs=4,096구조에서 최고의 성능 및 에너지 효율을 보였다.
본 논문에서는 매니코어 프로세서 상에서 차감 알고리즘을 병렬 구현하여 성능을 향상시킨다. 또한, 본 논문에서는 차감 클러스터링 알고리즘을 위한 최적의 매니코어 프로세서 구조를 탐색하기 위해 총 다섯 가지 PE 구조(PEs=16, 64, 256, 1,024, 4,096)에 대해 실행시간, 시스템 이용률 및 에너지 효율을 측정하였으며, 각 실험은 동일한 28nm 테크놀로지와 1 GHz의 동작 주파수를 사용하였다. 또한 두 개의 의료영상, 세 가지 해상도(128x128, 256x256, 512x512)해상도 및 클러스터 개수를 달리하여 성능을 분석하였다.
테크놀로지 레벨에서는 Synopsys Design Compiler 툴과 TSMC 28 nm 공정을 이용하여 아키텍처 레벨에서 설계되어진 RTL 코드를 합성한다. 마지막으로 디자인 공간 탐색기를 이용하여 PE 구조별 실행시간, 시스템 이용률 및 에너지 효율을 측정한다.
성능 비교를 위해 256×256 크기의 의료영상을 사용하였으며 동일한 클러스터 추정 알고리즘 구현하여 실행시간을 측정하였다.
실험 결과, 가장 오차율이 큰 –20에서 차수 68부터 안정적인 오차율 값을 출력하므로 본 논문에서는 차수를 68로 정하며, 입력 값이 –20 이하일 경우 결과 값을 0 으로 출력한다.
애플리케이션 레벨에서는 매니코어 프로세서용 시뮬레이터를 이용하여 차감 클러스터링 알고리즘에 대한 실행 사이클 개수, 동적 명령어 빈도, 시스템 이용률 등의 데이터를 추출한다. 아키텍처 레벨에서는 register-transfer level (RTL) Verilog를 이용하여 모델링된 매니코어 아키텍처를 설계한다. 테크놀로지 레벨에서는 Synopsys Design Compiler 툴과 TSMC 28 nm 공정을 이용하여 아키텍처 레벨에서 설계되어진 RTL 코드를 합성한다.
그림 4(b)는 초기 최대 포텐셜 값을 추출하기 위한 연산 과정을 보여준다. 이 과정에서 사용되는 지수함수는 매니코어 프로세서에서 제공되지 않기 때문에 본 논문에서는 shift, branch, arithmetic 명령어 (e.g., LSH, BGE, MUL, ADD, and SUB)를 사용하여 식(5)와 같이 테일러급수를 이용하여 지수함수를 구현한다.
차감 클러스터링 알고리즘을 위한 매니코어 프로세서의 성능 평가를 위해 본 논문에서는 실행 시간(execution time), 에너지 효율(energy efficiency) 및 시스템 이용률(System utilization)을 측정하며, 이는 표 2와 같다. 실행 시간은 차감 클러스터링 알고리즘을 완료하는데 소요되는 시간을 뜻하며, 에너지 효율은 소비된 에너지 당 처리량, 시스템 이용률은 실행시간 동안 전체 PE 수에 대한 실제 동작 하는 PE 수의 비율로 정의된다.
아키텍처 레벨에서는 register-transfer level (RTL) Verilog를 이용하여 모델링된 매니코어 아키텍처를 설계한다. 테크놀로지 레벨에서는 Synopsys Design Compiler 툴과 TSMC 28 nm 공정을 이용하여 아키텍처 레벨에서 설계되어진 RTL 코드를 합성한다. 마지막으로 디자인 공간 탐색기를 이용하여 PE 구조별 실행시간, 시스템 이용률 및 에너지 효율을 측정한다.
표 3은 성능 분석을 위해 모델링된 매니코어 프로세서의 시스템 파라미터로써 각 실험은 다섯 가지의 PE 구조 (PEs=16, 64, 256, 1024, 4096)에 대해 28nm 테크놀로지와 1GHz 클록 주파수를 사용하여 수행하였다. 또한 두 개의 의료영상, 각 영상마다 세 개의 해상도(128x128, 256x256, 512x512) 이용하여 성능을 분석하였다.
대상 데이터
그림 7은 매니코어 프로세서의 실행시간, 시스템 이용률및 에너지 효율을 평가하기 위한 실험 방법론을 보여준다. 실험 방법론은 애플리케이션, 아키텍처 및 테크놀로지 레벨로 구성되어 있다. 애플리케이션 레벨에서는 매니코어 프로세서용 시뮬레이터를 이용하여 차감 클러스터링 알고리즘에 대한 실행 사이클 개수, 동적 명령어 빈도, 시스템 이용률 등의 데이터를 추출한다.
데이터처리
본 절에서는 제안하는 매니코어 프로세서와 현재 널리 사용되고 있는 상용 고성능 GPU(NVIDIA Geforce GTX 560)와의 성능을 비교한다. 상용 GPU와의 정확한 비교는 적정하지 않지만 본 절의 목적은 상용 GPU와의 비교를 통해 선택한 최적의 매니코어 프로세서의 잠재가능성을 알아보기 위함이다.
성능/효과
4.3절에서 설명하였듯이 PE 개수가 증가함에 따라 PE 에 할당된 픽셀 연산에서 포텐셜 값 연산은 산술·논리 연산명령어만으로 이루어져 PE 수가 256까지는 시스템 이용률이 크게 변하지 않는다.
또한 차감 클러스터링 알고리즘을 위한 최적의 매니코어 프로서서 구조를 탐색하기 위해 다섯 가지 PE 구조(PEs=16, 64, 256, 1,024, 4,096)를 모델링하고 이에 대한 실행시간, 시스템 이용률 및 에너지 효율을 측정하였다. 두 가지 의료영상 및 각 영상마다 3가지 해상도 (128x128, 256x256, 512x512)를 사용하여 모의 실험한결과, PEs=4,096구조에서 최고의 성능 및 에너지 효율을 보였다. 또한 선택된 매니코어 구조는 상용 GPU보다 약 4.
차감 클러스터링 알고리즘은 한 픽셀 데이터를 기준으로 전체 픽셀 데이터와의 비교를 통해 가장 큰 밀집도의 포텐셜 값을 구하는 연산을 반복 수행한다. 따라서 본 논문에서는 차감 클러스터링 알고리즘의 반복적인 연산을 매니코어를 이용하여 병렬 구현함으로써 성능 향상을 꽤한다. 본 논문에서 병렬 구현한 차감 클러스터링 알고리즘의 순서도는 그림 3과 같다.
두 가지 의료영상 및 각 영상마다 3가지 해상도 (128x128, 256x256, 512x512)를 사용하여 모의 실험한결과, PEs=4,096구조에서 최고의 성능 및 에너지 효율을 보였다. 또한 선택된 매니코어 구조는 상용 GPU보다 약 4.4배 더 높은 성능을 보였다.
이는 그림 12(a)와 같이 PE 구조별 에너지의 변화폭은 일정하지만 실행시간은 PE의 수가 증가함에 따라 약 4배씩 감소하기 때문이다. 또한 해상도가 128x128에서 512x512로 증가할수록 더 높은 에너지 효율을 보이는데 이는 해상도가 증가할수록 더 많은 픽셀 데이터를 처리하고, 로컬 메모리의 사이즈 또한 증가하기 때문에 더 높은 효율성을 보인다. 그림 12(b)-(d)에서 보듯이 각 해상 도마다 PE 구조별 에너지 변화가 다른 것을 확인할 수 있다.
위와 같은 이유로 클러스터 개수가 다른 영상의 경우라도 영상의 사이즈가 같은 경우 서로 비슷한 실행시간이 요구된다. 또한 해상도별 실행시간도 해상도 증가에 따라 실행시간이 약 16배 증가하는 것을 알 수 있다. 하지만 PE 수가 4배씩 증가하지만 실행시간은 4배씩 감소되지 않는 것을 확인할 수 있다.
후속연구
향후 본 연구를 실제 FPGA 보드에 구현하여 본 논문의 결과를 검증할 계획이다.
질의응답
핵심어
질문
논문에서 추출한 답변
차감 클러스터링 알고리즘은 무엇인가?
차감 클러스터링 알고리즘은 Mountain 클러스터링 알고리즘[18]의 확장된 형태로서 데이터의 밀집도에 의해 클러스터의 수를 구하는 알고리즘이다. 각 데이터는 다른 모든 데이터와의 비교를 통해 거리에 반비례하는 포텐셜 값을 계산하고 가장 큰 포텐셜 값을 갖는 데이터를 클러스터의 중심 값으로 결정한다.
FCM 알고리즘의 초기 값을 계산할 때 통계학적 연구에 의해 경험적 또는 선험적으로 얻어진 유효성 지표를 이용한 방법의 문제점은?
FCM 알고리즘의 초기 값을 계산하는 방법 중에 통계학적 연구에 의해 경험적 또는 선험적으로 얻어진 유효성 지표를 이용한 방법이 제안되어져 왔다[6-8]. 하지만 이와 같은 방법은 특정한 영상에 대한 지표 값을 기준으로 클러스터의 개수를 판별하기 때문에 여러 가지 영상 데이터의 클러스터링 환경에서 보편적으로 적용할 수 없는 문제점이 있다[5].
퍼지 클러스터링 이란?
대표적인 영상 분할 알고리즘인 퍼지 클러스터링 (fuzzy c-means clustering, FCM) 기법은 같은 클러스터에 속하는 픽셀 정보의 소속 정도를 이용하여 개체 또는 패턴을 분류하는 방법으로 패턴 인식, 이미지 분석, 유전자 분류 분야에서 널리 사용되어져 왔다[3-5]. 하지만 FCM 알고리즘은 초기에 클러스터 개수 및 클러스터 중심 값이 임의적으로 선택 되기 때문에 정확한 클러스터링 결과를 보장하지 못하며, 또한 임계치를 만족하기 위해 반복 횟수가 증가하게 된다.
참고문헌 (26)
M. Smelyanskiy, D. Holmes, J. Chhugani, A. Larson, D. M. Carmeans, D. Hanson, P. Dubey, K. Augustine, D. Kim, A. Kyker, V. W. Lee, A. D. Nguyen, L. Seiler, R. Robb, "Mapping High-Fidelity Volume Rendering for Medical Imaging to CPU, GPU and Many-Core Architectures," IEEE Trans. on Visualization and Computer Graphics, Vol. 15, No. 6, pp. 1563-1579, 2009.
S. Krinidis, V. Chatzis, "A Robust Fuzzy Local Information C-Mans Clustering Algorithm," IEEE Transactions on Image Processing, vol. 19, no. 5, pp. 1328-1337, 2010.
J. Bezdek, Pattern Recognition With Fuzzy Objective Function Algorithm. New York: Plenum, 1981.
D. Pham, "An Adaptive Fuzzy C-Means Algorithm for Image Segmentation in the Presence of Intensity Inhomogeneities," Pattern Recognition Letters, vol. 20, pp. 57-68, 1999.
J. D. Owens, M. Houston, D. Luebke, S. Green, J. E. Stone and J. C. Phillips, "An Initialization Method for Fuzzy C-means Algorithm using Subtractive Clustering," Proceedings of IEEE, vol.96, no.5, pp. 879-899, 2010.
R. J. Cho, M. Huang, M. J. Campbell, H. Dong, L. Steinmetz, L. Sapinoso, et al, "Transcriptional Regulation and Function during the Human Cell Cycle," Nature Genetics article, vol. 27, pp. 48-54, 2001.
Y. I. Kim, D. W. Kim, D. Lee, K.H. Lee, "A Cluster Validation Index for GK Cluster Analysis based on Relative Degree of Sharing," Information Sciences, vol. 168, pp. 225-242, 2004.
Y. Okada, T. Sahara, H. Mitsubayashi, S. Ohgiya, T. Nagashima, "Knowledge-assisted Recognition of Cluster Boun-daries in Gene Expression Data," Artif. Intell. Med., vol. 35, pp. 171-183, 2005.
S.L. Chiu, "Extracting Fuzzy Rules from Data for Function Approximation and Pattern Classification," Fuzzy Information Engineering: a Guide Tour of Applications, pp. 149-162, 1997.
Z.h. Sun, "Study on Subtractive Clustering Video Moving Object Locating Method with Introduction of Eigengap," in the 9th International Conference on Fuzzy Systems and Knowledge Discovery, pp. 609-612, 2012.
S.H. Lee, "The Design and Implementation of Parallel Processing System using the Nios ^{(R)} II Embedded Processor," The Korea Society of Computer and Information, vol. 14, no. 11, pp. 97-103, Nov. 2009.
A. Gentile and D. S. Wills, "Portable Video Supercomputing," IEEE Trans. on Computers, vol. 53, no. 8, pp. 960-973, 2004.
Y.H. Kim and J.M. Kim, "Design Space Exploration of Optimal many-Core Processors for Discrete Wavelet Transform," Journal of Institute of Embedded Engineering of Korea, vol. 7, no. 5, pp. 277-284, 2012.
Y.M. Kim and J.M. Kim, "Design and Verification of High-Performance Parallel Processor Hardware for JPEG Encoder," Journal of Institute of Embedded Engineering of Korea, vol. 6, no. 2, pp. 100-107, 2011.
S. Sonntag, and F. Gilabert, "Design Space Exploration and Performance Evaluation at Electronic System Level for NoC-based MPSoC," IEEE/ACM International Conf. Computer-Aided Design, pp. 336-339, 2010.
H.G. Lee, U.Y. Ogras, R. Marculescu, and N. Chang, "Design Space Exploration and Prototyping for On-chip Multimedia Applications," Proceedings of the 43rd Annual Design Automation Conf., pp. 137-142, 2006.
R. Yager, D. Filev, "Generation of Fuzzy Rules by Mountain Clustering," Journal of Intelligent and Fuzzy Systems., vol. 2, no. 3, pp. 209-219, 1994.
S.G. Park, S.J. Choi, "Modeling of Left Ventricular Assist Device and Suction Detection Using Fuzzy Subtractive Clustering Method," Korea Intelligent Information System Society, vol. 22, no. 4, pp. 500-506, 2012.
R. Qun, L. Baron, and M. Balazinski, "Type-2 Takagi-Sugeno-Kang Fuzzy Logic Modeling using Subtractive Clustering," Fuzzy Information Processing Society., pp. 120-125, 2006.
B.-K. Choi, J.-M. Kim, "Implementation of Multi-Core Processor for Beamforming Algorithm of Mobile Ultrasound Image Signals," Journal of The Korea Society of Computer and Information, vol. 18, no. 2, pp. 1-8, 2011.
S.-M. Kang, J.-M. Kim, "Multimedia Extension Instructions and Optimal Many-core Processor Architecture Exploration for Portable Ultrasonic Image Processing," Journal of The Korea Society of Computer and Information, vol. 17, no. 8, pp. 1-10, 2012.
J.-Y. Kim, D.-G. Son, J.-M. Kim, H.-S. Jeon, "Parallel Implementation and Performance Evaluation of the SIFT Algorithm Using a Many-Core Processor, " Journal of The Korea Society of Computer and Information, vol. 18, no. 8, 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 The Korea Society of Computer and Information, vol. 18, no. 10, pp. 1-12, 2013.
I.-K. Jung, J.-S. Seo, M.-S. Kang, C.-H. Kim, J.-M. Kim, "Implementation and Performance Analysis of Fuzzy C-Means Algorithm Using GPGPU," Journal of Korean Institute of Next Generation Computing, vol. 9, no. 5, pp. 27-37, 2013.
S.-H. Yi, Y.-S. Woo, B.-N. Jang and Y.-M. Yi, "Efficient Local Binary Pattern Based Face Recognition Using OpenCL on the Embedded GPU," Journal of Korean Institute of Information Scientists and Engineers, vol. 40, no. 6, pp. 257-265, 2013.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.