Luận văn Nâng cao hiệu quả bài toán sắp xếp với giải thuật song song

Nội dung tài liệu: Luận văn Nâng cao hiệu quả bài toán sắp xếp với giải thuật song song

1. ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------- BÙI THANH TUYỀN NÂNG CAO HIỆU QUẢ BÀI TOÁN SẮP XẾP VỚI GIẢI THUẬT SONG SONG LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội – Năm 2014 1
2. ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------- BÙI THANH TUYỀN NÂNG CAO HIỆU QUẢ BÀI TOÁN SẮP XẾP VỚI GIẢI THUẬT SONG SONG Chuyên ngành: Cơ sở toán cho tin học Mã số: 60460110 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Nguyễn Thị Hồng Minh Hà Nội – Năm 2014 2
3. LỜI CẢM ƠN Trên thực tế, không có thành công nào mà không gắn liền với những sự hỗ trợ, giúp đỡ. Trong suốt thời gian từ khi bắt đầu học tập tại trường đến nay, em đã nhận được rất nhiều sự quan tâm, giúp đỡ của quý Thầy Cô Khoa Toán-Cơ-Tin học, Trường Đại học Khoa học Tự nhiên - ĐHQGHN đã cùng với tri thức và tâm huyết của mình để truyền đạt vốn kiến thức quý báu cho chúng em, và luôn luôn tạo mọi điều kiện tốt nhất cho chúng em trong suốt quá trình theo học tại trường. Em xin chân thành cảm ơn quý Thầy Cô và Ban lãnh đạo nhà trường! Với lòng biết ơn sâu sắc nhất, em xin gửi lời cảm ơn tới TS. Nguyễn Thị Hồng Minh, Phó chủ nhiệm Khoa Sau đại học - ĐHQGHN, là cán bộ trực tiếp hướng dẫn và định hướng khoa học cho em. Cô đã dành nhiều thời gian cho việc hướng dẫn em cách nghiên cứu, đọc tài liệu, cài đặt các thuật toán và giúp đỡ em trong việc xây dựng chương trình, em xin chân thành cảm ơn cô! Em cũng xin được chân thành gửi lời cảm ơn đến quý thầy cô, các anh chị em của Trung tâm Tính toán Hiệu Năng Cao Trường Ðại học Khoa học Tự nhiên đã quan tâm giúp đỡ, tạo điều kiện về nhiều mặt, chỉ bảo tận tình trong quá trình em thực hiện thực nghiệm tại trung tâm. Và cuối cùng em xin bày tỏ lòng chân thành biết ơn tới lãnh đạo khoa Công nghệ Thông tin,Trường Đại học Kinh doanh và Công nghệ Hà Nội cùng bạn bè đồng nghiệp, ba mẹ và anh chị em đã luôn ở bên cạnh những lúc em khó khăn và tạo điều kiện thuận lợi giúp em hoàn thành luận văn này. Hà Nội, ngày 26 tháng 3 năm 2014 Học viên: Bùi Thanh Tuyền 1
4. Mục lục LỜI CẢM ƠN ................................................................................................. 1 Danh mục viết tắt ............................................................................................ 4 Danh mục các hình .......................................................................................... 5 Danh mục các bảng ......................................................................................... 5 MỞ ĐẦU ........................................................................................................ 6 CHƯƠNG 1. TỔNG QUAN VỀ XỬ LÝ SONG SONG ................................... 8 1.1 Tổng quan về xử lí song song ....................................................... 8 1.1.1 Tính toán tuần tự và tính toán song song.............................................. 8 1.1.2 Kiến trúc máy tính song song ............................................................. 10 1.1.3 Một số mạng kết nối trên hệ thống song song .................................... 11 1.1.3.1 Mạng liên kết tuyến tính và liên kết vòng ................................... 11 1.1.3.2 Mạng liên kết lưới hai chiều ....................................................... 12 1.1.3.3 Mạng liên kết hình khối .............................................................. 12 1.1.4 Cơ sở đánh giá giải thuật song song ................................................... 13 1.1.4.1 Thời gian thực hiện ..................................................................... 13 1.1.4.2 Hệ số tăng tốc và độ hiệu quả giải thuật ..................................... 14 1.2 Tổng quan về bài toán sắp xếp .................................................... 15 1.2.1 Bài toán sắp xếp. ................................................................................. 15 1.2.2 Các cấu trúc dữ liệu cho bài toán sắp xếp. ......................................... 18 1.2.3 Phân lớp các thuật toán sắp xếp dựa trên độ phức tạp. ...................... 19 1.2.3.1 Lớp thuật toán có độ phức tạp O(n2) ........................................... 19 1.2.3.2 Lớp thuật toán có độ phức tạp O(nlogn) ..................................... 23 1.2.3.3 Thuật toán sắp xếp có độ phức tạp thấp với dữ liệu đặc biệt ...... 26 1.3 Kết luận chương ........................................................................ 28 CHƯƠNG 2. MỘT SỐ THUẬT TOÁN SONG SONG CHO BÀI TOÁN SẮP XẾP .............................................................................................................. 29 2.1 Chiến lược song song cho bài toán sắp xếp. ................................ 29 2
5. 2.2 Thuật toán sắp xếp song song phát triển dựa trên thuật toán tuần tự 30 2.2.1 Thuật toán sắp xếp hoán vị chẵn lẻ..................................................... 30 2.2.2 Thuật toán Shellsort. ........................................................................... 32 2.2.3 Thuật toán Parallel QuickSort. ........................................................... 36 2.2.4 Thuật toán HyperQuicksort ................................................................ 41 2.3 Thuật toán sắp xếp song song dựa trên các mẫu chuẩn PSRS ....... 47 2.3.1 Tư tưởng thuật toán ............................................................................ 47 2.3.2 Đánh giá độ phức tạp .......................................................................... 50 2.3.3 Ví dụ ................................................................................................... 50 2.4 Kết luận chương ........................................................................ 52 CHƯƠNG 3. ỨNG DỤNG LẬP TRÌNH SONG SONG CÀI ĐẶT THUẬT TOÁN SẮP XẾP PSRS VÀ PARALLELQUICKSORT ................................. 53 3.1 Môi trường và phương pháp thực nghiệm ................................... 53 3.1.1 Môi trường thực nghiệm ..................................................................... 53 3.1.2 Phương pháp thực nghiệm .................................................................. 54 3.2 Các kết quả thực nghiệm ............................................................ 54 3.2.1 Kết quả thực nghiệm khi chạy trên thuật toán PSRS ......................... 54 3.2.2 So sánh kết quả giữa thuật toán PSRS và ParallelQuicksort .............. 56 3.3 Kết luận chương ........................................................................ 57 KẾT LUẬN ................................................................................................ 588 TÀI LIỆU THAM KHẢO .............................................................................. 59 3
6. Danh mục viết tắt Viết tắt Viết đầy đủ Ý nghĩa ADN Acid Deoxyribo Nucleic Phân tử di truyền CPU Central Processing Unit Đơn vị xử lí trung tâm MIMD Multiple Instruction Multiple Đa lệnh Đa dữ liệu Data MISD Multiple Instruction Single Data Đa lệnh Đơn dữ liệu PQ Parallel QuickSort Sắp xếp nhanh song song PSRS Parallel Sorting by Regular Sắp xếp song song dựa Sampling trên mẫu SIMD Single Instruction Multiple Data Đơn lệnh Đa dữ liệu SISD Single Instruction Single Data Đơn lệnh Đơn dữ liệu 4
7. Danh mục các hình ...................................................................................... 5 Hình 1.1 Minh họa quá trình xử lí tuần tự .................................................... 8 Hình 1.2 Minh họa quá trình xử lí song song ............................................... 9 Hình 1.3 Phân loại Flynn về các kiến trúc song song ................................. 10 Hình 1.4 Mạng liên kết tuyến tính và mạng vòng ....................................... 11 Hình 1.5 Mạng liên kết lưới hai chiều ........................................................ 12 Hình 1.6 Mạng liên kết khối 4 chiều với 16 bộ xử lí. ................................. 13 Hình 2.1 Ví dụ thuật toán ShellSort ............................................................ 35 Hình 2.2 Minh họa thuật toán ParallelQuickSort ........................................ 38 Hình 2.3 Ví dụ minh họa thuật toán ParallelQuickSort .............................. 40 Hình 2.4 Minh họa thuật toán HyperQuickSort .......................................... 43 Hình 2.5 Ví dụ minh họa thuật toán HyperQuickSort ................................ 45 Hình 2.6 Minh họa thuật toán PSRS ........................................................... 49 Hình 3.1 Biểu đồ so sánh thời gian chạy của thuật toán PSRS .................. 57 Hình 3.2 Biểu đồ so sánh thời gian chạy của các BXL chạy với N=106 .... 57 Hình 3.3 Biểu đồ so sánh thời gian chạy của thuật toán PSRS và PQ........ 58 Danh mục các bảng Bảng 1. So sánh kết quả chạy thuật toán PSRS .......................................... 55 Bảng 2. So sánh thời gian chạy của PSRS và Parallel Quicksort ............... 58 5
8. MỞ ĐẦU Từ thủa sơ khai của lịch sử máy tính và khoa học tính toán, việc xây dựng được một chương trình tính toán trên một máy tính là điều hết sức kỳ diệu đối với tất cả mọi người. Từ những chiếc máy tính khổng lồ, cồng kềnh nhưng chỉ thao tác được những tác vụ đơn giản đến những máy nhỉnh hơn lòng bàn tay nhưng có thể tính toán được hàng nghìn tỷ phép tính trong một giây, từ những chương trình rất nhỏ chỉ có vài ba câu lệnh của những ngày xa xưa, đến những chương trình vô cùng lớn có sức ảnh hưởng đến toàn cầu như ngày nay tất cả những điều đó đã nói lên được sự phát triển mạnh mẽ của ngành công nghệ thông tin. Sự phát triển cả về phần cứng lẫn phần mềm đã tạo ra rất nhiều sự đổi thay trong công nghệ tính toán của ngành khoa học máy tính cũng như ảnh hưởng của nó đến tất cả các lĩnh vực khác nhau trong xã hội. Càng ngày yêu cầu về tốc độ tính toán và xử lí càng lớn, đòi hỏi các máy tính, các phần mềm chương trình phải thực thi cực nhanh. Chính vì vậy, việc sử dụng các hệ thống tính toán truyền thống đã không thể đáp ứng kịp nhu cầu đó của con người cũng như của các ngành khoa học liên quan. Việc xây dựng các chương trình tính toán trên các hệ thống song song để hỗ trợ cho hệ thống tuần tự đã trở thành một điều tất yếu. Nhìn lại chúng ta thấy rằng, hầu hết các chương trình đòi hỏi tốc độ tính toán lớn đều áp dụng trong những lĩnh vực quan trọng ảnh hưởng lớn đến xã hội. Không đâu xa, đó là những ứng dụng trong dự báo thời tiết, thiên tai, đó là những ứng dụng trong những ngành thiết kế máy bay, kĩ thuật quân sự, đó là những ứng dụng trong thương mại điện tử, trong y sinh học v.v tất cả đều được xử lí song song với mục tiêu nâng cao hiệu quả xử lí tính toán. Nhận thấy đây là một trong những hướng nghiên cứu đang được phát triển và sẽ được ứng dụng nhiều trong thực tế, vì vậy em đã lựa chọn đề tài của mình vào việc nghiên cứu và tìm hiểu về các hệ thống xử lí song song áp dụng vào giải quyết một bài toán cụ thể đó là bài toán sắp xếp. Khái niệm sắp xếp dường như đã gắn liền với xã hội loài người từ thuở ban đầu của nền văn minh. Nó đơn giản thể hiện trong việc sắp hàng, trong việc phân công công việc, Ngày nay, trong một thế 6
9. giới mà khoa học công nghệ thay đổi từng ngày và nhu cầu khai thác, tìm kiếm thông tin của con người ngày càng cao thì việc nâng cao tính hiệu quả của các giải thuật sắp xếp cũng ngày càng trở nên quan trọng hơn. Từ những vấn đề trên, đề tài “Nâng cao hiệu quả bài toán sắp xếp với giải thuật song song” sẽ tập trung vào nghiên cứu việc song song hóa các thuật toán sắp xếp nhằm giảm thiểu thời gian sắp xếp dữ liệu để đưa vào áp dụng trong các ứng dụng thực tế. Luận văn gồm có 3 chương: Chương 1. Tổng quan về xử lí song song và bài toán sắp xếp. Nội dung chủ yếu của chương nhằm giới thiệu tổng quan về xử lí song song, các mô hình cơ bản trong hệ thống song song đồng thời đưa ra sự nhìn nhận tổng quan nhất về bài toán sắp xếp, đi đôi với việc hệ thống hóa lại hầu hết các thuật toán sắp xếp theo hướng tính toán tuần tự. Chương 2. Một số thuật toán song song cho bài toán sắp xếp. Nội dung của chương tập trung vào vấn đề phát triển các thuật toán song song cho bài toán sắp xếp. Đây là nội dung chính của luận văn, các thuật toán sắp xếp sẽ được song song hóa dựa trên các chiến lược cụ thể. Chương 3. Ứng dụng lập trình song song cài đặt thuật toán PSRS và ParallelQuickSort. Nội dung của chương sẽ trình bày các kết quả thực nghiệm trên thuật toán PSRS và so sánh hai thuật toán PSRS và ParallelQuicksort về thời gian xử lí khi cùng chạy trên hệ thống tính toán song song với nhiều bộ xử lí. 7
10. CHƯƠNG 1. TỔNG QUAN VỀ XỬ LÝ SONG SONG VÀ BÀI TOÁN SẮP XẾP 1.1 Tổng quan về xử lí song song 1.1.1 Tính toán tuần tự và tính toán song song Trong những thập niên 60, nền tảng để thiết kế máy tính đều dựa trên mô hình của John Von Neumann, với một bộ xử lí đơn được nối với một vùng lưu trữ làm bộ nhớ và tại cùng một thời điểm chỉ có một lệnh được thực thi. Đó là hình thức tính toán tuần tự [1]. Tuy nhiên, hiện nay khoa học kỹ thuật ngày càng phát triển, từ đó sẽ đặt ra nhiều bài toán với khối lượng tính toán rất lớn, trong đó có những bài toán mà kết quả chỉ có ý nghĩa nếu được hoàn thành trong thời gian cho phép. Từ đó hình thành nên hệ thống xử lí song song. Xử lí song song là quá trình xử lí gồm nhiều tiến trình được kích hoạt đồng thời, được thực hiện trên nhiều bộ xử lí và cùng tham gia vào giải quyết một bài toán. Hình 1.1 và 1.2 dưới đây phần nào cho thấy cái nhìn khái quát về sự khác nhau giữa xử lí tuần tự và xử lí song song. Hình 1.1 Minh họa quá trình xử lí tuần tự Trong xử lí tuần tự (hình 1.1), một CPU sẽ thực hiện lần lượt các lệnh Si để giải quyết bài toán. Với xử lí song song (hình 1.2) các lệnh để giải quyết bài toán được chia ra thành các cụm độc lập, được gọi là các tiến trình và mỗi tiến trình sẽ được thực hiện trên một CPU khác nhau. 8