Bài toán tìm đường đi ngắn nhất là bài toán đã ra đời từ lâu. Vấn đề đặt ra là có quá nhiều điểm đến, nhiều đường đi giữa các tỉnh thành nhưng muốn biết nhanh chóng kết quả con đường từ điểm này đến điểm khác là ngắn nhất, ít chi phí nhất, thì chương trình chạy tuần tự không đáp ứng được về mặt thời gian thực hiện, thay vào đó với chương trình chạy song song thì khả năng tính toán là nhanh hơn so với chương trình tuần tự với tập dữ liệu lớn. Đề tài “Song song hóa thuật toán tìm đường đi ngắn nhất Floyd với CUDA” của tác giả Bùi Thị Thu Hiền đã làm rõ những vấn đề trên.

 

Đề tài đã trình bày cơ sở lý thuyết về tính toán song song, thuật toán song song tìm đường đi ngắn nhất được triển khai trên môi trường CPU-GPU, nhằm giải quyết bài toán sao cho thời gian hoàn thành là nhanh nhất. Các thuật toán song song được xây dựng dựa trên cơ sở các thuật toán tuần tự tìm đường đi ngắn nhất. Bước đầu thử nghiệm, so sánh tốc độ thực hiện của thuật toán tuần tự và thuật toán song song để giải quyết bài toán tìm đường đi ngắn nhất với độ lớn dữ liệu khác nhau đã cho ra một số kết quả khác nhau. Khi tập dữ liệu với số lượng đỉnh ít khoảng vài trăm đỉnh trở xuống thì thuật toán tuần tự thực hiện nhanh hơn, nhưng tập dữ liệu với số lượng đỉnh lớn vài nghìn đỉnh trở lên thì thuật toán song song thực hiện nhanh hơn.

 

Thuật toán tìm đường đi tuần tự đã được phân tách ra thành những phần có thể song song hóa và thực hiện song song hóa bằng CUDA. Việc phân chia dữ liệu cho mỗi luồng (threads) thực hiện một công việc nhất định đã làm cho bài toán song song CUDA trở nên nhanh hơn so với bài toán chạy tuần tự.

 

Trong thời gian tới, để phát triển đề tài, cần mở rộng thêm việc cho phép chương trình thực hiện chạy với dữ liệu lớn cỡ vài triệu đỉnh. Bên cạnh đó, chương trình cũng có thể được viết bằng CUDA.net.