Xây dựng cây bát phân dựa trên đường cong lấp đầy không gian với bộ xử lý đồ họa GPU - Châu, Nguyễn Hải (VNU Journal of Science: Natural Sciences and Technology, 2012)
Tóm tắt . Cây bát phân (octree) là một cấu trúc dữ liệu có nhiều ứng dụng trong các lĩnh vực như đồ họa máy tính, mô phỏng và mô hình hóa. Trong mô phỏng động lực phân tử và mô phỏng N -body, cây bát phân được sử dụng nhiều với các thuật toán phân cấp như tree, khai triển đa cực nhanh FMM (fast multipole method) để tính lực tương tác xa. Có nhiều phương pháp và cấu trúc dữ liệu có thể sử dụng để xây dựng cây bát phân. Trong bài báo này, chúng tôi sử dụng đường cong lấp đầy không gian SFC (space-filling curve) để xây dựng cây bát phân và song song hóa thuật toán xây dựng cây trên bộ xử lý đồ họa GPU. Kết quả thực nghiệm trên máy tính Acer 5745G với bộ xử lý Intel Core i3 2.13 GHz, 4GB RAM được trang bị bộ xử lý đồ họa GeForce 310M và máy tính để bàn với CPU Dual-Core AMD Opteron 2216 HE 1.0 GHz, 2GB RAM, được trang bị bộ xử lý đồ họa nVidia GeForce 8800 GT cho thấy, thuật toán song song do chúng tôi cài đặt trên GPU có tốc độ thực hiện nhanh hơn thuật toán tuần tự trên CPU từ 2.1 đến 7 lần đối với các hệ có từ 2 20 đến 10.2 20 phân tử. Đồng thời, mức độ tăng tốc của thuật toán song song xây dựng cây bát phân phụ thuộc vào hai yếu tố chính, đó là tốc độ truyền dữ liệu giữa máy tính với GPU và tốc độ thực hiện thuật toán sắp xếp các phân tử theo khóa Morton trên GPU. Từ khóa : cây bát phân (octree), FMM, treecode, mô phỏng động lực phân tử, mô phỏng N -body, GPU.