Song song hóa thuật toán Dijkstra trên đồ thị

Bối cảnh thực tế^[1]^[2]

Bài toán tìm đường đi ngắn nhất giữa hai đỉnh của đồ thị liên thông có nhiều ứng dụng thực tế như:

Bài toán chọn hành trình tiết kiệm nhất(theo tiêu chuẩn khoảng cách, thời gian hoặc chi phí) trên mạng giao thông.
Bài toán chọn phương pháp tiết kiệm nhất để đưa một hệ thống động lực từ trạng thái xuất phát đến trạng thái đích
Bài toán lập lịch thi công các công đoạn trong một công trình thi công lớn
Bài toán lựa chọn đường truyền tin chi phí nhỏ nhất trong mạng thông tin.
...

Bài toán trở nên phức tạp khi số lượng đối tượng cần xét duyệt tăng lên hàng triệu lần ^[3], đòi hỏi khối lượng tính toán lớn, độ chính xác cao trong thời gian thực như dự báo thời tiết, xử lý thông tin gen, điều khiển tàu vũ trụ, điều khiển lò phản ứng hạt nhân,...

Với những bài toán dạng này, việc tính toán xử lý chỉ trên một bộ vi xử lý hoặc trên một máy tính không thể đáp ứng được yêu cầu đặt ra ^[4]. Vì vậy, nhu cầu thực hiện tính toán song song để có thể tính toán, giải quết một vấn đề nào đó cùng lúc tại nhiều máy tính khác nhau trở nên cấp thiết. Do đó, việc ứng dụng công nghệ tính toán song song để tăng tốc thời gian xử lý đã được nhiều nhà khoa học nghiên cứu.

Thuật toán khảo sát^[1]

Bài toán tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh là một trong số các bài toán tối ưu trên đồ thị từ bài toán thực tế trên. Được nhà khoa học máy tính Hà Lan Edsger Dijkstra đề xuất và giải quyết, gọi là thuật toán Dijkstra.

Thuật toán có độ phức tạp là O(n²)^[5]. Do độ phức tạp tính toán cao, việc giải bài toán này với tính chất tuần tự gặp phải bất lợi lớn về thời gian thực hiện chương trình, tốc độ xử lý, khả năng lưu trữ,... đặc biệt là trên đồ thị có hàng ngàn đỉnh mà thời gian chạy phải được rút gọn thì thuật toán tuần tự không thực hiện được.

Điều này đặt ra yêu cầu phải chia đồ thị cho nhiều bộ xử lý tham gia tính toán đồng thời, điều đó có nghĩa là phải cải tiến thuật toán từ tuần tự nghiên cứu tìm ra các tiến trình cần xử lý song song trên đa bộ xử lý để tăng tốc độ và hiệu quả của giải thuật.

Nội dung thuật toán^[1]

Thuật toán tìm đường đi ngắn nhất từ đỉnh i đến đỉnh j

Xét đồ thị G(V,E) với các cạnh có trọng số không âm.

Dữ liệu nhập: Cho thuật toán là ma trận trọng số L với quy ước L_vk = +∞ nếu không có cạnh nối từ đỉnh v đến đỉnh k và hai đỉnh i, j cho trước.
Dữ liệu xuất: Đường đi ngắn nhất từ i đến j.

Thực nghiệm thuật toán^[2]

Cho đồ thị được biểu diễn như sau, sau khi thuật toán thực hiện xong thì kết quả được ghi nhớ lên các nhãn đỉnh tương ứng.

Ghi nhớ kết quả tính được trên đồ thị với thuật toán Dijkstra tuần tự.

Song song hóa thuật toán^[1]^[6]

Lưu đồ thuật toán^[1]

Tập tin:Luudo-Dijkstra-SongSong-Client.jpg

Lưu đồ thuật toán Dijkstra song song - Client

Tập tin:Luudo-Dijkstra-SongSong-Server.jpg

Lưu đồ thuật toán Dijkstra song song - Server

Thực nghiệm thuật toán^[2]

Tìm đường đi ngắn nhất từ đỉnh nguồn i=1 đến tất cả các đỉnh theo thuật toán song song trên đồ thị (n=12 đỉnh) dưới đây cho m=2 bộ xử lý (P₀, P₁), trong đó: P₀ là bộ xử lý chính và P₁ là bộ xử lý phụ.

Kết quả trên BXL P₀

Tập tin:Vd-Dijkstra-songsong.jpg

Đồ thị ghi nhớ trên bộ xử lý chính (P₀)

Kết quả trên BXL P₁

Tham khảo

^ ^a ^b ^c ^d ^e Tuyển tập báo cáo Hội nghị sinh viên nghiên cứu khoa học, lần 8 Đại Học Đà Nẵng, 2012 Lưu trữ 2014-03-27 tại Wayback Machine
^ ^a ^b ^c Tạp chí khoa học, ĐH Huế, tập 74B, Số 5, (2012), 81-92
^ M.Sasikumar, Dinesh Shikhare, P.Ravi Prakash. Introduction to Parallel Computing. Chapter 1, Why Parallel Processing, page 2, ISBN 81-203-1619-3
^ Introduction to Parallel Computing Why Use Parallel Computing?^{[liên kết hỏng]}
^ CSE633 Course Project, An Implementation of Parallelizing Dijkstra’s Algorithm, Parallel Dijkstra’s algorithm
^ Alistair K Phipps, Parallel algorithms for geometric shortest path problems, Master of Science Computer Science School of Informatics University of Edinburgh, 2004.