Chương I : Đại cương về tính toán song song i. Phân tích độ phức tạp P : số bộ xử lý. Vòng While thực hiện logn lần, mỗi lần thời gian tính là O(1) và đòi hỏi p bộ xử lý; Tại bước đầu tiên của thuật toán đòi hỏi nhiều bộ xử lý nhất p = n/2. Do trong thuật toán không có đòi hỏi cạnh tranh đọc cũng như cạnh tranh ghi nên thuật toán có thể cài đặt với thời gian O(logn) với O(n) bộ xử lý trên mô hình EREW PRAM.
Phát triển bởi nhân đôi Phương pháp phát triển bởi nhân đôi có thể được nhìn theo một cách khác. Tại mỗi bước, mỗi phần tử xử lý nhân đôi số phần tử tính toán. Vì thế “phát triển” thu được bởi nhân đôi số lượng dữ liệu tại mỗi bước. Tất nhiên, có các cách khác nhau sử dụng kĩ thuật này, thậm chí đối với các bài toán không kết hợp với cấu trúc cây nhị phân.
Sau đây là một vài ví dụ. Xét bài toán xếp hạng danh sách (list-ranking) : Cho một danh sách liên kết có N phần tử được lưu trong mảng A[1:N], hãy tính toán hạng của mỗi phần tử. Hạng của mỗi phần tử trong danh sách là khoảng cách từ nó tới cuối danh sách. Vì thế phần tử đầu tiên có hạng là N và phần tử cuối cùng có hạng là 1.
Để giải bài toán này ta sử dụng kĩ thuật nhân đôi, chúng ta phân một bộ xử lý tới mỗi phần tử. Ban đầu mỗi bộ xử lý chỉ biết hàng xóm bên phía phải của nó trong danh sách. Tại bước đầu tiên, mỗi bộ xử lý tìm kiếm hàng xóm của hàng xóm của nó. Nghĩa là, sau bước đầu tiên mỗi bộ xử lý biết được phần tử có khoảng cách tới nó là 2.
Gọi Next(i) là phần tử xa nhất nằm phía phải phần tử thứ i …Khởi tạo, next(i) là hàng xóm bên phải của i ngoại trừ phần tử cuối cùng trong danh sách thì hàng xóm bên phải của nó là Nil. Tại mỗi bước pi cập nhật next(i) tới next(next(i)) cho đến khi đạt tới cuối danh sách. R R Nếu tại bước k mỗi bộ xử lý biết phần tử cách nó là x thì trong bước tiếp theo mỗi 20 ĐỖ TRUNG KIÊN Chương I : Đại cương về tính toán song song bộ xử lý biết phần tử cách nó 2x. Vì thế xử lý nhân đôi đảm bảo rằng mỗi bộ xử lý sẽ đạt tới cuối danh sách trong nhiều nhất là logN bước và sẽ biết hạng của nó.
Thuật toán xếp hạng trong danh sách Input : A(1:n), link(1:n), head Output : Rank(1:n) Begin 1. For i = 1 to n dopar Rank(i) = 1 Next(i) = link(i) EndPar 2. For k = 1 to logn do 2.a For i=1 to n dopar if NEXT[i] <> 0 Rank(i) = Rank(i) + Rank(NEXT(i)) NEXT(i) = NEXT(NEXT(i)) endif EndPar End Phân tích độ phức tạp B1: O(n) bộ xử lý với thời gian O(1) B2: Lặp lại O(n) lần, 2.a O(n) bộ xử lý với thời gian O(1) => Thuật toán có độ phức tạp thời gian là O(logn) sử dụng O(n) bộ xử lý trên mô hình EREW PRAM. Một ví dụ khác là bài toán tìm đường đi trên cây từ gốc tới mọi nút trong cây tổng quát biểu diễn bởi quan hệ cha-con, nghĩa là mỗi nút ta biết cha của nó và kí hiệu là parent(i).
Với nút gốc r thì parent(r) = r. Với quan hệ cha-con này thì kết thúc bước đầu tiên ta biết được cha (tổ tiên thứ nhất ) và cha của cha (tổ tiên thứ hai) của mọi nút. Kết thúc bước thứ hai ta biết tổ tiên thứ nhất, thứ hai, thứ ba và thứ tư của mọi 21 ĐỖ TRUNG KIÊN Chương I : Đại cương về tính toán song song nút. Rõ ràng nếu chiều cao của cây là h thì chỉ cần logh bước là ta thu được đường đi trên cây từ gốc tới mọi nút.
Chương sau sẽ minh họa chi tiết kĩ thuật này. Cuối cùng ta xem xét các bài toán lý thuyết đồ thị ví dụ như tìm cây khung độ sâu tối thiểu, …hay đường đi ngắn nhất giữa mọi cặp nút. Các bài toán như thế có thể được giải quyết bởi kỹ thuật nhân đôi cây khung cục bộ. Chúng ta bắt đầu với các cây có gốc là một nút của đồ thị và chiều cao là 1.
Nghĩa là, với mỗi nút x trong đồ thị G tương ứng với một cây có gốc là x và chứa đựng tất cả các nút y sao cho (x, y) là một cạnh trong đồ thị. Rõ ràng danh sách kề của mỗi nút diễn tả một cây như thế. Bây giờ với mỗi cây chúng ta thực hiện trộn tất cả các cây mà gốc của nó là một trong những nút nằm trong cây đang xét và sau đó xóa các nút xuất hiện nhiều lần trên cây (nếu có). Nếu lặp đi lặp lại thủ tục trộn cây thì sau nhiều nhất logn bước chúng ta sẽ có lời giải mong muốn của bài toán (n là số lượng nút trong G).
Hình sau minh họa cách xác định cây khung có chiều xâu tối thiểu cho đồ thị digraph Chúng ta bắt đầu với các cây có gốc tại một nút trong G và có chiều cao là 1 (hình b). Sau khi trộn các cây theo cách diễn tả ở trên mà chưa xóa đi các nút xuất hiện lặp chúng ta thu được cây có nhiều cao là 2 hoặc ít hơn trong hình c. Bây giờ nếu các nút giống nhau xuất hiện nhiều hơn một lần trên cây thì chúng ta xóa tất cả các nút trừ nút có khoảng cách tới gốc là tối thiểu (điều này để chắc chắn cây xây dựng 22 ĐỖ TRUNG KIÊN Chương I : Đại cương về tính toán song song đảm bảo thuộc tính độ sâu tối thiểu). Các cây phải được xóa đi trong hình c được đánh dấu là X.
Vì đồ thị G có 6 nút nên cần 3 bước trộn cây như thế. Và cuối cùng ta thu được cây khung tối thiểu có gốc 1 tại hình d. Chia để trị Ta chia bài toán thành các bài toán con nhỏ hơn, giải quyết bài toán con cho đến khi bài toán con nhỏ nhất có thể giải được. Ví dụ : Xét bài toán tính tổng n số lưu trong mảng A[1:n].
Ở trên ta đã thiết kế thuật toán song song có độ phức tạp thời gian O(logn) với O(n) bộ xử lý. Sau đây ta sẽ sử dụng kỹ thuật chia để trị để giảm số lượng bộ xử lý mà không làm thay đổi độ phức tạp thời gian của thuật toán. Tiến hành phân chia dữ liệu ta sẽ có thuật toán với độ phức tạp thời gian O(logn) với O(n/logn) bộ xử lý. + Phân các phần tử của mảng vào n/logn nhóm; mỗi nhóm chứa logn phần tử k = logn và r = n/logn ; rk = n = 2k P Nhóm 1 : A1 A2 …….A logn R R R R R Nhóm 2 : Alogn + 1 ……A 2logn R R R R r = n/logn nhóm …………………………… + Phân mỗi nhóm cho một trong n/logn bộ xử lý.
+ Thời gian cộng trên mỗi bộ xử lý là O(logn) và lưu kết quả cất vào Bi. Sau R R đó sử dụng thuật toán trong mục 1 để tính tổng của B1 , B 2 , …., B n/logn với R R R R R R thời gian O(log(n/logn)) ≡ O(logn) sử dụng O(n/logn) bộ xử lý. Thuật toán tính tổng tối ưu Đầu vào : mảng A[1:n] Đầu ra : tổng -> Sum Begin 1. For i=1 to n/logn dopar i.
Sử dụng thuật toán tuần tự để tính tổng A(i-1)logn+1 ….Ailogn và cất R R R R vào biến Bi R 2. EndPar 23 ĐỖ TRUNG KIÊN Chương I : Đại cương về tính toán song song 3., Bn/logn => Sum R R R R R R End. Phân tích độ phức tạp : Thuật toán có độ phức tạp thời gian O(logn) với O(n/logn) bộ xử lý, mô hình sử dụng là EREW PRAM. Phân chia Kỹ thuật chia để trị bao gồm hai bước Bước 1 : Chia bài toán thành các bài toán con và giải quyết một cách đồng thời Bước 2 : Kết hợp để thu được lời giải của bài toán cần giải Trong kỹ thuật phân chia ta sẽ chú trọng hơn trong bước 1 hay ta chia bài toán thành các bài toán con mà không cần bước 2.
Minh họa thuật toán thông qua bài toán trộn mảng. Bài toán trộn : Cho hai mảng A, B được sắp xếp theo thứ tự không giảm. Trộn hai mảng và lưu vào mảng C sao cho các phần tử được sắp xếp theo thứ tự không giảm. Giả thiết n = 2k ; r = n/logn ; k, r ∈ N P P Thuật toán tuần tự có độ phức tạp O(n) Sau đây ta đi thiết kế thuật toán phân chia cho bài toán trộn mảng.
Phân chia mảng thành r nhóm = n/logn; mỗi nhóm có logn phần tử. Bây giờ ta sẽ tìm r số nguyên j(1), j(2), …. Nhóm r : B1 B 2………B j(r) R R R R R 24 ĐỖ TRUNG KIÊN Chương I : Đại cương về tính toán song song Ta sẽ phân bộ xử lý i (1 ≤ i ≤ r) cho nhóm i của A và nhóm i của B và nó sẽ thực hiện thuật toán trộn. Thuật toán trộn Đầu vào : A(1:n) B(1:n) đã được sắp xếp theo thứ tự không giảm, n = 2k P P Đầu ra : C(1:2n) được sắp xếp theo thứ tự không giảm.
For i = 1 to n dopar 2. Sử dụng tìm kiếm nhị phân để tìm chỉ số a. J(i) = max{t : A ik ≥ Bt} R R RR 3. Sử dụng thuật toán tuần tự để nối hai mảng A((i-1)×k+1:i ×k) và B() End.
Phân tích độ phức tạp Bước 2 : Độ phức tạp tại bước 2 là O(logn) Bước 3 : Phụ thuộc mảng con của A, B : mảng A((i-1)×k+1:i×k) gồm k phần tử ; còn số phần tử trong B (j(i-1)×k+1:i×k) là không biết trước. Nếu nó cũng là k thì thời gian của bước 3 là O(logn). Nếu nó lớn hơn k thì thực hiện đệ qui chia B trước A sau. Nên độ phức tạp tại bước 3 là O(logn).
Tóm lại thuật toán có độ phức tạp thời gian là O(logn) với O(n/logn) bộ xử lý trên mô hình EREW PRAM. 25 ĐỖ TRUNG KIÊN Chương II : Một số thuật toán song song cơ bản trên đồ thị CHƯƠNG 2 : MỘT SỐ THUẬT TOÁN SONG SONG CƠ BẢN TRÊN ĐỒ THỊ Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu và có nhiều ứng dụng hiện đại. Những tư tưởng cơ bản của lý thuyết đồ thị được đề xuất vào những năm đầu của thế kỷ 18 bởi nhà toán học lỗi lạc người Thụy sỹ Leonhard Euler. Chính ông là người đã sử dụng đồ thị để giải bài toán nổi tiếng về các cái cầu ở thành phố Konigsberg.