Nâng cao hiệu năng tính toán cho thuật toán phân cụm FCM

Bài viết đề xuất một giải pháp tăng hiệu năng tính toán của thuật toán FCM bằng việc rút gọn dữ liệu ở những bước song song không đầy đủ với mô hình kiến trúc thiết bị tính toán hợp nhất CUDA (Compute Unified Device Architecture [2]).
Nội dung trích xuất từ tài liệu:
Nâng cao hiệu năng tính toán cho thuật toán phân cụm FCMCHÀO MỪNG NGÀY THÀNH LẬP TRƯỜNG 01/4/2018 NÂNG CAO HIỆU NĂNG TÍNH TOÁN CHO THUẬT TOÁN PHÂN CỤM FCM IMPROVING THE COMPUTING PERFORMANCE FOR FCM CLUSTERING ALGORITHM VŨ ĐÌNH TRUNG, NGUYỄN TRỌNG ĐỨC Khoa Công nghệ thông tin, Trường ĐHHH Việt NamTóm tắt Trong xu hướng phát triển của ngành công nghiệp 4.0, xử lí dữ liệu lớn là vấn đề nhận được nhiều quan tâm của các nhà khoa học. Do khối lượng tính toán rất lớn và phức tạp, việc xử lí dữ liệu lớn thường được thực hiện song song trên các bộ xử lý đa lõi, đa luồng. Tuy nhiên, các thuật toán song song cũng cần phải được áp dụng và cải tiến nhằm phát huy sức mạnh của các bộ xử lý này. Với bộ xử lý đồ họa GPU (Graphics Processing Units), thuật toán phân cụm mờ FCM (Fuzzy C-Means [1]) đã được triển khai một cách hiệu quả, tuy rằng chưa giải quyết được vấn đề song song không đầy đủ NFPP (Not-Fully Parallelized Problem) tại bước tính toán các Trọng tâm cụm (Cluster Centers). Trong bài báo này, các tác giả đề xuất một giải pháp tăng hiệu năng tính toán của thuật toán FCM bằng việc rút gọn dữ liệu ở những bước song song không đầy đủ với mô hình kiến trúc thiết bị tính toán hợp nhất CUDA (Compute Unified Device Architecture [2]). Từ khóa: FCM, song song không đầy đủ, GPU, phân cụm dữ liệu.Abstract In the current trend of 4.0 industry, big data has received considerable attention from scientists. Due to the extremely large and complex data computational volume, big data tasks are typically performed in parallel using the power of massive multi-threading and mutil-core processors. However, the parallel algorithms also need to be applied and improved to harness the power of these processors. With Graphics Processing Units (GPUs), the Fuzzy C-Means (FCM [1]) cluster algorithm has implemented effectively, but not solved the not-fully parallelized problem (NFPP) at the calculating new cluster centers step. In this paper, the authors propose a method to improve the computing performance of the FCM algorithm by reducting data in the not-fully parallelized steps with Compute Unified Device Architecture Model (CUDA [2]). Keywords: FCM, not-fully parallelized, GPU, data clustering.1. Đặt vấn đề Phân cụm dữ liệu đã và đang được áp dụng trong nhiều lĩnh vực, như nhận dạng mẫu [3],nhận dạng người nói [4], khai thác dữ liệu, web [5],… Trong các thuật toán phân cụm được nghiêncứu và áp dụng, thuật toán phân cụm mờ FCM được xem là thuật toán hiệu quả. Thuật toán này sửdụng các độ đo tương tự để gán một điểm dữ liệu tới cụm của nó. Thời gian thực hiện của thuật toán FCM tăng khi số lượng các điểm cũng như số chiều củatập dữ liệu tăng. Vì vậy, để đối mặt với các thách thức của dữ liệu lớn hơn, song song hóa FCM làmột hướng tiếp cận cần thiết. Trong bài báo này, tác giả đề xuất một giải pháp tăng hiệu năng tínhtoán của thuật toán phân cụm mờ FCM bằng việc rút gọn dữ liệu ở những bước song song khôngđầy đủ với mô hình kiến trúc thiết bị tính toán hợp nhất CUDA (Compute Unified Device Architecture). Nội dung bài báo bao gồm 04 mục: Mục 1 - Đặt vấn đề; Mục 2 - Bộ xử lí đồ họa GPU và thuậttoán FCM: mô hình, kiến trúc bộ xử lí đồ họa GPU và thuật toán FCM; Mục 3 - Giải pháp tăng hiệunăng của thuật toán FCM: đề xuất giải pháp tăng hiệu năng của thuật toán FCM; Mục 4 - Kết luận,là những đánh giá về giải pháp đã đề xuất, hướng nghiên cứu, phát triển tiếp theo.2. Bộ xử lí đồ họa GPU và thuật toán phân cụm FCM2.1. Kiến trúc GPU Bộ xử lý đồ họa GPU được thiết kế đặc biệt cho tính toán song song và chuyên sâu [2]. Đểđạt được hiệu suất song song cao, GPU sử dụng kiến trúc Một lệnh đa luồng xử lý (SIMT). Một sốlượng rất lớn các luồng xử lý song song cùng một chuỗi lệnh trên các dữ liệu khác nhau.2.2. Kiến trúc thiết bị tính toán hợp nhất - CUDA Để khai thác sức mạnh của GPU, một kiến trúc lập trình song song mục đích chung - kiến trúcthiết bị tính toán hợp nhất (CUDA [2]) đã được đề xuất bởi NVIDIA. Trong mô hình lập trình CUDA,GPU được xem như một bộ đồng xử lý với khả năng thực hiện song song một số lượng rất lớn cácluồng công việc.Tạp chí Khoa học Công nghệ Hàng hải Số 54 - 4/2018 59 CHÀO MỪNG NGÀY THÀNH LẬP TRƯỜNG 01/4/20182.3. Thuật toán phân cụm FCM Thuật toán phân cụm mờ c-means (FCM) thực hiện việc lặp đi lặp lại bước phân vùng và tạora các cụm mới cho đến khi hội tụ [1]: SC0 = {Cj(0)}: tập các trọng tâm cụm ban đầu với giá trị ngưỡng hội tụ ; SCp: tập hợp các trọng tâm cụm tại bước p; p: bước thực hiện của thuật toán, ban đầu p = 0; d ij : khoảng cách Ơ-clit giữa Xi và Cj. Bước 1: Tính ...