대용량 위성영상의 무감독 분류를 위한 k-Means Clustering 알고리즘의 병렬처리: 다중코어와 PC-Cluster를 이용한 Hybrid 방식 = Parallel Processing of k-Means Clustering Algorithm for Unsupervised Classification of Large Satellite Images: A Hybrid Method Using Multicores and a PC-Cluster

다국어 초록 (Multilingual Abstract)

In this study, parallel processing codes of k-means clustering algorithm were developed and implemented in a PC-cluster for unsupervised classification of large satellite images. We implemented intra-node code using multicores of CPU (Central Processing Unit) based on OpenMP (Open Multi-Processing), inter-nodes code using a PC-cluster based on message passing interface, and hybrid code using both. The PC-cluster consists of one master node and eight slave nodes, and each node is equipped with eight multicores. Two operating systems, Microsoft Windows and Canonical Ubuntu, were installed in the PC-cluster in turn and tested to compare parallel processing performance. Two multispectral satellite images were tested, which are a medium-capacity LANDSAT 8 OLI (Operational Land Imager) image and a high-capacity Sentinel 2A image. To evaluate the performance of parallel processing, speedup and efficiency were measured. Overall, the speedup was over N / 2 and the efficiency was over 0.5. From the comparison of the two operating systems, the Ubuntu system showed two to three times faster performance. To confirm that the results of the sequential and parallel processing coincide with the other, the center value of each band and the number of classified pixels were compared, and result images were examined by pixel to pixel comparison. It was found that care should be taken to avoid false sharing of OpenMP in intra-node implementation. To process large satellite images in a PC-cluster, code and hardware should be designed to reduce performance degradation caused by file I / O. Also, it was found that performance can differ depending on the operating system installed in a PC-cluster.

국문 초록 (Abstract)

본 연구에서는 대용량 위성영상의 무감독분류를 위해 k-means clustering 알고리즘의 병렬처리 코드를 개발하여 PC-cluster에서 구현하였다. 이를 위해 OpenMP (Open Multi-Processing)를 기반으로 CPU (Central Processing Unit)의 다중코어를 이용하는 intra-node 코드와 message passing interface를 기반으로 PC-cluster를 이용하는 inter-nodes 코드, 그리고 이 둘을 병용하는 hybrid 코드를 구현하였다. 본 연구에 사용한 PC-cluster는 한 대의 마스터 노드와 여덟 대의 슬래이브 노드로 구성되어 있고 각 노드에는 여덟 개의 다중코어가 장착되어 있다. PC-cluster에는 Microsoft Windows와 Canonical Ubuntu의 두 가지 운영체제를 설치하여 병렬처리 성능을 비교하였다. 실험에 사용한 자료는 두 가지 다중분광 위성영상으로서 중용량인 LANDSAT 8 OLI (Operational Land Imager) 영상과 대용량인 Sentinel 2A 영상이다. 병렬처리의 성능을 평가하기 위하여 speedup과 efficiency를 측정한 결과 전반적으로 speedup은 N/2 이상, efficiency는 0.5 이상으로 나타났다. Microsoft Windows와 Canonical Ubuntu를 비교한 결과 Ubuntu가 2-3배의 빠른 결과를 나타내었다. 순차처리와 병렬처리 결과가 일치하는지 확인하기 위해 각 클래스의 밴드별 중심값과 분류된 화소의 수를 비교하고 결과 영상간 화소대 화소 비교도 수행하였다. Intra-node 코드를 구현할 때에는 OpenMP에 의한 false sharing이 발생하지 않도록 주의해야 하고, PC-cluster에서 대용량 위성영상을 처리하기 위해서는 파일 I/O에 의한 성능저하를 줄일 수 있도록 코드 및 하드웨어를 설계해야 함을 알 수 있었다. 또한 PC-cluster에 설치된 운영체제에 따라서도 성능 차이가 발생함을 알 수 있었다.

참고문헌 (Reference)

1 한수희, "대용량 위성영상의 무감독 분류를 위한 K-means 군집화 알고리즘의 병렬처리" 한국측량학회 35 (35): 187-194, 2017

2 Argonne National Laboratory, "The message passing interface (MPI) standard" Argonne National Laboratory

3 OpenMP ARB, "The OpenMP API specification for parallel programming" OpenMP ARB

4 Eager, D. L., "Speedup versus efficiency in parallel systems" 38 (38): 408-423, 1989

5 Wang, P., "Rapid processing of remote sensing images based on cloud computing" 29 (29): 1963-1968, 2013

6 Sugumaran, R., "Processing remote-sensing data in cloud computing environments, In Remote Sensing Handbook - Three Volume Set" CRC Press 2018

7 IBM, "Parallel processing environments" IBM Knowledge Center

8 Fredj, H. B., "Parallel implementation of Sobel filter using CUDA" 209-212, 2017

9 Koo, I. H, "High-speed processing of satellite image using GPU" Chungnam National University 2012

10 Sánchez, S., "GPU implementation of the pixel purity index algorithm for hyperspectral image analysis" 1-7, 2010

11 Lu, Y., "Fast implementation of image mosaicing on GPU" 1-5, 2017

12 González, C., "FPGA implementation of the pixel purity index algorithm for remotely sensed hyperspectral image analysis" 2010 : 969806-, 2010

13 Gustafson, J. L., "Encyclopedia of Parallel Computing" Springer 53-60, 2011

14 Plaza, A., "Commodity cluster-based parallel processing of hyperspectral imagery" 66 (66): 345-358, 2006

15 Sun, X., "Accelerated segmentation approach with CUDA for high spatial resolution remotely sensed imagery based on improved Mean Shift" 1-6, 2000