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<br /> K<br /> 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<br /> ứu<br /> ệ<br /> );<br /> 9-10/7/2015<br /> <br /> CẢI T<br /> THIỆN TỐ ĐỘ T KIẾM CỦA MÔ HÌNH Đ THỊ B T-GRAP<br /> ỐC<br /> TÌM<br /> M<br /> Ô<br /> ĐỒ<br /> PH<br /> DỰA TRÊN NỀN TẢN CUDA<br /> A<br /> NG<br /> A<br /> Lư<br /> ương Hoàng Hướng1, Ngu<br /> uyễn Hải Tha 2, Huỳnh X<br /> anh<br /> Xuân Hiệp3<br /> 1<br /> Trung tâm Công ngh phần mềm, Đại học Cần Thơ<br /> hệ<br /> 2<br /> Vụ K<br /> Khoa học, Công nghệ và Môi trường, Bộ Giáo dục và Đ tạo Việt N<br /> g<br /> G<br /> Đào<br /> Nam<br /> 3<br /> Khoa Công nghệ thông tin và Truyền thông, Nhóm nghiên cứu li ngành DR<br /> g<br /> n<br /> m<br /> iên<br /> REAM-CTU/IR Đại học Cần Thơ<br /> RD,<br /> C<br /> lhhuong<br /> g@ctu.edu.vn, nhthanh@{moet.gov.vn, mo<br /> oet.edu.vn}, h<br /> hxhiep@ctu.ed<br /> du.vn<br /> 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<br /> ẮT<br /> h<br /> l<br /> )<br /> nh<br /> xây<br /> rên<br /> balltree, giúp mô hình hóa hệ t<br /> b<br /> 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<br /> ám<br /> đ<br /> m<br /> Khi<br /> t<br /> 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<br /> v<br /> địa<br /> iện<br /> k<br /> ình<br /> Graph. Trong bài viết này,<br /> b<br /> 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<br /> c<br /> ất<br /> ếp<br /> ng<br /> n<br /> ếm<br /> ph<br /> g<br /> song hóa thuật toán tìm kiếm dựa trên nền t<br /> s<br /> tảng CUDA NV<br /> VIDIA. Các thự nghiệm được triển khai trê hai thuật toá tìm kiếm<br /> ực<br /> ợc<br /> ên<br /> án<br /> k-láng giềng gần nhất và tìm k<br /> k<br /> kiếm đường đi n<br /> 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<br /> đ<br /> h<br /> ự<br /> tì kiếm.<br /> ìm<br /> Từ khóa - CUDA, BT-G<br /> a<br /> Graph, vị trí địa lý, mạng giám sát bẫy đèn tự động, song son<br /> a<br /> m<br /> ự<br /> ng.<br /> <br /> I. GIỚI THIỆU<br /> G<br /> U<br /> BT-Gra (Graph M<br /> aph<br /> Model based on Ball Tree St<br /> n<br /> tructure) [11] là một mô hìn đồ thị được xây dựng dự trên cấu<br /> nh<br /> c<br /> ựa<br /> tr balltree [2 [11]. BT-G<br /> rúc<br /> 21]<br /> Graph không c giúp mô hình hóa hệ th<br /> chỉ<br /> h<br /> hống mạng giá sát các bẫy đèn tự động bằng cách<br /> ám<br /> y<br /> đề 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<br /> đ<br /> nh<br /> biến<br /> m<br /> ợ<br /> trí<br /> hi<br /> tốc<br /> 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<br /> v<br /> ớn<br /> ìm<br /> r<br /> p<br /> iếm của mô hình đồ thị<br /> h<br /> BT-Graph.<br /> B<br /> <br /> A)<br /> <br /> C)<br /> <br /> B)<br /> <br /> Hình 1. A) Tậ hợp điểm, B) Cấu trúc Balltr C) Mô hình đồ thị BT-Gra<br /> ập<br /> )<br /> ree,<br /> h<br /> aph<br /> <br /> Ngày n<br /> nay, việc sử d<br /> dụng Graphic Processing Units (GPUs) [28] đóng vai trò quan trọ trong xử lý các ứng<br /> U<br /> i<br /> ọng<br /> l<br /> dụng đòi hỏi c phải xử lý song song. N<br /> d<br /> cần<br /> ý<br /> 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<br /> s<br /> t<br /> mà<br /> độ 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<br /> đ<br /> ủa<br /> ồ<br /> hiều<br /> ứu<br /> ất<br /> và xử lý tuần t trên CPU [1 [2] [3] [7] [10].<br /> v<br /> tự<br /> 1]<br /> Trong b viết này, c<br /> bài<br /> chúng tôi đề x<br /> 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<br /> ng<br /> ới<br /> cải<br /> độ<br /> ủa<br /> đồ 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]<br /> đ<br /> aph<br /> ơng<br /> g<br /> huật<br /> k<br /> n<br /> PUs<br /> [15] [16] [26]. Các thực ngh<br /> .<br /> 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]<br /> iển<br /> m<br /> ng<br /> [23] [24] [25] và tìm kiếm đ<br /> đường đi ngắn nhất [5] [9] [17] [18] [27] [29].<br /> n<br /> Bài viết được chia th<br /> hành năm phần Phần thứ nh giới thiệu về mô hình B<br /> n.<br /> hất<br /> BT-Graph và tì kiếm vị trí địa lý dựa<br /> ìm<br /> tr mô hình. Phần thứ hai trình bày về CUDA NVID<br /> rên<br /> DIA. Phần thứ ba trình bày về cải thiện t độ tìm kiế của mô<br /> ứ<br /> tốc<br /> ếm<br /> hình đồ thị BT<br /> h<br /> T-Graph dựa tr nền tảng C<br /> rên<br /> 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<br /> c<br /> ần<br /> l<br /> lu<br /> uận.<br /> A<br /> II. CUDA NVIDIA<br /> 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<br /> m<br /> ng<br /> ởi<br /> 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<br /> N<br /> DA<br /> khả<br /> hợp<br /> n<br /> ng<br /> mềm. CUDA có khả năng tăn đáng kể<br /> ó<br /> ng<br /> hiệu suất tính t<br /> h<br /> toán bằng cách khai thác sứ mạnh của đơn vị xử lý đồ họa – Graph Processing Units (GPUs)<br /> ức<br /> đ<br /> ồ<br /> his<br /> ).<br /> 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.<br /> [6]<br /> hỗ<br /> g<br /> n<br /> s<br /> đến<br /> m<br /> n<br /> 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<br /> V<br /> lớn<br /> PUs<br /> g<br /> ợc<br /> rộng rãi trong xử lý song s<br /> r<br /> song. GPUs đ<br /> được sử dụng để giải quyết nhiều vấn đề phức tạp tro mô hình hóa và mô<br /> t<br /> ề<br /> ong<br /> h<br /> phỏng như: mô phỏng khí hậu, dịch bệnh,…<br /> p<br /> ô<br /> <br /> Lương Hoàng Hướ<br /> L<br /> ớng, Nguyễn Hải Thanh, Huỳnh X<br /> i<br /> Xuân Hiệp<br /> <br /> 73<br /> <br /> Hình 2. Lưu đồ xử lý của CUDA<br /> 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<br /> t<br /> thư<br /> ộng<br /> p<br /> ong<br /> triển các thuật toán song<br /> t<br /> 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<br /> s<br /> h<br /> nh<br /> ự<br /> c<br /> U,<br /> các tính toán song song sẽ d GPU xử lý với bộ nhớ riê biệt.<br /> c<br /> do<br /> êng<br /> <br /> 3.<br /> UDA giao tiếp với bộ cấp ph bộ nhớ<br /> hát<br /> Hình 3 GPU và CU<br /> ẢI<br /> ỐC<br /> Đ<br /> GRAPH DỰA TRÊN CUD<br /> A<br /> DA<br /> III. CẢ THIỆN TỐ ĐỘ TÌM KIẾM CỦA MÔ HÌNH ĐỒ THỊ BT-G<br /> A. Thuật toán tìm kiếm k-l<br /> A<br /> n<br /> láng giềng gần nhất của mô hình đồ thị BT-Graph dự trên CUDA<br /> ựa<br /> A<br /> Tìm kiế k-láng giề gần nhất trên mô hình đồ thị BT-Gr<br /> ếm<br /> ềng<br /> raph (Search b<br /> based on BT-Graph, viết tắt là BTS)<br /> [11] được thể hiện như là ph<br /> hương pháp tì kiếm k vị trí địa lý gần nhất được áp d<br /> ìm<br /> t<br /> n<br /> dụng trên hệ t<br /> thống mạng các bẫy đèn<br /> 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<br /> ự<br /> ột<br /> địa<br /> nh.<br /> ập<br /> t<br /> g<br /> tr vấn q tron V, k là số đ<br /> ruy<br /> ng<br /> đ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<br /> t<br /> á<br /> m<br /> ầu<br /> uá<br /> 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ư<br /> k<br /> ật<br /> ỗi<br /> ật<br /> một<br /> rường hợp, cuối cùng trả<br /> 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<br /> về Q chứa k vị trí có cùng đ<br /> v<br /> ị<br /> điều kiện gần n<br /> g<br /> u<br /> h<br /> y<br /> 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<br /> n<br /> bỏ<br /> ả<br /> nút<br /> qua<br /> đ<br /> và cập nhật lại Q. Trường h ba nếu B l một nút trong, gọi đệ quy thuật toán tì kiếm cho h nút con củ B là con<br /> v<br /> i<br /> hợp<br /> là<br /> y<br /> ìm<br /> hai<br /> ủa<br /> tr và con phả Chi tiết giả thuật được m tả như tron [11].<br /> rái<br /> ải.<br /> ải<br /> mô<br /> ng<br /> Tuy nh<br /> hiên, khi số lượ vị trí địa lý lớn và khô gian tìm kiếm mở rộng thì cần cải th<br /> ợng<br /> ông<br /> k<br /> hiện tốc độ tìm kiếm của<br /> m<br /> BTS. Ngoài ra khi số lượng điểm truy vấ lớn cũng cần phải cải th<br /> B<br /> a<br /> g<br /> ấn<br /> hiện tốc độ tìm kiếm. Vì vậ chúng tôi đề xuất hai<br /> m<br /> ậy,<br /> đ<br /> tr<br /> rường hợp giả quyết bài to tìm kiếm k<br /> ải<br /> oán<br /> k-láng giềng gần nhất bằng phương pháp song song hóa<br /> p<br /> a.<br /> Trường hợp một chú tôi đề xuấ sử dụng thu toán vét cạ áp dụng cho tìm kiếm kg<br /> úng<br /> ất<br /> uật<br /> ạn<br /> o<br /> -láng giềng dự trên nền<br /> ựa<br /> tảng CUDA (g tắt là BF-k<br /> gọi<br /> kNNCUDA) [2] [3] [8] [10 [19] [23] [2 và được c đặt với hai module chín Module<br /> 0]<br /> 25]<br /> cài<br /> i<br /> nh.<br /> một thực hiện tính toán son song khoản cách từ điểm truy vấn đế tất cả các đ<br /> m<br /> ng<br /> ng<br /> m<br /> ến<br /> điểm trong tập dữ liệu – Thực hiện tại<br /> p<br /> GPU. Module hai thực hiện sắp xếp các k<br /> G<br /> khoảng cách tí toán được theo thứ tự tă dần và chọ ra k-khoảng cách nhỏ<br /> ính<br /> ăng<br /> ọn<br /> nhất (gần nhất – Thực hiện tại CPU.<br /> n<br /> t)<br /> <br /> 74<br /> 7<br /> <br /> CẢI THIỆN TỐC ĐỘ TÌM KIẾM CỦA MÔ HÌNH ĐỒ THỊ B<br /> N<br /> Ô<br /> BT-GRAPH DỰA TRÊN NỀN TẢ<br /> ỰA<br /> ẢNG CUDA<br /> <br /> Giải th<br /> huật 1: BF-kN<br /> NNCUDA<br /> //Xử lý tại CPU<br /> 1.<br /> <br /> u<br /> d<br /> Nạp dữ liệu vào bộ nhớ dùng chung<br /> <br /> 2.<br /> <br /> Thiết lập ch số k<br /> hỉ<br /> <br /> 3.<br /> <br /> Sao chép dữ liệu từ CPU vào GPU<br /> ữ<br /> U<br /> //Xử lý tại G<br /> GPU<br /> <br /> 4.<br /> <br /> Tính toán k<br /> khoảng cách từ điểm truy vấ q đến tất cả điểm v ∈ V<br /> ừ<br /> ấn<br /> ả<br /> <br /> 5.<br /> <br /> Sao chép dữ liệu từ GPU về CPU<br /> ữ<br /> U<br /> //Xử lý tại C<br /> CPU<br /> <br /> 6.<br /> <br /> Sắp xếp các khoảng cách tính được the thứ tự tăng dần<br /> c<br /> h<br /> eo<br /> <br /> 7.<br /> <br /> Lấy ‘k’ kho<br /> oảng cách đầu tiên thể hiện cho các điểm gần nhất<br /> u<br /> <br /> 8.<br /> <br /> Giải phóng bộ nhớ CUDA<br /> g<br /> <br /> Trường hợp hai chún tôi đề xuất với mỗi lần thực hiện BTS trên một điể truy vấn th sẽ do một lu<br /> g<br /> ng<br /> t<br /> t<br /> S<br /> ểm<br /> hì<br /> uồng trong<br /> CUDA xử lý [ Phương ph này chúng tôi gọi là BT<br /> C<br /> [4].<br /> háp<br /> g<br /> TSCUDA. Ý tưởng thuật to được thể h<br /> t<br /> oán<br /> hiện trong hình 4 và giải<br /> th 2.<br /> huật<br /> <br /> Hình 4. BTSCUD với mỗi đi truy vấn sẽ do một luồn trong CUD A xử lý<br /> DA<br /> iểm<br /> ng<br /> 2:<br /> A<br /> Giải thuật 2 BTSCUDA<br /> /<br /> //Xử lý tại CP<br /> PU<br /> 1. T cấu trúc c T<br /> Tạo<br /> cây<br /> 2. T mảng chứ các điểm tru vấn qArrra<br /> Tạo<br /> ứa<br /> uy<br /> ay<br /> 3.<br /> <br /> S chép cây T và mảng qA<br /> Sao<br /> Arrray từ CPU vào GPU<br /> U<br /> /<br /> //Xử lý tại GP<br /> PU<br /> <br /> 4.<br /> <br /> V mỗi điểm truy vấn<br /> Với<br /> m<br /> <br /> 5.<br /> 6.<br /> 7.<br /> <br /> T kiếm trên cây T với ph<br /> Tìm<br /> n<br /> hương pháp BF<br /> FS<br /> T kết quả là danh sách k-l<br /> Trả<br /> à<br /> láng giềng gần nhất của mỗ điểm truy vấ<br /> n<br /> ỗi<br /> ấn<br /> S chép kết q tất cả danh sách k-láng giềng tìm đượ từ GPU về CPU<br /> Sao<br /> quả<br /> h<br /> ợc<br /> <br /> B. Thuật toán tìm kiếm đư<br /> B<br /> n<br /> ường đi ngắn n<br /> nhất của mô hình đồ thị BT-Graph dựa trên CUDA<br /> h<br /> Thuật t<br /> toán Dijkstra [ [26] là thu toán tìm kiếm đường đi ngắn nhất bằ phương p<br /> [5]<br /> uật<br /> k<br /> i<br /> ằng<br /> pháp duyệt qua đồ thị và<br /> tìm kiếm đườn đi sao cho c phí duyệt t đỉnh bắt đầu đến đỉnh kết thúc là nhỏ n<br /> ng<br /> chi<br /> từ<br /> t<br /> nhất. Thuật to án Dijkstra tuần tự được<br /> xây dựng trên cơ sở gán cho các đỉnh của đồ thị các nh tạm thời. Các nhãn này được thay đổ theo mỗi bước lặp tính<br /> x<br /> o<br /> a<br /> hãn<br /> C<br /> ổi<br /> toán. Có hai n<br /> nhãn là cố định và tạm thời. Ở mỗi bước lặp sẽ thay đổi một nhãn t<br /> h<br /> đ<br /> tạm thời thành nhãn cố định. Một nút<br /> h<br /> được đánh dấu là nhãn cố đị sẽ cho kết quả là đường đi ngắn nhất từ đỉnh tới nú đó. Thuật to bao gồm ba bước cơ<br /> đ<br /> u<br /> ịnh<br /> t<br /> g<br /> út<br /> oán<br /> b<br /> bản: khởi tạo (<br /> b<br /> (Initialization) tìm giá trị nh nhất (Extra<br /> ),<br /> hỏ<br /> act_Min) và cậ nhật giá trị (UpdateCost)<br /> ập<br /> ị<br /> ).<br /> <br /> Lương Hoàng Hướ<br /> L<br /> ớng, Nguyễn Hải Thanh, Huỳnh X<br /> i<br /> Xuân Hiệp<br /> <br /> 75<br /> <br /> Giải thuậ 3: Thuật toán Dijkstra<br /> ật<br /> //Initial<br /> 1. foreach v ∈ V do<br /> v]<br /> d[v ← ∞<br /> 2.<br /> 3.<br /> <br /> end<br /> <br /> 4.<br /> <br /> d[S] ← 0<br /> <br /> 5.<br /> <br /> Q←V<br /> <br /> 6.<br /> 7.<br /> 8.<br /> 9.<br /> 10.<br /> 11.<br /> 12.<br /> 13.<br /> 14.<br /> 15.<br /> <br /> while Q ≠ ∅ do<br /> //Extract_<br /> _Min<br /> u ← { v: v ∈ Q ^ ∀w ∈ Q, d[v] ≤ d[w }<br /> w]<br /> if (d[u] = ∞) then<br /> break;<br /> Remove u from Q<br /> //UpdateC<br /> Cost<br /> foreach (u v) ∈ V do<br /> u,<br /> if ((d[u] + c(u, v)) < d[v]) then<br /> d<br /> d[v] ← d[u] + c(u, v)<br /> ,<br /> end<br /> end<br /> <br /> Để song song hóa th<br /> huật toán Dijk<br /> kstra, chúng tô đề xuất mỗi cạnh của đồ thị BT-Grap sẽ tương ứn với một<br /> ôi<br /> ồ<br /> ph<br /> ng<br /> lu<br /> uồng trong CU<br /> UDA. Quá trì xử lý song song được th hiện như lư đồ ở hình 5 Trong đó, h bước Extra<br /> ình<br /> g<br /> hể<br /> ưu<br /> 5.<br /> hai<br /> act_Min và<br /> UpdateCost đư cài đặt bằn CUDA.<br /> U<br /> ược<br /> ng<br /> <br /> Hình 5. Lưu đ song song t<br /> H<br /> đồ<br /> thuật toán Dijk<br /> kstra trên mô hình đồ thị BT<br /> h<br /> T-Graph sử dụ CUDA<br /> ụng<br /> ình<br /> Quá trìn cấp phát bộ nhớ GPUs c các cạnh của đồ thị BT-Graph được th hiện như hì 6.<br /> nh<br /> ộ<br /> cho<br /> c<br /> hể<br /> <br /> Hình 6. Cấp phát bộ nhớ lưu trữ cho mô hình đồ thị B<br /> ô<br /> BT-Graph<br /> <br /> 76<br /> <br /> 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<br /> <br /> Thuật toán Dijkstra cài đặt với CUDA (gọi tắt là DijkstraCUDA) được thể hiện như sau:<br /> Giải thuật 4: Thuật toán DijkstraCUDA<br /> Bước 1:<br /> 1.<br /> Khởi tạo ma trận trọng số, điểm bắt đầu và kết thúc<br /> Bước 2:<br /> 2.<br /> Cấp phát bộ nhớ trong CUDA tương ứng với số cạnh của mô hình đồ thị BT-Graph<br /> Bước 3:<br /> 3.<br /> Sao chép dữ liệu từ CPU sang GPU<br /> Bước 4:<br /> 4.<br /> Tìm kiếm đỉnh u tự do sao cho chi phí đi từ đỉnh xuất phát S đến u là nhỏ nhất<br /> 5.<br /> Nếu không tìm thấy u thỏa điều kiện trên thì thoát:<br /> + Hoặc là tìm thấy đường đi.<br /> + Hoặc không tìm thấy đường đi.<br /> 6.<br /> Nếu tìm thấy đỉnh u thỏa điều kiện, dùng đỉnh u xét các đỉnh tự do khác.<br /> 7.<br /> Dùng CUDA để cấp các luồng cho việc thực hiện tính toán giữa đỉnh u và các<br /> đỉnh còn lại.<br /> Bước 5:<br /> 8.<br /> Sao chép dữ liệu từ GPU về CPU<br /> Bước 6:<br /> 9.<br /> Giải phóng CUDA<br /> IV. THỰC NGHIỆM<br /> Trong phần thực nghiệm này chúng tôi tiến hành so sánh tốc độ tìm kiếm trên mô hình đồ thị BT-Graph giữa<br /> thuật toán tuần tự trên CPU và thuật toán song song trên CUDA. Máy tính được sử dụng cho phần thực nghiệm này là<br /> Desktop (Intel Core i3-3220 3.3 GHz, bộ nhớ 4GB DDR3, card đồ họa NVIDIA GeForce GTX 660 với bộ nhớ 2GB<br /> GDDR5) chạy hệ điều hành Ubuntu 14.04 64 bits.<br /> A. Dữ liệu thực nghiệm<br /> Dữ liệu sử dụng cho thực nghiệm được chia làm hai loại, loại một dùng cho thực nghiệm tìm kiếm k-láng giềng<br /> và loại hai dùng cho tìm kiếm đường đi ngắn nhất Dijkstra. Các dữ liệu được sinh ra ngẫu nhiên từ chương trình thực<br /> nghiệm.<br /> Cấu trúc thông tin của dữ liệu loại một bao gồm hai danh sách. Danh sách thứ nhất chứa các điểm dữ liệu ban<br /> đầu gồm ba cột và số dòng là tùy chọn. Mỗi dòng mô tả thông tin một điểm dữ liệu. Cột một chứa tên của điểm dữ liệu,<br /> cột hai chứa giá trị x trong không gian hai chiều và cột ba chứa giá trị y trong không gian hai chiều. Danh sách thứ hai<br /> chứa các điểm truy vấn cũng gồm ba cột và số dòng là tùy chọn. Mỗi dòng mô tả thông tin một điểm truy vấn. Cột một<br /> chứa tên của điểm dữ liệu, cột hai và cột ba chứa giá trị x và y trong không gian hai chiều.<br /> Cấu trúc thông tin của dữ liệu loại hai dùng để mô tả số đỉnh, cạnh và thông tin các cạnh của mô hình đồ thị BTGraph. Dòng thứ nhất chứa hai giá trị, số đỉnh và số cạnh của mô hình đồ thị BT-Graph. Các dòng còn lại, mỗi dòng<br /> chứa ba giá trị - đỉnh đầu, đỉnh cuối và trọng số của cạnh được tạo bởi hai đỉnh đó.<br /> B. Công cụ thực nghiệm và phương pháp thực nghiệm<br /> Trong thực nghiệm này, chúng tôi đã xây dựng một công cụ dựa trên nền tảng NetGen [14] với tên gọi là: GLS<br /> (Geographical Location Search) [11], cho phép xây dựng mô hình đồ thị BT-Graph [28] dựa trên tập dữ liệu cho trước.<br /> Ngoài ra, chương trình còn cho phép tính toán, thực thi chương trình CUDA thông qua thư viện DLL&C của Smalltalk<br /> và so sánh thời gian thực thi của các thuật toán.<br /> Trong cùng một thuật toán và một tập dữ liệu, chúng tôi tiến hành thực thi chương trình nhiều lần và lấy kết quả<br /> trung bình về thời gian thực thi của thuật toán đó nhằm mục đích để thu được kết quả tương đối chính xác.<br /> C. So sánh hiệu suất của thuật toán tìm kiếm k-láng giềng<br /> Yêu cầu đặt ra cho phần thực nghiệm này là so sánh được tốc độ tìm kiếm của thuật toán kNN truyền thống [11]<br /> trên mô hình đồ thị BT-Graph và thuật toán kNN dựa trên CUDA [26].<br /> Thực nghiệm được tiến hành trên tập dữ liệu được mô tả như trong phần dữ liệu thực nghiệm. Chúng tôi tiến<br /> hành thực thi chương trình 10 lần trên mỗi thuật toán và lấy giá trị trung bình theo thời gian thực thi. Kết quả thực<br /> nghiệm của chương trình sau khi đã lấy trung bình được thể hiện như trong bảng 1. Trong đó, N là số lượng điểm dữ<br /> liệu ban đầu, Q là số lượng điểm truy vấn.<br /> <br />