Tài liệu Song song hóa một số thuật toán tổ hợp

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------- Vũ Hồng Linh SONG SONG HÓA MỘT SỐ THUẬT TOÁN TỔ HỢP Chuyên ngành: Bảo đảm toán học cho máy tính và hệ thống tính toán Mã số: 604635 LUẬN VĂN THẠC SĨ KHOA HỌC Người hướng dẫn khoa học: PGS.TS. HOÀNG CHÍ THÀNH Hà Nội – 2011 LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp LỜI CẢM ƠN Tôi xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới PGS.TS Hoàng Chí Thành, người đã trực tiếp hướng dẫn, giúp đỡ, động viên tôi trong suốt thời gian thực hiện luận văn này. Con cảm ơn Cha, Mẹ và gia đình, những người đã dạy dỗ, khuyến khích, động viên con trong những lúc khó khăn, tạo mọi điều kiện cho con nghiên cứu học tập. Tôi cũng xin chân thành cảm ơn các Thầy Cô trong Bộ môn Tin học, Khoa Toán - Cơ - Tin học, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội và các bạn bè, đồng nghiệp tại Trường Dự bị Đại Học Dân tộc Trung Ương đã giúp đỡ tôi rất nhiều trong quá trình học tập, sưu tầm tài liệu và trong công tác để tôi có thể hoàn thành bản luận văn này. Dù đã cố gắng hết sức cùng với sự tận tâm của thầy giáo hướng dẫn song do trình độ còn hạn chế nên khó tránh khỏi những thiếu sót. Rất mong nhận được sự góp ý của thầy cô và các bạn. Hà Nội, tháng 10 năm 2011 Học viên Vũ Hồng Linh 2 LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp MỤC LỤC MỞ ĐẦU..................................................................................................... 6 1. LÝ DO CHỌN ĐỀ TÀI......................................................................... 6 2. PHẠM VI NGHIÊN CỨU..................................................................... 7 3. PHƯƠNG PHÁP NGHIÊN CỨU.......................................................... 7 CHƯƠNG 1. TỔNG QUAN VỀ TÍNH TOÁN SONG SONG ................. 8 1.1 CÁC MÔ HÌNH TÍNH TOÁN SONG SONG ....................................... 8 1.1.1 Mô hình SISD (Single Instruction, Single Data) ........................ 8 1.1.2 Mô hình SIMD (Single Instruction, Multiple Data).................... 9 1.1.3 Mô hình MISD (Multiple Instruction, Single Data)...................... 9 1.1.4 Mô hình MIMD (Multiple Instruction, Multiple Data) ............... 10 1.2 MỘT SỐ KỸ THUẬT PHÂN RÃ TRONG TÍNH TOÁN SONG SONG ........................................................................................................ 11 1.2.1 Phân rã đệ quy (recursive decomposition) ................................. 12 1.2.2 Phân rã dữ liệu (data-decomposition) ........................................ 13 2.2.3 Phân rã thăm dò (exploratory decomposition) ........................... 17 1.3 KỸ THUẬT SONG SONG HÓA TÍNH TOÁN DỰA TRÊN PHÂN ĐOẠN DÃY CÁC NGHIỆM CỦA BÀI TOÁN ........................................ 20 CHƯƠNG 2. BÀI TOÁN DÃY BỊ CHẶN .............................................. 22 2.1 BÀI TOÁN DÃY BỊ CHẶN................................................................ 22 2.2 THUẬT TOÁN TÌM CÁC DÃY BỊ CHẶN ........................................ 23 2.3 SONG SONG HÓA THUẬT TOÁN TÌM CÁC DÃY BỊ CHẶN........ 25 CHƯƠNG 3. ÁP DỤNG CHO MỘT SỐ BÀI TOÁN TỔ HỢP ............ 28 3.1 BÀI TOÁN HOÁN VỊ......................................................................... 28 3.1.1 Bài toán hoán vị....................................................................... 28 3.1.2 Thuật toán sinh các hoán vị .................................................... 29 3.1.3 Song song hóa thuật toán sinh các hoán vị............................. 36 3.1.4 Ứng dụng của bài toán hoán vị ............................................... 37 3 LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp 3.2 BÀI TOÁN TẬP CON ........................................................................ 39 3.2.1 Bài toán tập con....................................................................... 40 3.2.2 Thuật toán sinh các tập con..................................................... 41 3.2.3 Song song hóa thuật toán sinh các tập con ............................. 42 3.2.4 Ứng dụng của bài toán tập con................................................ 42 3.3 BÀI TOÁN PHÂN HOẠCH................................................................ 43 3.3.1 Bài toán phân hoạch................................................................ 43 3.3.2 Thuật toán tìm các phân hoạch ............................................... 47 3.3.3 Song song hóa thuật toán tìm các phân hoạch........................ 49 3.3.4 Ứng dụng của bài toán phân hoạch ........................................ 49 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................................... 51 TÀI LIỆU THAM KHẢO........................................................................ 53 PHỤ LỤC.................................................................................................. 54 PHỤ LỤC 1. BÀI TOÁN DÃY BỊ CHẶN................................................. 54 1. Chương trình cho thuật toán tuần tự ........................................... 54 2. Chương trình cho thuật toán khi phân đoạn nghiệm .................. 55 PHỤ LỤC 2. BÀI TOÁN HOÁN VỊ.......................................................... 58 1. Chương trình cho thuật toán tuần tự ........................................... 58 2. Chương trình cho thuật toán khi phân đoạn nghiệm .................. 59 PHỤ LỤC 3. BÀI TOÁN TẬP CON.......................................................... 62 1. Chương trình cho thuật toán tuần tự ........................................... 62 2. Chương trình cho thuật toán khi phân đoạn nghiệm .................. 63 PHỤ LỤC 4. BÀI TOÁN PHÂN HOẠCH................................................. 65 1. Chương trình cho thuật toán tuần tự ........................................... 65 2. Chương trình cho thuật toán khi phân đoạn nghiệm .................. 66 4 LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp MỤC LỤC CÁC HÌNH VẼ Hình 1. Mô hình tính toán tuần tự …………………………………………..6 Hình 1.1. Mô hình máy tính SISD ................................................................ 8 Hình 1.2. Mô hình máy tính SIMD............................................................... 9 Hình 1.3. Mô hình máy tính MISD............................................................. 10 Hình 1.4. Mô hình máy tính MIMD ........................................................... 11 Hình 1.5. Phân rã đệ quy sắp xếp dãy gồm 12 chữ số ................................. 13 Hình 1.6. Phân rã phép nhân ma trận.......................................................... 14 a) Phân hoạch các ma trận đầu vào và đầu ra thành 2x2 ma trận con.......... 14 b) Một phân rã của phép nhân ma trận thành bốn công việc dựa trên các phân hoạch của các ma trận trong (a) .................................................................. 14 Hình 1.7. Nhân hai ma trận A và B với phân hoạch của ma trận trung gian 3 chiều D.................................................................................................... 16 Hình 1.8. Một phân rã của phép nhân ma trận dựa trên việc phân hoạch ma trận trung gian 3 chiều D ............................................................................ 17 Hình 1.9. Đồ thị phụ thuộc của phân rã trong Hình 1.8 .............................. 17 Hình 1.10. Phân rã thăm dò minh họa cho Bài toán đố thứ 15 .................... 19 Hình 1.11. Sơ đồ tính toán song song tìm các nghiệm của bài toán ............ 21 Hình 3.1. Loại ai và dồn danh sách XS ….………………………………….35 5 LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp MỞ ĐẦU 1. LÝ DO CHỌN ĐỀ TÀI Trong tính toán truyền thống, phần mềm máy tính được viết cho tính toán tuần tự. Để giải quyết một bài toán, một thuật toán được xây dựng và thực hiện như một chuỗi tuần tự các lệnh. Các lệnh này được thực hiện trong bộ xử lý trung tâm (CPU) của máy tính. Tại một thời điểm, chỉ có một lệnh được thực hiện. Sau khi lệnh trước kết thúc thì lệnh tiếp theo mới được thực hiện. Quá trình thực hiện các lệnh được thể hiện như hình dưới đây. Hình 1. Mô hình tính toán tuần tự Tính toán song song là một hình thức tính toán, trong đó nhiều tính toán được thực hiện đồng thời. Tính toán song song hoạt động trên nguyên tắc một bài toán lớn được chia thành các bài toán nhỏ hơn, sau đó các bài toán này được giải quyết đồng thời. Song song đã được sử dụng nhiều năm và trong những năm gần đây tính toán song song đã trở thành mô hình thống trị trong kiến trúc máy tính, chủ yếu dưới hình thức các bộ đa xử lý (multi-processors). Vậy, tại sao phải tính toán song song? Mặc dù tốc độ xử lý của các bộ xử lý tăng lên nhiều, nhưng do giới hạn về vật lý nên khả năng tính toán của chúng không thể tăng mãi được. Điều này dẫn tới là muốn tăng được khả năng tính toán của các hệ thống máy tính thì phải khai thác được khả năng xử lý song song của chúng. 6 LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp Nhiều bài toán với số lượng tính toán rất lớn như bài toán mô phỏng thời tiết, bài toán tạo hình trong y học hay phân tích mật mã… không thể giải được trong một khoảng thời gian hợp lý nếu sử dụng tính toán tuần tự - ngay cả khi ta thực hiện trên các siêu máy tính, do đó đòi hỏi phải sử dụng những hệ thống đa bộ xử lý và xử lý song song. Để song song hóa tính toán, chúng ta có thể chia bài toán thành các bài toán nhỏ hơn rồi giải quyết song song các bài toán đó như chiến lược chia để trị. Hoặc có thể chia nhỏ dữ liệu của bài toán rồi giải quyết song song theo từng phần. Tuy nhiên, với các bài toán tổ hợp thì hai phương pháp trên là không khả thi. Với một hướng tiếp cận mới, song song hóa tính toán dựa trên phân đoạn dãy các nghiệm của bài toán, chúng tôi sẽ giải quyết được vấn đề song song hóa các thuật toán tổ hợp. 2. PHẠM VI NGHIÊN CỨU Trong phạm vi một luận văn thạc sĩ, đề tài tập trung nghiên cứu cơ sở lý thuyết và ứng dụng. Trên cơ sở đó, tiến hành phân đoạn dãy nghiệm cho một số bài toán tổ hợp tiêu biểu. 3. PHƯƠNG PHÁP NGHIÊN CỨU - Phương pháp nghiên cứu tài liệu - Phương pháp phân tích - Phương pháp tổng hợp - Phương pháp thực nghiệm - Phương pháp lập trình 7 LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp CHƯƠNG 1. TỔNG QUAN VỀ TÍNH TOÁN SONG SONG 1.1 CÁC MÔ HÌNH TÍNH TOÁN SONG SONG Có nhiều cách phân loại các kiến trúc tính toán khác nhau trong đó sự phân loại của M. Flynn được dùng phổ biến nhất. Flynn phân loại kiến trúc máy tính dựa trên một số đặc tính như: số lượng bộ xử lý, số lượng các chương trình chúng có thể thực hiện và cấu trúc của bộ nhớ. Sự phân loại này đã dẫn đến bốn mô hình kiến trúc tính toán như sau: 1.1.1 Mô hình SISD (Single Instruction, Single Data) Những máy tính SISD chỉ có một CPU mà tại một thời điểm chúng chỉ thực hiện duy nhất một lệnh (Single Instruction) và chỉ có thể xử lý một đối tượng dữ liệu (Single Data). Control Unit Control Signals Instruction Arithmetic Processor Results Data Stream Memory Hình 1.1. Mô hình máy tính SISD Chẳng hạn, khi thực hiện phép tính C = A + B và A = B*2 thì máy sẽ thực hiện tuần tự như sau: 8 LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp Mô hình SISD chính là mô hình máy tính truyền thống kiểu Von Neumann. 1.1.2 Mô hình SIMD (Single Instruction, Multiple Data) Những máy tính SIMD có một bộ điều khiển và chỉ thực hiện một lệnh tại một thời điểm nhưng chúng có nhiều phần tử xử lý. Control Unit Cotrol signals Processing Element 1 Cotrol signals Processing Element 2 Processing Element 3 Hình 1.2. Mô hình máy tính SIMD Bộ điều khiển phát ra tín hiệu điều khiển cho các phần tử xử lý và các phần tử xử lý này sẽ thực hiện cùng một thao tác trên các đối tượng dữ liệu khác nhau. 1.1.3 Mô hình MISD (Multiple Instruction, Single Data) Máy tính loại MISD là ngược lại với SIMD. Máy tính MISD có thể thực hiện nhiều chương trình (nhiều lệnh) trên cùng một mục dữ liệu, nên còn 9 LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp được gọi là MPSD (đa chương trình, đơn luồng dữ liệu). Kiến trúc kiểu này có thể chia thành hai nhóm:  Lớp các máy tính yêu cầu những bộ xử lý khác nhau có thể nhận được những lệnh khác nhau để thực hiện trên cùng một mục dữ liệu. Control Unit1 Control Unit 2 Control Unit n Instruction Stream 1 Arithmetic Processor 1 Instruction Stream2 Arithmetic Processor 2 Instruction Stream n Arithmetic Processor n Data stream Hình 1.3. Mô hình MISD  Lớp các máy tính có các luồng dữ liệu được chuyển tuần tự theo dãy các CPU liên tiếp. 1.1.4 Mô hình MIMD (Multiple Instruction, Multiple Data) MIMD là một hệ thống đa bộ xử lý hoặc đa máy tính. Mỗi bộ xử lý trong hệ thống này có một bộ điều khiển riêng. 10 LUẬN VĂN CAO HỌC Control Unit1 Control Unit 2 Song song hóa một số thuật toán tổ hợp Instruction Stream 1 Instruction Stream2 Instruction Stream n Control Unit n Arithmetic Processor 1 Data Stream 1 Arithmetic Processor 2 Data Stream 2 Arithmetic Processor n Data Stream n Hình 1.4. Mô hình máy tính MIMD Hệ thống MIMD có các đặc trưng sau:  Chúng phân tán tiến trình cho một số bộ xử lý độc lập.  Tất cả các bộ xử lý chia sẻ tài nguyên được lưu trữ trong bộ nhớ chính.  Các bộ xử lý hoạt động đồng thời và độc lập với nhau.  Mỗi bộ xử lý chạy một chương trình riêng. 1.2 MỘT SỐ KỸ THUẬT PHÂN RÃ TRONG TÍNH TOÁN SONG SONG Quá trình phân chia một bài toán thành các bài toán nhỏ hơn, một số hoặc tất cả các bài toán nhỏ đó có thể được thực hiện song song, được gọi là phân rã. Việc thực hiện đồng thời nhiều tính toán là chìa khóa để giảm thời 11 LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp gian cần thiết để giải quyết toàn bộ bài toán. Các bài toán có thể có kích thước tùy ý, nhưng một khi đã xác định, chúng được coi là đơn vị chia của bài toán. Các bài toán được phân rã có thể có kích thước không giống nhau. Trong mục này, chúng ta sẽ mô tả một số kỹ thuật phân rã thường được sử dụng để đạt được sự tương tranh. Đây không phải là đầy đủ tất cả các kỹ thuật phân rã có thể có. Ngoài ra, mỗi một phân rã không phải lúc nào cũng dẫn đến một thuật toán song song tốt nhất cho bài toán xác định. Mặc dù có những thiếu sót song các kỹ thuật phân rã mô tả trong phần này thường tạo một khởi đầu tốt cho nhiều bài toán và sự kết hợp của các kỹ thuật này có thể được sử dụng để có được sự phân rã hiệu quả cho nhiều bài toán. Các kỹ thuật phân rã bao gồm: phân rã đệ quy (recursive decomposition), phân rã dữ liệu (data-decomposition) và phân rã thăm dò (exploratory decomposition). 1.2.1. Phân rã đệ quy Phân rã đệ quy là một phương pháp đạt được sự tương tranh trong các bài toán giải được bằng chiến lược chia để trị. Trong kỹ thuật này, để giải một bài toán các thuật toán gọi đến chính nó một hoặc nhiều lần để xử lý các bài toán con liên quan. Đầu tiên, ta chia bài toán thành các bài toán con tương tự với bài toán ban đầu nhưng kích thước nhỏ hơn. Sau đó giải đệ quy các bài toán con và kết hợp các lời giải để được lời giải cho bài toán ban đầu. Ví dụ 1.1: Xét bài toán sắp xếp dãy n phần tử A sử dụng thuật toán quicksort (giả sử n = 12). Quicksort là một thuật toán chia để trị mà bắt đầu chọn một phần tử trục x. Sau đó phân hoạch dãy A thành 2 dãy con A0 và A1 sao cho các phần tử của A0 nhỏ hơn x và các phần tử của A1 lớn hơn hoặc bằng x. Đây là bước chia 12 LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp của thuật toán. Sau đó, mỗi một dãy con A0 và A1 được sắp xếp bằng cách gọi đệ quy thủ tục quicksort. Hình 1.5. Phân rã đệ quy sắp xếp một dãy gồm 12 số Hình vẽ trên là đồ thị thực hiện của bài toán. Lúc đầu chỉ có một dãy (là nút gốc của cây), và chúng ta chỉ cần dùng một quá trình duy nhất để phân rã nó. Hoàn thành quá trình phân rã ở nút gốc ta được hai dãy con (A0 và A1, tương ứng với hai nút đầu tiên của cây) và mỗi dãy có thể thực hiện phân rã song song với nhau. Tương tự như vậy, sự tương tranh tiếp tục tăng lên khi ta di chuyển dần xuống đến nút lá của cây. 1.2.2. Phân rã dữ liệu Phân rã dữ liệu là một phương pháp mạnh và thường được sử dụng để tạo ra sự tương tranh trong các thuật toán chạy trên các bộ dữ liệu lớn. Trong phương pháp này, sự phân rã các tính toán được thực hiện theo hai bước:  Bước 1: Dữ liệu mà các tính toán sử dụng được phân rã;  Bước 2: Các dữ liệu được phân rã này được sử dụng để tạo ra sự phân rã của các tính toán trong các công việc. 13 LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp Các thao tác mà những công việc này thực hiện trên các phân vùng dữ liệu khác nhau thường tương tự (như ví dụ nhân ma trận) hoặc được chọn từ một nhóm nhỏ các thao tác. Một số cách phân rã dữ liệu như sau: Phân hoạch dữ liệu đầu ra: Trong nhiều bài toán, mỗi yếu tố đầu ra có thể được tính toán một cách độc lập như một chức năng của đầu vào. Trong các bài toán như vậy, một phân hoạch của dữ liệu đầu ra tự động tạo ra một sự phân rã của các bài toán cho mỗi công việc, mỗi công việc được phân công tính toán một phần của đầu ra. Ta xét bài toán nhân ma trận trong ví dụ dưới đây để minh họa cho việc phân rã dựa vào phân hoạch dữ liệu đầu ra. Ví dụ 1.2: Xét bài toán nhân hai ma trận vuông A và B cấp n để được ma trận C. Hình 1.6 cho thấy sự phân rã bài toán này thành bốn công việc. Mỗi ma trận được xem là sự hợp thành của bốn khối hay các ma trận con được xác định bằng cách chia đôi kích thước của ma trận. Bốn ma trận con của C, kích thước của mỗi ma trận là (n/2) × (n/2), được tính toán một cách độc lập bởi bốn công việc là tổng của các ma trận con của A và B. Hình 1.6. Phân rã bài toán nhân ma trận a) Phân hoạch các ma trận đầu vào và đầu ra thành 2x2 ma trận con b) Một phân rã của phép nhân ma trận thành bốn công việc dựa trên các phân hoạch của các ma trận trong (a) 14 LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp Phân hoạch dữ liệu đầu vào: Phân hoạch dữ liệu đầu ra chỉ thực hiện được khi mỗi dữ liệu đầu ra có thể được tính toán như một chức năng của đầu vào. Trong nhiều thuật toán, khó hoặc không thể phân hoạch được dữ liệu đầu ra. Ví dụ, trong tìm kiếm phần tử max, min hoặc tổng của một tập hợp số, dữ liệu đầu ra là một giá trị chưa xác định. Trong thuật toán sắp xếp, mỗi phần tử đầu ra riêng biệt không thể được xác định hiệu quả khi đứng riêng biệt. Trong các trường hợp như vậy, có thể sử dụng phân hoạch dữ liệu đầu vào để đạt được sự tương tranh. Mỗi phân hoạch được tạo ra sẽ được tính toán bởi một công việc. Sau đó sẽ có một công việc để tổng hợp các kết quả. Ví dụ, trong tính tổng của một dãy N số sử dụng p bộ xử lý (N > p), ta có thể phân hoạch đầu vào thành p dãy con có kích thước gần bằng nhau. Mỗi công việc sẽ tính tổng các phần tử trong mỗi dãy con, sau đó p kết quả thành phần sẽ được tổng hợp lại thành kết quả cuối cùng. Phân hoạch dữ liệu trung gian: Các thuật toán thường được cấu trúc như những tính toán nhiều tầng sao cho dữ liệu đầu ra của tầng này là đầu vào của tầng tiếp theo. Sự phân rã như vậy của một thuật toán có thể suy ra từ việc phân hoạch dữ liệu đầu vào hoặc dữ liệu đầu ra của một tầng trung gian của thuật toán. Việc phân hoạch dữ liệu trung gian đôi khi có thể đạt được sự tương tranh cao hơn so với việc phân hoạch dữ liệu đầu vào hoặc dữ liệu đầu ra. Thông thường, dữ liệu trung gian không được sinh ra một cách rõ ràng trong các thuật toán tuần tự và việc cấu trúc lại một số thuật toán ban đầu có thể phải sử dụng dữ liệu phân hoạch trung gian để tạo ra một phân rã. Ví dụ 1.3: Chúng ta trở lại với ví dụ nhân hai ma trận kích thước n×n. Ở phần trên, chúng ta đã phân rã ma trận đầu ra C để đạt được sự tương tranh tối đa là 4. Chúng ta có thể làm tăng mức độ tương tranh bằng cách tạo ra một giai đoạn trung gian trong đó 8 công việc tính toán các ma trận con và lưu kết quả vào ma trận tạm thời D. 15 LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp Hình 1.7. Nhân hai ma trận A và B với phân hoạch của ma trận trung gian 3 chiều D Một phân hoạch của ma trận trung gian D biến một phân rã thành 8 công việc. Hình 1.8 mô tả sự phân rã này. Sau khi hoàn thành phép nhân, sẽ có một công việc thực hiện phép cộng để được ma trận kết quả. Tất cả các ma trận con D*,i,j có cùng chiều thứ hai và thứ ba là i và j được tính tổng và đưa vào ma trận Ci, j. 8 công việc được đánh số từ 1 đến 8 trong Hình 1.8, mỗi công việc sẽ thực hiện O(n 3/8) công việc trong phép nhân (n/2) × (n/2) các ma trận con của A và B. Sau đó mỗi công việc từ 9 đến 12 sử dụng O(n2/4) thời gian để cộng (n/2) × (n/2) ma trận con của ma trận trung gian D để được ma trận kết quả cuối cùng C. Hình 1.9 cho thấy đồ thị phụ thuộc nhiệm vụ tương ứng với phân rã trong Hình 1.8. 16 LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp Hình 1.8. Một phân rã của phép nhân ma trận dựa trên việc phân hoạch ma trận trung gian 3 chiều D Hình 1.9. Đồ thị phụ thuộc của phân rã trong Hình 1.8 2.2.3. Phân rã thăm dò Phân rã thăm dò được sử dụng để phân rã các bài toán mà các tính toán nằm bên dưới tương ứng với một sự tìm kiếm trong không gian nghiệm. Trong phân rã thăm dò, chúng ta phân hoạch không gian tìm kiếm thành nhiều phần nhỏ hơn, và tìm kiếm đồng thời trên các không gian này cho đến khi các nghiệm mong muốn được tìm thấy. Ví dụ 1.4: Bài toán đố thứ 15 17 LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp Có 15 quân cờ được được đánh số từ 1 đến 15 đặt trên một bàn cờ gồm 4×4 ô. Quân cờ có thể di chuyển vào vị trí trống từ một vị trí liền kề nó do đó sẽ tạo ra một ô trống ở vị trí ban đầu của quân cờ. Quân cờ có thể di chuyển theo 4 hướng: lên, xuống, sang trái và sang phải. Cho biết cấu hình ban đầu và cuối cùng của quân cờ. Hãy xác định một chuỗi các di chuyển sao cho từ cấu hình ban đầu, ta đạt được cấu hình cuối cùng sau một chuỗi ngắn nhất các phép dịch chuyển. Giả sử ta có một cấu hình ban đầu và cấu hình cuối cùng như sau: Đầu tiên, từ cấu hình ban đầu ta tạo ra các nút sao cho mỗi nút là một khả năng di chuyển để tạo ra các cấu hình mới của bàn cờ (ví dụ ta có 4 khả năng di chuyển như hình minh họa). Sau đó mỗi nút được giao cho một công việc để tiếp tục khám phá cho đến khi ít nhất một trong số đó tìm thấy một nghiệm. Ngay sau khi một công việc tìm thấy nghiệm nó sẽ thông báo cho các công việc khác để chấm dứt việc tìm kiếm. 18 LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp Hình 1.10. Phân rã thăm dò minh họa cho bài toán đố thứ 15 19 LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp 1.3 KỸ THUẬT SONG SONG HÓA TÍNH TOÁN DỰA TRÊN PHÂN ĐOẠN DÃY CÁC NGHIỆM CỦA BÀI TOÁN Với nhiều bài toán chúng ta có thể biết trước số lượng nghiệm của nó và sự sắp xếp của các nghiệm trong một dãy cần tìm. Đối với các bài toán này ta có thể áp dụng chiến lược phân rã dữ liệu đầu ra với một cách làm chi tiết hơn. Song song hóa tính toán dựa trên phân đoạn dãy các nghiệm của bài toán là một hướng tiếp cận mới để giải quyết các bài toán trên. Để tổ chức tính toán song song, ta thực hiện hai bước sau: Bước 1: Chia dãy các nghiệm cần tìm của bài toán thành n (n ≥ 2) đoạn con. Mỗi một đoạn con có đầu vào và điều kiện kết thúc riêng. Đầu vào của quá trình tính toán thứ nhất trùng với đầu vào của bài toán, điều kiện kết thúc của quá trình tính toán thứ n trùng với điều kiện kết thúc của bài toán. Việc phân đoạn dãy nghiệm của bài toán phải thỏa mãn hai điều kiện: 1. Dễ dàng xác định đầu vào và điều kiện kết thúc của các quá trình tìm đoạn con các nghiệm. 2. Độ dài các đoạn con các nghiệm chênh lệch nhau càng ít càng tốt. Hai điều kiện này nhằm hiện thực hóa quá trình tính toán song song, cân bằng tải cho các bộ xử lý và giảm đáng kể thời gian tính toán. Đạt được cả hai điều kiện là điều rất khó khăn. Chính vì thế, chúng ta thường ưu tiên điều kiện thứ nhất và cố gắng để điều kiện thứ hai đạt được đến mức tốt nhất có thể. Bước 2: Sử dụng cùng một chương trình (thuật toán) để tính toán tìm ra các đoạn con nghiệm đó một cách đồng thời trên môi trường tính toán song song. 20