Song song hóa thuật toán duyệt đồ thị theo chiều rộng

Bài viết Song song hóa thuật toán duyệt đồ thị theo chiều rộng trình bày về song song hóa thuật toán duyệt đồ thị theo chiều rộng BFS (Breadth First Search). Sau đó tác giả sẽ cài đặt thử nghiệm thuật toán để đánh giá được hiệu năng của phương pháp này.
Nội dung trích xuất từ tài liệu:
Song song hóa thuật toán duyệt đồ thị theo chiều rộng Tuyển tập Hội nghị Khoa học thường niên năm 2017. ISBN: 978-604-82-2274-1 SONG SONG HÓA THUẬT TOÁN DUYỆT ĐỒ THỊ THEO CHIỀU RỘNG Nguyễn Ngọc Quỳnh Châu, Đặng Thị Thu Hiền Trường Đại học Thủy lợi, email: chaunnq@tlu.edu.vn 1. GIỚI THIỆU CHUNG 2.2. Song song hóa thuật toán tìm kiếm theo chiều rộng Tính toán song song là một hình thức tính toán trong đó nhiều phép tính được thực Đầu vào của bài toán là đồ thị vô hướng hiện đồng thời, hoạt động trên nguyên tắc là G = (V, E) với V là tập đỉnh, E là tập cạnh những vấn đề lớn được chia thành nhiều và một đỉnh ban đầu cho trước 0. Đầu ra của phần nhỏ hơn, sau đó được giải quyết riêng thuật toán là hai mảng D, P với Du là phần rẽ hoặc tương tranh. Các thuật toán song tử lưu bậc của đỉnh u trong cây BFS, Pu là song đã được sử dụng từ nhiều năm qua, phần tử lưu cha của đỉnh u trong cây BFS. chủ yếu là trong lĩnh vực tính toán hiệu Ý tưởng song song hóa thuật toán như năng cao [3]. sau [2]: Trong bài báo này, tác giả trình bày về song  Gọi Q là một hàng đợi chứa các đỉnh cần song hóa thuật toán duyệt đồ thị theo chiều xét, khởi tạo Q = {0}. rộng BFS (Breadth First Search). Sau đó tác  Gọi V’ là tập chứa các đỉnh đã đưa vào giả sẽ cài đặt thử nghiệm thuật toán để đánh hàng đợi Q, khởi tạo V’ = {0}. giá được hiệu năng của phương pháp này.  Khởi tạo D0 = {0}.  Gọi P là tập k bộ vi xử lý, trong đó Pi là 2. PHƯƠNG PHÁP NGHIÊN CỨU bộ xử lý thứ i. 2.1. Thuật toán duyệt đồ thị theo  Chia tập đỉnh V thành k nhóm đôi một chiều rộng không giao nhau, nhóm thứ i ký hiệu là Vi.  Bộ xử lý Pi sẽ quản lý nhóm đỉnh Vi. Thuật toán duyệt đồ thị theo chiều rộng  Hàng đợi Q do P0 quản lý. hay còn gọi là tìm kiếm theo chiều rộng BFS  Thuật toán chạy lặp lại các bước sau cho cho phép tìm kiếm tất cả các đỉnh trong đồ đến khi Q rỗng: thị bắt đầu từ một đỉnh cho trước: + Lấy đỉnh u ra khỏi hàng đợi Q = Q-u. a) Thuật toán bắt đầu duyệt các đỉnh kề + P0 gửi đỉnh u tới tất cả các bộ xử lý. với đỉnh cho trước. + Mọi bộ xử lý Pi sẽ thực hiện hai thao tác: b) Với mỗi đỉnh trong số các đỉnh được (a) Tìm tập đỉnh Ni thỏa mãn Ni = {v  Vi- duyệt ở lần duyệt trước, thuật toán lại tiếp V’|(u,v)  E}, (b) gửi Ni tới P0, P0 sẽ cập tục duyệt những đỉnh kề với nó mà chưa nhật lại: Q = Q  Ni và V = V  Ni. được duyệt. c) Lặp lại bước (b) cho đến khi duyệt hết 3. KẾT QUẢ NGHIÊN CỨU tất cả các đỉnh trong đồ thị. Trong đồ thị không có trọng số, thuật toán Chương trình viết bằng ngôn ngữ C/C++ tìm kiếm theo chiều rộng luôn tìm ra đường dựa trên thư viện lập trình song song MPI. đi ngắn nhất có thể. Môi trường thử nghiệm được cài đặt dựa trên 162 Tuyển tập Hội nghị Khoa học thường niên năm 2017. ISBN: 978-604-82-2274-1 nền tảng OpenMPI với hai máy tính sử dụng bộ xử lý phải chờ đợi dữ liệu, dẫn tới không các bộ xử lý đa lõi có kết nối mạng nội bộ. hiệu quả khi tính toán. Hai máy tính này có cấu hình như sau:  Dell Vostro 3450, Ram 4G, Intel core I5, CPU 2.4GHz  4.  Dell Vostro 2420, Ram 4G, Intel core I5, CPU 2.6GHz  4. Dữ liệu là một đồ thị G = (V, E) được sinh ngẫu nhiên với số lượng tập đỉnh là 3x104 đỉnh, số lượng cạnh xấp xỉ 9x108 cạnh. Bảng 1 biểu diễn thời gian chạy chương trình (bao gồm thời gian nạp dữ liệu đồ thị vào chương trình t1, tổng thời gian tính toán song song t2 và tổng thời gian truyền thông giữa các bộ xử Hình 1. Biểu diễn tổng thời gian tính toán lý t3) khi số bộ xử lý (coi là số luồng thread khi số lượng bộ xử lý tăng lên của chương trình MPI) tăng lên. Bảng 1. Kết quả chạy thực nghiệm Số bộ xử lý t1 (ms) t2 (ms) t3 (ms) 1 91819 12337 0 2 44708 5894 4374 4 25789 3862 4062 8 25490 4697 4075 16 25738 6912 18264 32 26550 12440 47727 Hình 2. Biểu diễn tổng thời gian Nhìn vào hình 1, ta thấy rằng khi số lượng truyền thông giữa các bộ xử lý bộ xử lý tăng lên, thời gian chạy thuật toán khi số lượng bộ xử lý tăng lên BFS giảm đi tương ứng. Điều này cho thấy giải thuật song song đã làm tăng tốc độ thực 4. KẾT LUẬN thi của chương trình, giúp tìm ra cây BFS nhanh hơn thuật toán tuần tự (khi dùng 1 bộ Trong bài báo này, tác giả đã trình bày về xử lý ta coi như tương đương giải thuật tuần ý tưởng song song hóa thuật toán tìm kiếm tự). Thời gian tính toán giảm từ khoảng 12 theo chiều rộng BFS trên đồ thị vô hướng giây với 1 bộ xử lý xuống còn hơn 3 giây khi không trọng số. Tác giả đã cài đặt thử sử dụng 4 bộ xử lý. Tuy nhiên thời gian tính nghiệm và đánh giá tốc độ cải thiện của thuật toán lại tăng lên khi số lượng bộ xử lý tăng toán song song so với thuật toán tuần tự. Một lên, ví dụ như khi dùng tới 32 bộ xử lý thì số nhận xét rút ra như sau: thời gian tính toán lại rất tồi lên tới khoảng  Thuật toán song song cho phép cải thiện 12 giây, gần như thuật toán tuần tự. Lý giải thời gian chạy, tìm ra kết quả nhanh hơn so cho hiện tượng này là do khi s ...