Cải thiện tốc độ tìm kiếm của mô hình đồ thị BT-Graph dựa trên nền tảng CUDA

Bài viết Cải thiện tốc độ tìm kiếm của mô hình đồ thị BT-Graph dựa trên nền tảng CUDA đề xuất một hướng tiếp cận mới trong việc cải thiện tốc độ tìm kiếm của mô hình đồ thị BT-Graph bằng phương pháp song song hóa tìm kiếm dựa trên nền tảng CUDA.
Nội dung trích xuất từ tài liệu:
Cải thiện tốc độ tìm kiếm của mô hình đồ thị BT-Graph dựa trên nền tảng CUDA Kỷ yếu Hội nghị Q K Quốc gia lần thứ VIII về Nghiên cứ cơ bản và ứng dụng Công nghệ thông tin (FAIR) Hà Nội, ngày 9 ứu ệ ); 9-10/7/2015 CẢI T THIỆN TỐ ĐỘ T KIẾM CỦA MÔ HÌNH Đ THỊ B T-GRAP ỐC TÌM M Ô ĐỒ PH DỰA TRÊN NỀN TẢN CUDA A NG A Lư ương Hoàng Hướng1, Ngu uyễn Hải Tha 2, Huỳnh X anh Xuân Hiệp3 1 Trung tâm Công ngh phần mềm, Đại học Cần Thơ hệ 2 Vụ K Khoa học, Công nghệ và Môi trường, Bộ Giáo dục và Đ tạo Việt N g G Đào Nam 3 Khoa Công nghệ thông tin và Truyền thông, Nhóm nghiên cứu li ngành DR g n m iên REAM-CTU/IR Đại học Cần Thơ RD, C lhhuong g@ctu.edu.vn, nhthanh@{moet.gov.vn, mo oet.edu.vn}, h hxhiep@ctu.ed du.vn TÓM TẮ - BT-Graph (Graph Model based on Ball Tree Structure) là một mô hìn đồ thị được x dựng dựa tr cấu trúc ẮT h l ) nh xây rên balltree, giúp mô hình hóa hệ t b thống mạng giá sát các bẫy đèn tự động và hỗ trợ tìm kiếm vị trí địa lý. K số lượng vị trí địa lý lớn ám đ m Khi t và không gian đ lý tìm kiếm mở rộng thì cần phải cải thi tốc độ tìm kiếm của mô hì đồ thị BT-G v địa iện k ình Graph. Trong bài viết này, b chúng tôi đề xuấ một hướng tiế cận mới tron việc cải thiện tốc độ tìm kiếm của mô hình đồ thị BT-Grap bằng phương pháp song c ất ếp ng n ếm ph g song hóa thuật toán tìm kiếm dựa trên nền t s tảng CUDA NV VIDIA. Các thự nghiệm được triển khai trê hai thuật toá tìm kiếm ực ợc ên án k-láng giềng gần nhất và tìm k k kiếm đường đi n ngắn nhất dựa trên mô hình đồ thị BT-Graph và cho thấy sự cải thiện tốt về thời gian đ h ự tì kiếm. ìm Từ khóa - CUDA, BT-G a Graph, vị trí địa lý, mạng giám sát bẫy đèn tự động, song son a m ự ng. I. GIỚI THIỆU G U BT-Gra (Graph M aph Model based on Ball Tree St n tructure) [11] là một mô hìn đồ thị được xây dựng dự trên cấu nh c ựa tr balltree [2 [11]. BT-G rúc 21] Graph không c giúp mô hình hóa hệ th chỉ h hống mạng giá sát các bẫy đèn tự động bằng cách ám y đề xuất bán kín hoạt động cho các cảm b tự động, mà còn hỗ trợ tìm kiếm vị tr địa lý [11]. Tuy nhiên, kh số lượng đ nh biến m ợ trí hi tốc vị trí địa lý lớ và không gian địa lý tì kiếm mở rộng thì cần phải cải tiến t độ tìm ki v ớn ìm r p iếm của mô hình đồ thị h BT-Graph. B A) C) B) Hình 1. A) Tậ hợp điểm, B) Cấu trúc Balltr C) Mô hình đồ thị BT-Gra ập ) ree, h aph Ngày n nay, việc sử d dụng Graphic Processing Units (GPUs) [28] đóng vai trò quan trọ trong xử lý các ứng U i ọng l dụng đòi hỏi c phải xử lý song song. N d cần ý Ngoài ra GPUs cũng hỗ trợ tốt trong việc xử lý đồ thị m không cần phải giảm s t mà độ phức tạp củ mô hình đồ thị. Đã có nh nghiên cứ về việc cho thấy hiệu suấ cao giữa xử lý song song trên GPUs đ ủa ồ hiều ứu ất và xử lý tuần t trên CPU [1 [2] [3] [7] [10]. v tự 1] Trong b viết này, c bài chúng tôi đề x xuất một hướn tiếp cận mớ trong việc c thiện tốc đ tìm kiếm củ mô hình ng ới cải độ ủa đồ thị BT-Gra bằng phươ pháp song song hóa th toán tìm kiếm dựa trên nền tảng GP CUDA NVIDIA [6] đ aph ơng g huật k n PUs [15] [16] [26]. Các thực ngh . hiệm được tri khai dựa trên hai thuật toán: tìm kiếm k-láng giền gần nhất [8] [13] [19] iển m ng [23] [24] [25] và tìm kiếm đ đường đi ngắn nhất [5] [9] [17] [18] [27] [29]. n Bài viết được chia th hành năm phần Phần thứ nh giới thiệu về mô hình B n. hất BT-Graph và tì kiếm vị trí địa lý dựa ìm tr mô hình. Phần thứ hai trình bày về CUDA NVID rên DIA. Phần thứ ba trình bày về cải thiện t độ tìm kiế của mô ứ tốc ếm hình đồ thị BT h T-Graph dựa tr nền tảng C rên CUDA. Phần thứ tư trình bày về các thực nghiệm. Phầ cuối cùng là phần kết c ần l lu uận. A II. CUDA NVIDIA CUDA [26] là một mô hình lập trình và là một nền tảng tính toán son song được phát triển bở Công ty m ng ởi NVIDIA. CUD cung cấp k năng kết h giữa kiến trúc phần cứn và phần m N DA khả hợp n ng mềm. CUDA có khả năng tăn đáng kể ó ng hiệu suất tính t h toán bằng cách khai thác sứ mạnh của đơn vị xử lý đồ họa – Graph Processing Units (GPUs) ức đ ồ his ). GPUs [ [16] [28] h trợ đa luồng khổng lồ - nhiều lõi, với số lượng lên đ hàng trăm lõi và hàng ngàn luồng. [6] hỗ g n s đến m n Với số lượng l các lõi GP cung cấp một khả năng xử lý dữ liệu song song, chính vì điều đó GPUs đượ sử dụng V lớn PUs g ợc rộng rãi trong xử lý song s r song. GPUs đ được sử dụng để giải quyết nhiều vấn đề phức tạp tro mô hình hóa và mô t ề ong h phỏng như: mô phỏng khí hậu, dịch bệnh,… p ô Lương Hoàng Hướ L ớng, Nguyễn Hải Thanh, Huỳnh X i Xuân Hiệp 73 Hình 2. Lưu đồ xử lý của CUDA CUDA cung cấp một tập hợp các t viện mở rộ hỗ trợ lập trình viên tro việc phát t t thư ộng p ong triển các thuật toán song t song. Cả CPU và GPU đều tham gia vào quá trình tính toán. Các tín toàn tuần tự sẽ được thực thi trên CPU trong khi s h nh ự c U, các tính toán song song sẽ d GPU xử lý với bộ nhớ riê biệt. c do êng 3. UDA giao tiếp với bộ cấp ph bộ nhớ hát Hình 3 GPU và CU ẢI ỐC Đ GRAPH DỰA TRÊN CUD A DA III. CẢ THIỆN TỐ ĐỘ TÌM KIẾM CỦA MÔ HÌNH ĐỒ THỊ BT-G A. Thuật toán tìm kiếm k-l A n láng giềng gần nhất của mô hình đồ thị BT-Graph dự trên CUDA ựa A Tìm kiế k-láng giề gần nhất trên mô hình đồ thị BT-Gr ếm ềng raph (Search b based on BT-Graph, viết tắt là BTS) [11] được thể hiện như là ph hương pháp tì kiếm k vị trí địa lý gần nhất được áp d ìm t n dụng trên hệ t thống mạng các bẫy đèn tự động tại mộ không gian đ lý xác địn Với V là tậ hợp các vị trí địa lý (bẫy đèn), Q chứa các điểm láng giềng của ự ột địa nh. ập t g tr vấn q tron V, k là số đ ruy ng điểm gần nhất cần tìm. Quá trình tìm kiếm được bắt đầ từ nút gốc, trong suốt qu trình tìm t á m ầu uá kiếm giải thuậ sẽ tính toán lại Q. Tại mỗ nút B đang xét, giải thuậ thực hiện m trong ba trư k ật ỗi ật một rường hợp, cuối cùng trả nhất của truy vấn q. Trường hợp một nếu khoảng cách từ điểm truy vấn q đến về Q chứa k vị trí có cùng đ v ị điều kiện gần n g u h y nút đang xét B lớn hơn D, b qua B và trả kết quả là Q. Trường hợp hai nếu B là n lá, duyệt q tất cả các điểm x ∈ B n bỏ ả nút qua đ và cập nhật lại Q. Trường h ba nếu B l m ...