Một số phương pháp gia tăng hiệu suất xử lý trên GPU đối với các bài toán song song không đầy đủ

THE INTERNATIONAL CONFERENCE ON MARINE SCIENCE AND TECHNOLOGY 2016 
HỘI NGHỊ QUỐC TẾ KHOA HỌC CÔNG NGHỆ HÀNG HẢI 2016 441 
Một số phương pháp gia tăng hiệu suất xử lý trên GPU đối với các bài toán 
song song không đầy đủ 
Methods to enhance the computing performance on GPU in not-fully parallelized problems 
Vũ Đình Trung, Nguyễn Trọng Đức 
Trường Đại học Hàng hải Việt Nam, 
trungvd@vimaru.edu.vn 
Tóm tắt 
Sự ra đời của các bộ xử lý đồ họa GPU (Graphics Processing Units) đã làm thay đổi đáng 
kể hiệu năng của các hệ thống tính toán bởi khả năng xử lý song song trong các bộ xử lý này. Tuy 
nhiên, với những bài toán song song không đầy đủ NFPP (not-fully parallelized problems) khi vẫn 
tồn tại trong nó các ràng buộc về xử lý và dữ liệu thì việc sử dụng GPU khi thực hiện các bài toán 
này không đạt được hiệu quả như mong đợi. Trong phạm vi của bài báo, nhóm tác giả đề xuất một 
số phương pháp nhằm nâng cao hiệu suất tính toán trên GPU cho các bài toán NFPP. Các phương 
pháp đề xuất được áp dụng trong trường hợp cụ thể là bài toán tìm trọng tâm cụm trong phân cụm 
dữ liệu mờ tổng quát GFKM (Generalized Fuzzy k-Means clustering). 
Từ khóa: Song song không đầy đủ, bộ xử lý đồ họa, phân cụm. 
Abstract 
The introduction of the Graphics Processing Units have changed significantly the 
performance of the computing system by the parallel processing capability of this processors. 
However, with the not-fully parallelized problems (NFPP) when it still exists the constraints of data 
and processing, the use of GPU performing this task has not achieved the expected efficiency. 
Within the scope of this paper, the authors propose some methods to enhance the computing 
performance on the GPU for NFPP. The proposed methods are applied in a specified case, which 
is the problem of finding cluster centers in the generalized fuzzy k-means clustering. 
Keywords: Not-fully Parallelized, GPU, data clustering. 
1. Đặt vấn đề 
Trong các bài toán song song không đầy đủ luôn tồn tại các ràng buộc về xử lý và dữ liệu. 
Như vậy, việc sử dụng GPU khi thực hiện các bài toán này không đạt được hiệu quả vì không thể 
tách rời từng bước xử lý để thực thi song song. Ngoài ra, một bài toán song song không đầy đủ 
cũng có thể được tạo lên từ các bài toán con song song không đầy đủ khác, như vậy việc truy cập 
dữ liệu là không đồng nhất. Để hạn chế các ràng buộc dữ liệu, tăng tính song song cho các bài toán 
NFPP, các giải pháp đã đề xuất [1, 7] thường tập trung vào việc sắp xếp lại dữ liệu nhằm đạt được 
hiệu quả truy cập bộ nhớ tốt nhất, sau đó một giải thuật song song sẽ được áp dụng để thu gọn các 
dữ liệu này. 
Trong phạm vi của bài báo, nhóm tác giả đề xuất hai giải thuật: giải thuật sắp xếp đếm song 
song, và giải thuật sắp xếp theo khóa ổn định. Các giải thuật được áp dụng trong bài toán tìm trọng 
tâm cụm của phân cụm dữ liệu mờ tổng quát. Để triển khai các thuật toán, các thư viện Thrust của 
CUDA [2] được sử dụng. 
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: mô 
hình, kiến trúc bộ xử lý đồ họa GPU và CUDA; mục 3 - Bài toán tìm trọng tâm cụm: các bước xử 
lý, các phương pháp đề xuất và kết quả thực nghiệm; mục 4 - Kết luận, là những đánh giá về các 
phương pháp đã đề xuất, hướng nghiên cứu, phát triển tiếp theo. 
2. Bộ xử lý đồ họa GPU 
2.1. Kiến trúc GPU 
Bộ xử lý đồ họa GPU được thiết kế đặc biệt cho việc tính toán chuyên sâu và song song hóa 
[1, 10]. Để đạt được hiệu suất song song cao, các GPU sử dụng kiến trúc một dòng lệnh - đa luồng 
THE INTERNATIONAL CONFERENCE ON MARINE SCIENCE AND TECHNOLOGY 2016 
HỘI NGHỊ QUỐC TẾ KHOA HỌC CÔNG NGHỆ HÀNG HẢI 2016 442 
xử lý (SIMT - Single Instruction - Multi Threads) (hình 1). Một số lượng rất lớn các luồng được 
thực thi song song trên các dữ liệu khác nhau. 
Hình 1. Kiến trúc bộ xử lý đồ họa GPU 
2.2. Kiến trúc tính toán hợp nhất CUDA 
Nhằm tăng hiệu năng xử lý cho GPU, một kiến trúc lập trình song song mục đích chung - 
kiến trúc thiết bị tính toán hợp nhất CUDA (Compute Unified Device Architecture) đã được 
NVIDIA đề xuất [1]. Trong mô hình lập trình theo kiến trúc CUDA, GPU được xem như một bộ 
đồng xử lý có khả năng xử lý một số lượng lớn các luồng song song. Một chương trình nguồn đơn 
giản bao gồm các mã chủ chạy trên CPU và các mã hạt nhân chạy trên GPU, khi đó các tính toán 
chuyên sâu và các tác vụ song song được cài đặt như các mã hạt nhân thực thi trên GPU. Các luồng 
của GPU được tổ chức thành các khối luồng, mỗi khối được xử lý đồng bộ trên một bộ xử lý luồng. 
Các luồng trong một khối luồng có thể chia sẻ dữ liệu thông qua bộ nhớ chia sẻ và có thể thực hiện 
các đồng bộ biên, nhưng không có cơ chế đồng bộ tự nhiên nào cho các khối luồng khác nhau ngoại 
trừ việc dừng chạy mã hạt nhân. Tùy thuộc vào số bộ xử lý luồng trên GPU mà các mã hạt nhân có 
thể chạy song song hoặc xen kẽ; khi một mã hạt nhân kết thúc, bộ xử lý luồng có thể lên lịch trình 
để xử lý mã hạt nhân tiếp theo. 
3. Bài toán tìm trọng tâm cụm 
3.1. Tính toán trọng tâm cụm 
Trong thuật toán phân cụm mờ tổng quát GFKM, việc tính toán trọng tâm cụm mới được 
xác định bởi biểu thức (1) [8]: 
Cj(p+1) = 


ji
ji
S
q
ji
S
i
q
ji
u
u
X
X
X
,
,
 , for S j = {Xi: Cj NNTi, i = 1 to N} (1) 
Trong đó: 
p: vòng lặp hiện tại, Cj(p+1) là trọng tâm cụm mới thứ j (j = 1...k); 
Xi: điểm dữ liệu thứ I; 
NNTi: M chỉ số trọng tâm cụm gần nhất của Xi. Giá trị tối ưu của M được chỉ ra trong [8] là 2; 
ui,j: hệ số thành viên xác định mức độ Xi thuộc về cụm Cj, ui,j [0;1]; 
q: hệ số mờ hóa (fuzzifier), giá trị tối ưu của q được xác định theo biểu thức (2) [9]. 
q = 1 + (
N
1418
+22.05)d-2 + (
N
33.12
+0.243)d-0.0406In(N)-0.1134 (2) 
với N là số điểm dữ liệu trong tập dữ liệu và d là số chiều của dữ liệu. 
THE INTERNATIONAL CONFERENCE ON MARINE SCIENCE AND TECHNOLOGY 2016 
HỘI NGHỊ QUỐC TẾ KHOA HỌC CÔNG NGHỆ HÀNG HẢI 2016 443 
Trong bước cập nhật hệ số thành viên ui,j trước đó, dữ liệu là một ma trận hai chiều kích 
thước N×d với số hàng là số điểm dữ liệu và số cột là số chiều của dữ liệu. Ma trận hai chiều N×d 
được lưu dưới dạng mảng một chiều. Mỗi luồng sẽ truy cập đến vùng bộ nhớ của một điểm dữ liệu 
liên tục hợp nhất như được thể hiện trong hình 2 và tính toán M hệ số thành viên lớn nhất cho điểm 
dữ liệu đó. Điều này giúp đạt được hiệu suất truy cập bộ nhớ tốt nhất khi tiêu tốn ít chu kỳ lệnh 
hơn, khi đó thời gian thực thi lệnh sẽ giảm đáng kể bởi nhiều luồng có thể hoạt động song song 
đồng bộ trên GPU. 
Hình 2. Sự truy cập dữ liệu hợp nhất 
Tuy nhiên, việc lưu trữ dữ liệu dưới dạng này sẽ gây khó khăn cho bước tìm trọng tâm cụm 
mới tiếp theo. Tại bước này, mỗi luồng sẽ thực hiện việc tính toán một trọng tâm cụm mới dựa trên 
việc thu gọn các điểm dữ liệu thuộc về cụm đó. Các điểm thuộc về một cụm là rời rạc, do đó việc 
truy cập tới các điểm dữ liệu lúc này sẽ thiếu sự hợp nhất (hình 3). 
Hình 3. Sự truy cập dữ liệu không hợp nhất 
Trong biểu thức (1), phần tử số, việc nhân hệ số thành viên với véc tơ điểm dữ liệu có thể 
thực thi song song trên từng chiều (hình 4), tuy nhiên, việc truy cập tới các hệ số thành viên của 
từng điểm dữ liệu cũng thiếu sự hợp nhất. 
Hình 4. Xử lý song song trên từng chiều của các điểm dữ liệu 
3.2. Phương pháp đề xuất 
Đầu tiên, dữ liệu sẽ được chuyển vị từ N×d thành d×N sử dụng hàm chuyển vị trong thư 
viện CUBLAS của CUDA [3], nhằm đạt được sự truy cập bộ nhớ tốt hơn trên từng chiều dữ liệu 
(hình 5). 
Hình 5. Dữ liệu được chuyển vị (d×N) 
Các luồng T1 T2 T3  TN-1 TN
Dữ liệu X (N ×d ) X1 X2 X3  XN-1 XN
Các luồng T1 T2 T3  Tk-1 Tk
Dữ liệu X (N ×d ) X1 X2 X3 X4 X5 X6  XN-1 XN
Các luồng T1,1 T1,2 T1,3  T1,d-1 T1,d
Điểm dữ liệu X1 X1,1 X1,2 X1,3  X1,d-1 X1,d
Điểm dữ liệu X3 X3,1 X3,2 X3,3  X3,d-1 X3,d
Lượt thứ d T1 T2  
Lượt thứ hai T1 T2  
Lượt thứ nhất T1 T2  
Dữ liệu X (d ×N ) X1,1 X2,1  XN ,1 X1,2 X2,2  XN ,2  X1,d X2,d  XN ,d
THE INTERNATIONAL CONFERENCE ON MARINE SCIENCE AND TECHNOLOGY 2016 
HỘI NGHỊ QUỐC TẾ KHOA HỌC CÔNG NGHỆ HÀNG HẢI 2016 444 
Tiếp theo, để đạt được hiệu suất truy cập điểm dữ liệu và hệ số thành viên tốt hơn, mảng 
NNT sẽ được sắp xếp theo khóa là chỉ số trọng tâm cụm và các giá trị được sắp xếp theo là chỉ số 
các điểm dữ liệu và hệ số thành viên thuộc về từng cụm. 
Các giải thuật sắp xếp cho mảng NNT: 
Giải thuật sắp xếp đếm song song: 
Bước 1: tìm histogram hay số điểm dữ liệu thuộc về mỗi cụm; 
Bước 2: quét scan để tính chỉ số điểm dữ liệu bắt đầu của mỗi cụm; 
Bước 3: sắp xếp đếm dựa trên mảng scan. 
Bước 1 và 3 sử dụng cùng một kỹ thuật song song là các thao tác nguyên tử. Khi nhiều 
luồng cùng gia tăng số điểm của một cụm nhất định, các thao tác nguyên tử đảm bảo các luồng thực 
hiện mà không bị xung đột việc đọc và ghi dữ liệu với các luồng khác. Tuy nhiên, việc sử dụng các 
thao tác nguyên tử để sắp xếp không đảm bảo thứ tự của các chỉ số điểm dữ liệu thuộc về mỗi cụm 
và dẫn đến việc truy cập chéo dữ liệu làm giảm hiệu suất (hình 6). 
Hình 6. Truy cập chéo tới các điểm dữ liệu 
Giải thuật sắp xếp theo khóa ổn định sử dụng thư viện Thrust của CUDA. Giải thuật sắp xếp 
này đảm bảo thứ tự của các chỉ số điểm dữ liệu sau khi sắp xếp, giúp tránh được việc truy cập chéo 
dữ liệu (hình 7). Song, việc khởi tạo và duy trì thứ tự trong hàm này dẫn tới việc tốn thời gian xử lý 
hơn, đôi khi không bù được cho thời gian xử lý nhanh hơn trong bước tiếp theo, đặc biệt đối với các 
bộ dữ liệu không đủ lớn. 
Hình 7. Truy cập tuần tự tới các điểm dữ liệu 
Sau hai bước tiền xử lý trên, việc tính toán trọng tâm cụm mới sẽ đạt hiệu suất tốt hơn. Cụ 
thể, mỗi mã hạt nhân có thể xử lý trên từng cụm và từng chiều dữ liệu. Các mã hạt nhân này sử 
dụng giải thuật rút gọn song song tối ưu được phát triển bởi Mark Harris [7] và có thể chạy song 
song hoặc xen kẽ trên các bộ xử lý luồng độc lập (hình 8). 
Trong ví dụ minh họa ở hình 8, sau các bước chuyển vị và sắp xếp, mỗi mã hạt nhân sẽ 
được thực thi trên một bộ xử lý luồng nhất định. Với cụm thứ nhất, SM1 thực thi mã hạt nhân tính 
tổng các hệ số thành viên hay mẫu số của biểu thức (1) trong khi SM2, SM3, và SM4 thực thi mã 
hạt nhân tính tổng các tích hệ số thành viên hay tử số của biểu thức (1) lần lượt trên chiều thứ nhất, 
thứ hai và thứ 3. Sau đó, công việc chia tử số cho mẫu số có thể thực hiện trên cả GPU hoặc CPU. 
Luồng T1 T2 T3  T1 T2 T3  T1 T2 T3 
Dữ liệu X (d ×N ) X1,1 X2,1  XN ,1 X1,2 X2,2  XN ,2  X1,d X2,d  XN ,d
Luồng T1 T2 T3  T1 T2 T3  T1 T2 T3 
Dữ liệu X (d ×N ) X1,1 X2,1  XN ,1 X1,2 X2,2  XN ,2  X1,d X2,d  XN ,d
THE INTERNATIONAL CONFERENCE ON MARINE SCIENCE AND TECHNOLOGY 2016 
HỘI NGHỊ QUỐC TẾ KHOA HỌC CÔNG NGHỆ HÀNG HẢI 2016 445 
Hình 8. Sắp xếp theo chỉ số cụm 
3.3. Kết quả thực nghiệm 
Để kiểm chứng các phương pháp đề xuất, nhóm tác giả tiến hành thực nghiệm trên PC với 
một cạc đồ họa tầm trung NVIDIA GeForce GTX 760 [4, 5] và CPU Intel(R) Core(TM) i5-4690 
[6]. 
Thực nghiệm thứ nhất: thực hiện với bộ dữ liệu trung bình “LBP” sinh từ ba ảnh thực: 
“Lena,” “Baboon,” và “Peppers”. Bộ dữ liệu 16 chiều, bao gồm 49.152 điểm dữ liệu và số trọng 
tâm cụm là 8. Kết quả thực nghiệm được chỉ ra trong bảng 1 cho thấy phương pháp sắp xếp đếm 
cho kết quả tốt hơn phương pháp sắp xếp theo khóa ổn định. Kết quả không tốt của phương pháp 
sắp xếp theo khóa ổn định trong trường hợp này là do việc tốn thời gian khởi tạo và duy trì thứ tự 
trong xử lý sắp xếp với bộ dữ liệu không đủ lớn như đã trình bày trong phần 3.2. 
Bảng 1. Sắp xếp trên bộ dữ liệu “LBP” 
CPU GPU - sắp xếp đếm 
GPU - sắp xếp theo khóa 
ổn định 
1.00 1.52 0.98 
Thực nghiệm thứ hai: thực hiện trên bộ dữ liệu lớn “poker”, bao gồm 10 chiều dữ liệu với 
1.025.010 dòng và số trọng tâm cụm là 10. Kết quả thực nghiệm được chỉ ra trong Bảng 2 và Hình 
9 cho thấy khi k < 8 phương pháp sắp xếp theo khóa ổn định tốt hơn phương pháp sắp xếp đếm. 
Ngược lại, khi k > 8, sự tăng tốc của cả hai phương pháp có sự chênh lệch không lớn. Kết quả này 
là do với cùng một bộ dữ liệu khi số trọng tâm cụm càng lớn thì số điểm dữ liệu thuộc về từng cụm 
càng giảm, khi đó sẽ không khai thác hết được khả năng tính toán song song của GPU, dẫn đến sự 
tăng tốc của cả hai phương pháp đều giảm. 
Bảng 2. Sắp xếp trên bộ dữ liệu “poker” 
CPU GPU - sắp xếp đếm GPU - sắp xếp theo khóa 
ổn định 
1.00 1.85 1.89 
Chỉ số
1 1 3 7 1 2 0.9 0.1 0 0 0.9 0.1
2 3 5 6 1 3 0.9 0 0.1 0 0.9 0.1
3 8 4 9 1 4 0.85 0 0 0.15 0.85 0.15
4 7 9 10 3 1 0.1 0 0.9 0 0.9 0.1
5 4 3 6 3 4 0 0 0.75 0.25 0.75 0.25
6 2 6 5 2 3 0 0.8 0.2 0 0.8 0.2
7 3 10 1 2 4 0 0.85 0 0.15 0.85 0.15
8 10 1 8 4 2 0 0.1 0 0.9 0.9 0.1
X (3x8) 1 2 3 4 5 6 7 8
1 1 3 8 7 4 2 3 10 SM2 1 2 3 4
2 3 5 4 9 3 6 10 1 SM3 4 4 4 4
3 7 6 9 10 6 5 1 8 SM4 0 4 8 12
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
NNT 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4
Chỉ số X 1 2 3 4 1 6 7 8 2 4 5 6 3 5 7 8
U' 0.9 0.9 0.85 0.1 0.1 0.8 0.85 0.1 0.1 0.9 0.75 0.2 0.15 0.25 0.15 0.9
NNT(M=2) Hệ số thành viên U U'
SM1
Chuyển vị dữ 
liệu
Sắp xếp theo 
chỉ số cụm
Dữ liệu X (8x3)
Đầu vào
Cụm
Histogram
Scan
THE INTERNATIONAL CONFERENCE ON MARINE SCIENCE AND TECHNOLOGY 2016 
HỘI NGHỊ QUỐC TẾ KHOA HỌC CÔNG NGHỆ HÀNG HẢI 2016 446 
Hình 9. Quan hệ giữa hiệu suất hệ thống và số lượng trọng tâm cụm 
Thực nghiệm thứ ba: thực hiện trên bộ dữ liệu nhân tạo với 491.520 điểm dữ liệu, 8 trọng 
tâm cụm và số chiều dữ liệu d thay đổi. 
Hình 10. Quan hệ giữa hiệu suất hệ thống và số chiều dữ liệu 
Hình 10 cho thấy, phương pháp sử dụng sắp xếp đếm, tốc độ giảm khá nhanh từ khoảng 2.3 
xuống 1.8 khi d nhỏ hơn 16; sau đó, tốc độ có sự lên xuống không ổn định nhưng vẫn duy trì trong 
khoảng 1.6 đến 1.8. Với phương pháp sử dụng sắp xếp theo khóa ổn định, tốc độ tăng nhanh từ 
khoảng 1.5 tới 2.5 khi d nhỏ hơn 64; khi số chiều lớn hơn, tốc độ duy trì ổn định ở khoảng 2.5. 
THE INTERNATIONAL CONFERENCE ON MARINE SCIENCE AND TECHNOLOGY 2016 
HỘI NGHỊ QUỐC TẾ KHOA HỌC CÔNG NGHỆ HÀNG HẢI 2016 447 
Trong thí nghiệm này, với số lượng trọng tâm cụm nhỏ thì số điểm dữ liệu thuộc về mỗi 
cụm sẽ đủ lớn và sức mạnh của GPU được khai thác tốt. Sự khác biệt trong kết quả đạt được giữa 
hai phương pháp được lí giải là do phương pháp sắp xếp đếm liên quan đến các thao tác nguyên tử, 
thiếu tính ổn định cho các chỉ số điểm dữ liệu thuộc về từng cụm và do đó làm giảm hiệu suất truy 
cập bộ nhớ. Phương pháp sắp xếp theo khóa ổn định giúp cho việc truy cập bộ nhớ trên từng chiều 
dữ liệu hiệu quả, đặc biệt khi số lượng chiều dữ liệu ngày càng tăng. 
4. Kết luận 
Trong bài báo, nhóm tác giả đã phân tích các yếu tố ảnh hưởng đến hiệu suất xử lý song 
song trong các bài toán song song không đầy đủ, từ đó đưa ra các phương pháp gia tăng hiệu suất 
xử lý các bài toán này trên các bộ xử lý đồ họa. Kết quả thực nghiệm trên bộ xử lý đồ họa GPU tầm 
trung, số lượng bộ xử lý luồng hạn chế, các phương pháp đề xuất đều cho kết quả khá khả quan, 
nhanh hơn trung bình từ 1.5 đến 3 lần so với xử lý trên CPU. Những kết quả nghiên cứu có thể làm 
cơ sở khi giải quyết các bài toán dữ liệu lớn bằng phương pháp phân cụm, như: bài toán phân tích 
dữ liệu tuyến, luồng giao thông, bài toán nguồn nhân lực thuyền viên, 
Tài liệu tham khảo 
[1]. NVIDIA. “CUDA C programming guide”. CUDA toolkit documentation. March-2015. 
NVIDIA corporation, accessed 01 April 2015. 
[2]. NVIDIA. “Thrust quick start guide”. CUDA toolkit documentation. March-2015. NVIDIA 
corporation, accessed 01 April 2015. 
[3]. NVIDIA. “CUBLAS library v7.0”. CUDA toolkit documentation. March-2015. NVIDIA 
corporation, accessed 01 April 2015. 
[4]. NVIDIA. “CUDA GPUs”. NVIDIA developer. March-2015. NVIDIA corporation. accessed 
01 April 2015. 
[5]. NVIDIA. “Geforce GTX 760”. Geforce. March-2015. NVIDIA corporation, accessed 01 
April 2015. 
[6]. Intel. “CPU Intel(R) Core(TM) i5-4690”. Intel processor specifications. Intel corporation. 
accessed 01 April 2015. 
[7]. Harris M.. “Optimizing parallel reduction in cuda”. NVIDIA developer technology, 2007. 
pp1-38. 
[8]. Jen-Che Lai. “Generalized fuzzy k-means clustering using m nearest cluster centers”. Master 
of science thesis. National Taiwan Ocean University. June-2013. pp1-18. 
[9]. V. Schwammle and O. N. Jensen. “A simple and fast method to determine k-means cluster 
analysis”. Bioinformatics, Vol. 26. September-2010. pp2841-2848. 
[10]. You Li, Kaiyong Zhao, Xiaowen Chu, and Jiming Liu. “Speeding up k-means algorithm by 
GPU”. CIT 2010 IEEE 10th international conference on. Bradford. June-2010. pp115-122. 
[11]. Bin Zheng, Jinbiao Chen, Shaosheng Xia, and Yongxing Jin. “Data analysis of vessel 
traffic flow using clustering algorithms”. Intelligent computation technology and 
automation (ICICTA). 2008 international conference on, Hunan. Vol#2. November-2008. 
pp243-246. 
[12]. Eva Lema, George P. Vlachos, and Dimitrios Zikos. Linking causal factors and the human 
element in maritime accidents using K-means clustering. International journal of risk 
assessment and management. Vol.19. No.3. pp.214-227.