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. | 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@ 1. GIỚI THIỆU CHUNG . 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. . 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 .
