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

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ồn8Duyệt cây có thứ tự tổng quát9Tâm và median của câyChỉ 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ểum 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)) 10Tìm kiếm theo chiều rộng11Câ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ý12Thuật toán song song giải bài toán k-median trên đồ thịGiới thiệu bài toánThuật toán nhánh cận tuần tựThuật toán nhánh cận song song13Giới thiệu bài toánKhở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ó.14Ví dụ minh họaCó 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ụ. 15Ví 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ử.16Mô hình toán họcVới điều kiện17Các phương pháp đã giải quyết18Thuật toán nhánh cậnKhở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óaKhi 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 19Thuật toán nhánh cậnKhở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óaKhi 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 20Thuật toán nhánh cận giải bài toán k-medianLựa chọn bài toán conLựa chọn theo độ sâu Lựa chọn cận tốt nhất đầu tiênPhân nhánh : Nếu bài toán con có lời giải bộ phận là a1a2ai-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). 21Tính cậnBài toán nới lỏng lagrage	Với điều kiệnBài toán đối ngẫu	Với điều kiện22Thuật toán nhánh cận song songPhân loại thuật toán nhánh cận song songLựa chọn kiến trúc thiết kế thuật toán song songThiết kế mô hình thuật toán song song23Phân loại thuật toán nhánh cận song songSong 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.24Phân loại thuật toán nhánh cận song songSong 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.25Lựa chọn kiến trúcBộ nhớ phân tánBộ nhớ dùng chung26Lựa chọn kiến trúcBộ nhớ phân tánBộ nhớ dùng chung27Thiết kế mô hình thuật toán nhánh cận song songQuản lý tập bài toán conLược đồ thực hiệnXây dựng hệ thống28Quản lý tập bài toán conCâ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.29Câ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ủ. 30Dò xét kết thúc và cân bằng chất lượngDò 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 31Sơ đồ hệ thống32Thiết kế chương trìnhTổng quan hệ thốngThuật toán nhánh cận tuần tựThuật toán nhánh cận song songDữ liệu tập trungDữ liệu phân tánKết quả thực nghiệmNhận xét và hướng phát triển33Tổng quan hệ thống34Thuật toán tuần tự35Lượ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ếtThuật toánTrên máy chủTrên máy thợ36Thuật toán trên máy chủ37Thuật toán trên máy thợ38Lượ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ếtThuật toán Trên máy chủTrên máy thợ39Thuật toán trên máy chủ40Thuật toán trên máy khách41Kết quả thực nghiệmSử dụng ngôn ngữ VC++, thư viện chuyển thông báo MPIPhần cứng : một máy chủ Tạo file dữ liệu test6 5 31 2 102 3 43 4 7 4 5 85 6 26 30 10 14 21 29 31 10 0 4 11 19 21 14 4 0 7 15 17 21 11 7 0 8 10 29 19 15 8 0 2 31 21 17 10 2 0 Floyd.exeFloyd.datkmedian.dat42Số medianGiá trị tối ưuThời gian thực hiện thuật toán tuần tự (Ts giây)Thời gian thực hiện thuật toán song song - Dữ liệu tập trung(Tp giây)Hiệu suấtThời gian thực hiện thuật toán song song - Dữ liệu phân tán(Tp giây)Hiệu suất4753254%37%63086525610%1152%8214635928214%7355%10164165740717%9874%121319133983715%27854%1410832374188514%82532%168843023247514%102432%18720125478617%32845%205912456156317%42364%4344Số đỉnhGiá trị tối ưuThời gian thực hiện thuật toán tuần tự (Ts giây)Thời gian thực hiện thuật toán song song - Dữ liệu tập trung(Tp giây)Hiệu suấtThời gian thực hiện thuật toán song song - Dữ liệu phân tán(Tp giây)Hiệu suất20753020%20%3018575511%413%404006161313%535%506431451729%862%6093162365547%3771%70121965899569%7686%8015540114715184%14886%90200612984671%4278%10058192424658%4558%4546Hướng phát triểnQuá trình khởi tạo : mất nhiều thời gian, lãng phí tài nguyênGiả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 lagrangeGiả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. 47Hướ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.48Hướ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. 49Kết luậnHệ 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. 50