Thuật toán song song cho một số bài toán trên đồ thị

THUẬT TOÁN SONG SONG CHO MỘT SỐ BÀI TOÁN
TRÊN ĐỒ THỊ
Nội dung
Đại cương về tính toán song song
Một số thuật toán song song cơ bản trên đồ thị
Thuật toán song song giải bài toán K-Median
Thiết kế chương trình


Đại cương về tính toán song song
Một số khái niệm và thuật ngữ
Phân loại các kiến trúc song song
Đánh giá độ phức tạp của thuật toán song song
Một số mẫu thiết kế thuật toán song song


Một số khái niệm và thuật ngữ
Tính toán song song hay xử lý song song : là quá trình xử lý thông tin trong đó nhấn mạnh việc nhiều đơn vị dữ liệu được xử lý đồng thời bởi một hay nhiều bộ xử lý để giải quyết một bài toán
Tốc độ


Hiệu quả (Efficient) của thuật toán song song được tính bằng : Tốc độ / số bộ xử lý tham gia tính toán
Giá (cost) của một quá trình tính toán trên hệ thống song song được tính như sau : Giá = Độ phức tạp tính toán  Số lượng bộ xử lý tham gia tính toán
Phân loại các kiến trúc song song
SISD (single instruction stream, single data stream)
MISD (multiple instruction stream, single data stream)
SIMD (single instruction stream, multiple data stream)
EREW (Exclusive Read, Exclusive Write)
CREW (Concurent Read Exclusive Write)
ERCW (Exclusive Read Concurent Write)
CRCW (Concurent Read Concurent Write)
MIMD (multiple instruction stream, multiple data stream)
Hệ đa xử lý với bộ nhớ phân tán
Hệ đa xử lý dùng chung bộ nhớ
Hệ đa xử lý với bộ nhớ dùng chung phân tán
Đánh giá độ phức tạp
Song song giới hạn và song song không giới hạn
Các kỹ thuật cho việc nâng cao hiệu quả của thuật toán song song
Giảm số lượng bộ xử lý
Giảm độ phức tạp thuật toán
Độ phức tạp của bài toán
Một số mẫu thiết kế thuật toán song song
Mẫu cây nhị phân
Phát triển bởi nhân đôi
Chia để trị
Phân chia
Một số thuật toán song song cơ bản trên đồ thị
Thuật toán trên đồ thị không có trọng số
Thuật toán trên cây : Duyệt cây có thứ tự tổng quát, xác định tổ tiên chung gần nhất, tâm và median của cây.
Tìm kiếm trên đồ thị : Tìm kiếm theo chiều sâu, tìm kiếm theo chiều rộng.
Thành phần liên thông và một số bài toán liên quan : Tìm thành phần liên thông, hai liên thông trong đồ thị, tập chu trình cơ bản, tâm và median của đồ thị,..
Thuật toán trên đồ thị có trọng số
Cây khung tối thiểu
Đường đi ngắn nhất đơn nguồn
Duyệt cây có thứ tự tổng quát
Tâm và median của cây
Chỉ số ngăn cách :
Chỉ số lan truyền :

c là tâm của cây khi s(c) là tối thiểu
m là median của cây khi t(m) là tối thiểu
Ý tưởng : sử dụng thuật toán song song tìm tổ tiên chung gần nhất NCA(i, j).

d(i,j) = level(i) + level(j) - 2  level(NCA(i,j))

Tìm kiếm theo chiều rộng
Cây khung tối thiểu
Ý tưởng : Song song hoá thuật toán của Prim-Dijkstra
Thực hiện :
+ Giả sử có K bộ xử lý p1, p2, …, pK
+ Phân một tập con nút cho mỗi pi
+ Tại mỗi bước tìm nút gần cây nhất một cách song song => K nút => chọn nút gần nhất và quảng bá tới các bộ xử lý




Thuật toán song song giải bài toán k-median trên đồ thị
Giới thiệu bài toán

Thuật toán nhánh cận tuần tự

Thuật toán nhánh cận song song
Giới thiệu bài toán
Khởi nguồn từ thế kỷ 17, Fermat đưa ra một câu hỏi : Cho một tam giác (với 3 đỉnh trên mặt phẳng), hãy tìm một điểm ( median) trong mặt phẳng sao cho tối thiểu hóa tổng khoảng cách từ nó tới các đỉnh.
Đầu thế kỷ 20, Alfred Weber tổng quát hóa : đưa thêm trọng số vào đỉnh, số đỉnh n  3, số median k  1
Đầu năm 1960, Hakimi phát triển bài toán tìm k median trên một đồ thị gồm n đỉnh. Phân ra làm 3 lớp bài toán : K-median đơn thuần, UFLP , QAP.
Bài toán K-median trên đồ thị tổng quát là NP-khó.


Ví dụ minh họa
Có hai vị trí để đặt trạm phục vụ. Trạm nào sẽ được đặt :



Chúng ta muốn tối thiểu hoá tổng khoảng cách từ các trạm còn lại tới hai trạm phục vụ.
Ví dụ minh họa


Làm sao để biết được vị trí tối ưu mà không phải duyệt qua tổ hợp bộ k phần tử.
Mô hình toán học
Với điều kiện
Các phương pháp đã giải quyết
Thuật toán nhánh cận
Khởi tạo : Tập hoạt động (tập các bài toán con chưa được duyệt) chứa bài toán ban đầu, giá trị kỷ lục bằng .
Lựa chọn : Lựa chọn và xoá một bài toán con khả thi từ tập hoạt động.
Phân nhánh :
Phân nhánh để sinh ra các bài toán con mới từ bài toán đang xét. Tính cận của các bài toán con mới này.
Kiểm tra các bài toán con vừa được sinh ra. Có hai trường hợp : (1) bài toán con đã được giải quyết – đi tới bước 5, (2) bài toán con chưa được giải quyết – đi tới bước 4.
Cập nhật tập hoạt động : Đưa các bài toán con có cận nhỏ hơn kỷ lục tạm thời vào tập hoạt động.
Cập nhật kỷ lục :
Nếu giá trị của bài toán con nhỏ hơn kỷ lục và khi đó nó sẽ thay thế kỷ lục. Ngược lại sẽ bị xóa
Khi cập nhật kỷ lục mới (5i) thì tất cả các bài toán con trong tập hoạt động có cận dưới lớn hơn hoặc bằng kỷ lục sẽ bị xóa
Kết thúc thuật toán : Lặp lại các bước từ 2-5 nếu tập hoạt động không rỗng. Ngược lại, thì kết thúc thuật toán và lời giải tối ưu là giá trị kỷ lục
Thuật toán nhánh cận
Khởi tạo : Tập hoạt động (tập các bài toán con chưa được duyệt) chứa bài toán ban đầu, giá trị kỷ lục bằng .
Lựa chọn : Lựa chọn và xoá một bài toán con khả thi từ tập hoạt động.
Phân nhánh :
Phân nhánh để sinh ra các bài toán con mới từ bài toán đang xét. Tính cận của các bài toán con mới này.
Kiểm tra các bài toán con vừa được sinh ra. Có hai trường hợp : (1) bài toán con đã được giải quyết – đi tới bước 5, (2) bài toán con chưa được giải quyết – đi tới bước 4.
Cập nhật tập hoạt động : Đưa các bài toán con có cận nhỏ hơn kỷ lục tạm thời vào tập hoạt động.
Cập nhật kỷ lục :
Nếu giá trị của bài toán con nhỏ hơn kỷ lục và khi đó nó sẽ thay thế kỷ lục. Ngược lại sẽ bị xóa
Khi cập nhật kỷ lục mới (5i) thì tất cả các bài toán con trong tập hoạt động có cận dưới lớn hơn hoặc bằng kỷ lục sẽ bị xóa
Kết thúc thuật toán : Lặp lại các bước từ 2-5 nếu tập hoạt động không rỗng. Ngược lại, thì kết thúc thuật toán và lời giải tối ưu là giá trị kỷ lục
Thuật toán nhánh cận giải bài toán k-median
Lựa chọn bài toán con
Lựa chọn theo độ sâu
Lựa chọn cận tốt nhất đầu tiên
Phân nhánh : Nếu bài toán con có lời giải bộ phận là a1a2…ai-1 thì nó sẽ được phân thành (n-m+i – ai-1) bài toán con với lời giải bộ phận tương ứng là (a1,a2,….,ai-1+1); ……;(a1,a2,…..,n-k+i)

Ví dụ : n = 10, k = 5; bài toán con hiện tại có lời giải bộ phận là (0, 2); các bài toán con được sinh ra có lời giải bộ phận là (0,2,3); (0,2,4); (0,2,5); (0,2,6); (0,2,7).
Tính cận
Bài toán nới lỏng lagrage


Với điều kiện

Bài toán đối ngẫu


Với điều kiện

Thuật toán nhánh cận song song
Phân loại thuật toán nhánh cận song song

Lựa chọn kiến trúc thiết kế thuật toán song song

Thiết kế mô hình thuật toán song song

Phân loại thuật toán nhánh cận song song
Song song loại 1 : Song song hóa các pha trong thuật toán tuần tự.
Song song loại 2 : Thực hiện các hoạt động trên các bài toán con một cách đồng thời.
Song song loại 3 : Một vài cây nhánh cận được xây dựng một cách song song.
Phân loại thuật toán nhánh cận song song
Song song loại 1 : Song song hóa các pha trong thuật toán tuần tự.
Song song loại 2 : Thực hiện các hoạt động trên các bài toán con một cách đồng thời.
Song song loại 3 : Một vài cây nhánh cận được xây dựng một cách song song.
Lựa chọn kiến trúc
Bộ nhớ phân tán
Bộ nhớ dùng chung
Lựa chọn kiến trúc
Bộ nhớ phân tán
Bộ nhớ dùng chung
Thiết kế mô hình thuật toán nhánh cận song song
Quản lý tập bài toán con
Lược đồ thực hiện
Xây dựng hệ thống
Quản lý tập bài toán con
Cân bằng số lượng : đảm bảo rằng không có bộ xử lý nào được nghỉ ngơi trong khi các bộ xử lý khác có một số lượng lớn nút cần ước lượng.
Giải pháp : Nếu máy rỗi thì thông báo, ngưỡng k.
Dò xét kết thúc : Khi hoàn tất quá trình tìm kiếm.
Cân bằng chất lượng : Đảm bảo các bộ xử lý đều khai thác nút có khả năng dễ dẫn tới lời giải tối ưu.
Cân bằng số lượng
Ý tưởng : Khi tập hoạt động tại một bộ xử lý trở nên rỗng, thì bộ xử lý có tập hoạt động lớn nhất sẽ gửi một phần công việc của nó tới bộ xử lý rỗng sao cho số lượng công việc trong hai bộ xử lý xấp xỉ nhau
Thực hiện : BXL có các nút , thì sẽ gửi tới BXL yêu cầu. Trong đó
Bộ xử lý có tập hoạt động lớn nhất ? => Sử dụng một “bộ giám sát” trên máy chủ.
Dò xét kết thúc và cân bằng chất lượng
Dò xét kết thúc : Khi tập bài toán con rỗng và tất cả các máy thợ đều rỗi.
Cân bằng chất lượng : Sử dụng cận dưới tốt nhất, hàm trọng số đánh giá chất lượng tập hoạt động.
Thực hiện : nếu thì tráo đổi nút giữa hai bộ xử lý.

max, min là chất lượng tập hoạt động cực đại, cực tiểu.  : dung sai chất lượng
Sơ đồ hệ thống
Thiết kế chương trình
Tổng quan hệ thống
Thuật toán nhánh cận tuần tự
Thuật toán nhánh cận song song
Dữ liệu tập trung
Dữ liệu phân tán
Kết quả thực nghiệm
Nhận xét và hướng phát triển
Tổng quan hệ thống
Thuật toán tuần tự
Lược đồ song song dữ liệu tập trung
Ý tưởng : Danh sách các bài toán con chưa được giải quyết lưu tại máy chủ, các bài toán con được rời và gửi tới các máy thợ. Mỗi máy thợ khi nhận bài toán con tiến hành phân nhánh, tính cận và lưu vào một danh sách cục bộ. Sau đó nó gửi tới máy chủ, máy chủ lúc này tiến hành nối các bài toán con nhận được tới kho dữ liệu tập trung.
Cấu trúc dữ liệu : Danh sách liên kết
Thuật toán
Trên máy chủ
Trên máy thợ
Thuật toán trên máy chủ
Thuật toán trên máy thợ
Lược đồ song song dữ liệu phân tán
Ý tưởng : Mỗi máy thợ lưu một danh sách các bài toán con cục bộ. Máy chủ chỉ gửi bài toán con đầu tiên tới một máy thợ rỗi ban đầu và sau đó không lưu trữ bất kỳ bài toán con nào mà chỉ thực hiện điều phối các bài toán con giữa các máy thợ.
Cấu trúc dữ liệu : Danh sách liên kết
Thuật toán
Trên máy chủ
Trên máy thợ
Thuật toán trên máy chủ
Thuật toán trên máy khách
Kết quả thực nghiệm
Sử dụng ngôn ngữ VC++, thư viện chuyển thông báo MPI
Phần cứng : một máy chủ …
Tạo file dữ liệu test
Hướng phát triển
Quá trình khởi tạo : mất nhiều thời gian, lãng phí tài nguyên
Giải pháp : Chia đều cho các bộ xử lý
Tính cận : Mới sử dụng phương pháp đối ngẫu bài toán nới lỏng lagrange
Giải pháp :
Kết hợp với một số phương pháp khác, ví dụ như lợi dụng đặc tính của đồ thị (cây khung nhỏ nhất).
Lựa chọn biến phân nhánh : Cài đặt thêm một số giải pháp để nhanh tiến tới lời giải tối ưu.

Hướng phát triển (tiếp)
Lựa chọn bài toán con : Cây tìm kiếm vẫn có khả năng phát triển theo chiều rộng.
Giải pháp : sử dụng danh sách liên kết có kiểu như sau




Số lượng bài toán con phải duyệt tương đối lớn
Giải pháp : Sử dụng hệ thống gồm hai pha, pha thứ nhất là thuật toán di truyền song song, pha thứ hai là thuật toán nhánh cận song song.
Hướng phát triển (tiếp)
Hoàn thiện hệ thống trở thành một khung chương trình sử dụng giải quyết các bài toán tối ưu dựa trên kỹ thuật nhánh cận.
Cài đặt tất cả các chiến lược trong các pha của thuật toán nhánh cận(như lựa chọn nút,...).
Xây dựng khung chương trình cho các kỹ thuật khác như thuật toán di truyền, chia để trị, qui hoạch động, và một số kỹ thuật Heuristic.
Xây dựng hệ thống trên mô hình bộ nhớ dùng chung.
Xây dựng hệ thống trên môi trường WAN.
Kết luận
Hệ thống lại một số kiến thức đại cương về tính toán song song.
Trình bày một cách hệ thống một số thuật toán song song cơ bản trên đồ thị.
Đề xuất thuật toán tuần tự và thuật toán song song để tìm lời giải chính xác cho bài toán k-median.
Xây dựng và đánh giá hệ thống đã đề xuất.