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

Bối cảnh thực tế

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. 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=

Lưu đồ thuật toán

khung|giữa|Lưu đồ thuật toán Dijkstra song song - Client khung|giữa|Lưu đồ thuật toán Dijkstra song song - Server

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ý (P₀, P₁), trong đó: P₀ là bộ xử lý chính và P₁ là bộ xử lý phụ.

Kết quả trên BXL P₀

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

Kết quả trên BXL P₁

khung|giữa|Đồ thị ghi nhớ trên bộ xử lý chính (P₁)