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



Bối cảnh thực tếTạp chí khoa học, ĐH Huế, tập 74B, Số 5, (2012), 81-92

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 , đò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 . 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
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(n2). 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

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 Lvk = +∞ 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
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.

Song song hóa thuật toánAlistair K Phipps,  Parallel algorithms for geometric shortest path problems, Master of Science Computer Science School of Informatics University of Edinburgh, 2004.

Lưu đồ thuật toán

Thực nghiệm thuật toán
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ý (P0, P1), trong đó: P0 là bộ xử lý chính và P1 là bộ xử lý phụ.

Kết quả trên BXL P0

Kết quả trên BXL P1

Tham khảo

Lý thuyết đồ thị