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

ĐẠ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 ĐẠ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 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 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 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 Danh mục 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 Multiple Instruction Multiple Đa lệnh Đa dữ liệu Viết tắt MIMD Data MISD PQ Multiple Instruction Single Data Đa lệnh Đơn dữ liệu 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 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 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 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 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 Hình 1.2 Minh họa quá trình xử lí song song Mục đích xây dựng hệ thống xử lí song song là để thực hiện tính toán nhanh hơn trên cơ sở sử dụng đồng thời nhiều bộ xử lí để giải quyết được những bài toán phức tạp với yêu cầu khối lượng tính toán lớn. Ví dụ các bài toán tính toán lớn như mô phỏng các hoạt động ở mức lượng tử, tính toán quỹ đạo chuyển động của vật thể trong không gian, dự báo thời tiết, các bài toán nghiên cứu trên ADN… Trong tính toán song song hiện nay, chúng ta có thể sử dụng hai mô hình chính: Thứ nhất là sử dụng các siêu máy tính với rất nhiều các bộ xử lí được tích hợp bên trong và được thiết kế đồng bộ cả về phần cứng lẫn phần mềm. Các công nghệ được áp dụng trong các siêu máy tính thường là các công nghệ tiên tiến làm cho giá thành của hệ thống siêu máy tính thường rất cao. Cách thứ hai là kết nối các đơn máy tính đồng bộ lại với nhau và cùng thực hiện bài toán, hệ thống các máy tính kết nối này là hệ thống tính toán song song phân cụm. Hệ thống này có ưu điểm là giá thành rẻ hơn do nó sử dụng các thiết bị thông thường và tính linh hoạt của hệ thống (số nút, số bộ xử lí, bộ nhớ, thiết bị mạng… đều mang tính tùy biến cao). Sự phát triển mạnh mẽ của mạng máy tính, các công nghệ mạng hiện nay đã lấp đi sự hạn chế về truyền thông trong hệ thống máy tính song song phân cụm làm cho nó được phát triển rộng rãi. Các lĩnh vực sử dụng hệ thống tính toán song song phân cụm thường yêu cầu tính toán không quá lớn như xử lí ảnh, nhận dạng vân tay, tính toán kết cấu công trình, mô phỏng các thí nghiệm… 9 Phần dưới đây sẽ trình bày về các mô hình máy tính song song cơ bản theo phân loại của Flynn giúp chúng ta có cái nhìn tổng quát hơn về các hệ thống song song. 1.1.2 Kiến trúc máy tính song song Một hệ thống máy tính song song là một máy tính với nhiều hơn một bộ xử lí cho phép thực hiện đồng thời nhiều tiến trình. Định nghĩa này có thể bao quát được tất cả các siêu máy tính với hàng trăm bộ xử lí, các mạng máy tính trạm hay các hệ thống nhúng... Dựa vào sự phân biệt ở cách kết nối giữa các bộ xử lí (hay thành phần xử lí), giữa bộ xử lí và bộ nhớ mà có rất nhiều loại kiến trúc máy tính song song khác nhau. Nhưng theo phân loại của Flynn dựa trên cấu trúc luồng lệnh và luồng dữ liệu thì có bốn kiến trúc điển hình [1] đó là: Hình 1.3 Phân loại Flynn về các kiến trúc song song SIMD- Single Instruction Multiple Data: Đơn lệnh đa dữ liệu. Đây là một kiểu máy tính song song mà các bộ xử lí thực hiện cùng một lệnh nhưng với các dữ liệu khác nhau. Mô hình này có ưu điểm là đơn giản trong thiết kế phần cứng cũng như phân mềm nhưng chỉ phù hợp để giải quyết các bài toán tương đối đặc thù có tính cân đối cao như trong xử lí như xử lí ảnh, các bài toán với các dữ liệu dạng vecto hoặc ma trận. Các thuật giải cho các đa máy tính thường chạy không hiệu quả trên các máy SIMD. MIMD- Multiple Instruction Multiple Data: Đa lệnh đa dữ liệu. Đây là một mô hình kiến trúc máy tính song song thông dụng hiện nay. Với mô hình này thì 10 tất cả các bộ xử lí sẽ thực hiện các lệnh khác nhau với các dữ liệu riêng khác nhau. Sự thực thi các lệnh có thể theo cơ chế đồng bộ hoặc không đồng bộ, điều này giúp cho MIMD rất linh hoạt trong việc xử lí song song. Tuy nhiên, cùng với tính linh hoạt của mình, mô hình MIMD cũng mang theo một sự phức tạp nhất định. Việc lập trình được những bài toán song song theo mô hình này đòi hỏi có nhiều công sức nghiên cứu, phân tích bài toán để tìm ra một cách phân rã tối ưu. Ngoài ra còn có hai loại mô hình khác theo phân loại của Flynn tuy nhiên ít thông dụng: SISD-Single Instruction Single Data: Đơn lệnh đơn dữ liệu và MISDMultiple Instruction Single Data: Đa lệnh đơn dữ liệu. Với sự đa dạng của các mô hình kiến trúc máy tính song song, thì việc tổ chức và kết nối các bộ xử lí trong các mô hình cũng được quan tâm và nghiên cứu. Hầu hết các máy tính với đa bộ xử lí đều phải đưa ra một cách để các bộ xử lí tương tác với nhau. Trong một số hệ thống, các bộ xử lí sử dụng kết nối mạng để truy cập vào bộ nhớ chia sẻ, nhưng cũng có một số hệ thống khác thì lại sử dụng phương thức gửi và nhận tin nhắn để truyền thông với nhau. Dưới đây là một số mạng kết nối được sử dụng trong các hệ thống máy tính song song. 1.1.3 Một số mạng kết nối trên hệ thống song song 1.1.3.1 Mạng liên kết tuyến tính và liên kết vòng Với mạng liên kết tuyến tính, các bộ xử lí được liên kết với nhau theo dãy và được đánh số theo thứ tự tăng dần. Trong mạng liên kết này, trừ hai phần tử đầu và cuối của mạng, tất cả các bộ xử lí đều có hai láng giềng là bộ xử lí trước và sau nó. Đây là dạng liên kết đơn giản, nhưng dữ liệu cũng cần phải chuyển qua nhiều bộ xử lí, do đó sự truyền thông dữ liệu giữa các bộ xử lí đặc biệt là bộ xử lí đầu và cuối sẽ bị chậm lại khi số bộ xử lí lớn. Hình 1.4 Mạng liên kết tuyến tính và mạng vòng 11 Mạng liên kết vòng được tổ chức tương tự như mạng liên kết tuyến tính, tuy nhiên, với mạng liên kết vòng, bộ xử lí đầu tiên và cuối cùng được kết nối với nhau để tạo thành một vòng. Trong mạng liên kết vòng, sự trao đổi giữa các bộ xử lí có thể thực hiện theo một chiều gọi là mạng đơn, hoặc theo cả hai chiều gọi là mạng kép. Sự truyền thông trong mạng liên kết vòng, nhất là các bộ xử lí ở xa nhau vẫn bị trễ. 1.1.3.2 Mạng liên kết lưới hai chiều (Two-Dimentional mesh) Với mạng liên kết lưới hai chiều, mỗi bộ xử lí được liên kết với các láng giềng: Trên, dưới, trái và phải. Mạng liên kết lưới hai chiều có hai dạng đó là lưới quay vòng lưới không quay vòng. Hình 1.5 Mạng liên kết lưới hai chiều 1.1.3.3 Mạng liên kết hình khối (Hypercube Network) Giả sử có 𝑛 bộ xử lí, trong đó 𝑛 là lũy thừa của 2, 𝑛 = 2𝐷 (𝐷 ≥ 0). Trong mạng này, mỗi bộ xử lí sẽ liên kết với đúng 𝐷 bộ xử lí lân cận. Trong đó, chỉ số của các bộ xử lí được đánh dưới dạng chuỗi nhị phân, hai bộ xử lí được kết nối với nhau nếu chúng sai khác nhau đúng một bit. 12 Hình 1.6 Mạng liên kết khối Trên đây là một số kiểu liên kết các bộ xử lí điển hình được sử dụng trong các mô hình song song. Việc sử dụng kiến trúc song song nào và các thức liên kết giữa các bộ xử lí song song ra sao cũng là một yếu tố quan trọng ảnh hưởng đến khả năng xử lí bài toán. 1.1.4 Cơ sở đánh giá giải thuật song song Việc sử dụng mô hình song song nào phù hợp với bài toán nào là một vấn đề khá quan trọng trong xử lí song song bởi lẽ một thuật toán có thể phù hợp với mô hình này nhưng chưa chắc đã là tốt với mô hình kia. Để đánh giá được một giải thuật song song, thông thường chúng ta sẽ dựa vào ba tiêu chí: Thời gian thực hiện, khả năng tăng tốc, độ hiệu quả của thuật toán [4]. 1.1.4.1 Thời gian thực hiện Khi tốc độ tính toán được coi là mục tiêu chủ yếu khi xây dựng các máy tính song song, thì thời gian thực hiện là một độ đo quan trọng trong việc đánh giá giải thuật. Nó được xác định như là thời gian giải thuật yêu cầu để giải quyết một vấn đề trên máy tính song song, đó là khoảng thời gian kể từ thời điểm ban đầu đến thời điểm kết thúc. Nếu các bộ xử lí khác nhau, tất cả không bắt đầu và kết thúc đồng thời, thì thời gian thực hiện bằng thời gian kéo dài giữa thời điểm bộ xử lí đầu tiên bắt đầu tính toán đến thời điểm cuối cùng bộ xử lí kết thúc tính toán. Trước khi thực sự cài đặt một giải thuật song song hay tuần tự đều có sự phân tích về lý thuyết, giải thuật cần bao nhiêu thời gian để giải quyết vấn đề tính toán đã 13 cho. Điều này thường được thực hiện bằng cách tính toán các thao tác cơ bản hoặc các bước mà giải thuật thực hiện trong trường hợp xấu nhất. Số các bước như thế là một hàm của kích thước đầu vào (input size). Các thao tác cơ bản có thể là phép cộng, so sánh hoặc đổi chỗ, truyền dữ liệu. Mỗi thao tác như vậy yêu cầu một số cố định các đơn vị thời gian trên máy tính đơn bộ xử lí truyền thống. 1.1.4.2 Hệ số tăng tốc và độ hiệu quả giải thuật Thời gian thực hiện không hẳn là thước đo thuận tiện nhất để đánh giá độ hiệu quả của thuật giải. Khi thời gian thực hiện có xu hướng biến đổi theo kích thước bài toán, thời gian thực hiện phải được tiêu chuẩn hóa khi so sánh hiệu năng giải thuật với kích thước bài toán khác nhau. Hiệu quả của giải thuật được định nghĩa là phần thời gian mà bộ xử lí dùng để thực hiện công việc có ích, chỉ ra mức độ hiệu quả của một giải thuật khi sử dụng các tài nguyên tính toán của một máy tính song song theo hướng độc lập với kích thước bài toán. Được xác định bằng công thức sau: 𝐸𝑝 = 𝑇𝑠 𝑝𝑇𝑝 Trong đó: 𝑇𝑠 là thời gian thực hiện thuật toán tuần tự trên 1 bộ xử lí 𝑇𝑝 là thời gian thực hiện thuật toán song song trên 𝑝 bộ xử lí 𝐸𝑝 là hệ số hiệu quả của giải thuật 𝑝 là số bộ xử lí Một độ đo khác đánh giá được hiệu năng của giải thuật là khả năng tăng tốc, đây là hệ số mà thời gian thực hiện được giảm đi khi thực hiện bài toán với 𝑝 bộ xử lí. Được xác định theo công thức sau: 14 𝑆𝑝 = 𝑇𝑠 𝑇𝑝 Trong đó: 𝑇𝑠 là thời gian thực hiện thuật toán tuần tự trên 1 bộ xử lí 𝑇𝑝 là thời gian thực hiện thuật toán song song trên 𝑝 bộ xử lí 𝑆𝑝 là hệ số tăng tốc. 𝑆𝑝 càng lớn thì thuật toán song song càng tốt. Năm 1967 Amdahl đã đưa ra luật về giới hạn khả năng tăng tốc: Luật Amdahl [4]: Giả sử 𝑓 là tỉ lệ cần phải thực hiện tính toán tuần tự, trong đó, 0≤ 𝑓 ≤1. Khả năng tăng tốc tối đa 𝑆𝑝 đạt được bởi một máy tính song song có p bộ xử lí thực hiện tính toán là: 𝑆𝑝 ≤ 1 𝑓+ = 1−𝑓 𝑝 1 + (𝑝 − 1)𝑓 𝑝 1.2 Tổng quan về bài toán sắp xếp Sắp xếp là một bài toán quan trọng và phổ biến trong lĩnh vực tin học. Đó là bài toán cơ bản được sử dụng bởi hầu hết các chương trình ứng dụng trên máy tính [5]. Thực tế này có phần dễ hiểu vì việc xử lí trên dữ liệu đã được sắp xếp sẽ trở nên dễ dàng hơn nhiều so với dữ liệu ngẫu nhiên không có thứ tự. Hơn nữa, có nhiều giải thuật thao tác trên dữ liệu yêu cầu dữ liệu phải được sắp xếp trước khi xử lí. Vì vậy, đã có nhiều thuật toán sắp xếp đã được nghiên cứu và phát triển. 1.2.1 Bài toán sắp xếp. Sắp xếp là quá trình xử lí một danh sách các phần tử để đặt chúng theo một thứ tự nào đó (tăng dần, giảm dần) dựa trên nội dung lưu trữ tại mỗi phần tử. Với dữ liệu là kiểu số, bài toán sắp xếp đơn giản được phát biểu như sau: Cho một 15 mảng S có 𝑛 phần tử thuộc kiểu số, S={a1, a2,…, an} chưa có thứ tự theo giá trị các phần tử. Yêu cầu chuyển mảng S đã cho thành mảng S’ S’={a1’, a2’,…, an’| ai’∈S, ai’ ≤ aj’ (hoặc ai’ ≥aj’) với 1≤ 𝑖 ≤ 𝑗 ≤ 𝑛}. Ta có mảng S’ được sắp xếp từ mảng S. Có nhiều giải thuật thực hiện việc sắp xếp mảng, chúng ta có thể phân loại các giải thuật sắp xếp theo các tiêu chí dưới đây: Xét về không gian sắp xếp, giải thuật sắp xếp được phân thành sắp xếp trong và sắp xếp ngoài [3][4]. Với sắp xếp trong, số lượng các phần tử được sắp xếp là đủ nhỏ để vừa với bộ nhớ chính, trong khi sắp xếp ngoài được sử dụng để sắp trên các bộ nhớ bổ trợ như trên ổ đĩa lưu trữ, thường được sử dụng để sắp xếp trong trường hợp số phần tử là quá lớn. Xét về cách thức thực hiện sắp xếp, có thể phân thành hai loại là sắp xếp dựa trên sự so sánh và sắp xếp không dựa trên sự so sánh [3]. Thuật toán sắp xếp dựa trên sự so sánh sắp xếp một chuỗi các phần tử bằng cách lặp lại phép so sánh các cặp các phần tử, nếu chúng không theo thứ tự thì đổi chỗ chúng cho nhau. Các phép tính cơ bản của sắp xếp dựa trên sự so sánh được gọi là “so sánh- đổi chỗ”. Khi xây dựng thuật toán sắp xếp kiểu này, chúng ta luôn phải đặt ra mục tiêu là giảm thiểu tối đa số phép “so sánh và đổi chỗ” để tăng hiệu quả của các thuật toán sắp xếp. Với một tư tưởng khác, các thuật toán sắp xếp không dựa trên sự so sánh thực hiện việc sắp xếp bằng cách sử dụng sự hiểu biết cụ thể về các thuộc tính của các phần tử (chẳng hạn như sự biểu diễn các phần tử dưới dạng nhị phân…). Phổ biến hơn và thường được sử dụng hơn đó là phân loại các thuật toán sắp xếp dựa trên sự phân tích về độ phức tạp của các thuật toán. Dựa vào độ phức tạp các thuật toán sắp xếp có thể được chia thành ba lớp sau: Lớp thuật toán có độ phức tạp 𝑂(𝑛2 ) bao gồm thuật toán sắp xếp chọn (SelectSort), thuật toán sắp xếp chèn (InsertSort), thuật toán sắp xếp nổi bọt (BubbleSort), thuật toán sắp xếp Gnome, thuật toán ShellSort. Thứ hai là lớp thuật toán có độ phức tạp 16 𝑂(𝑛𝑙𝑜𝑔𝑛) bao gồm các thuật toán sắp xếp nhanh (QuickSort), thuật toán sắp xếp trộn (MergeSort), thuật toán sắp xếp vun đống (HeapSort), thuật toán sắp xếp chẵn lẻ (OddEvenSort)… và cuối cùng là lớp thuật toán có độ phức tạp thấp, sắp xếp trên dữ liệu đặc biệt như thuật toán sắp xếp CountingSort 𝑂(𝑛 ∗ 𝑚), RadixSort 𝑂(𝑛 + 𝑚). Cùng với mục đích sắp xếp như nhau, nhưng có nhiều phương pháp giải quyết khác nhau như vậy. Do đó, nếu chỉ dựa vào độ phức tạp của thuật toán để đánh giá thuật toán này là tốt hơn thuật toán kia về mọi mặt là không nên. Việc chọn một thuật toán sắp xếp thích hợp cho phù hợp với từng yêu cầu, từng điều kiện cụ thể là kỹ năng của người lập trình. Những thuật toán có độ phức tạp 𝑂(𝑛2 ) thì chỉ nên áp dụng trong chương trình có ít lần sắp xếp và với kích thước nhỏ. Về tốc độ, có thể nói BubbleSort luôn là tồi nhất, nhưng mã lệnh của nó thì lại đơn giản dễ cài đặt. Trong những thuật toán có độ phức tạp O(n2), InsertionSort tỏ ra nhanh hơn những phương pháp còn lại mã lệnh cũng tương đối đơn giản. Với n là nhỏ, việc chọn ra m khóa nhỏ nhất bởi SelectionSort có thể thực hiện dễ dàng chứ không cần phải sắp xếp lại toàn bộ như InsertionSort. Các thuật toán CountingSort và RadixSort nên được tận dụng trong trường hợp các khóa sắp xếp là số tự nhiên (hay là một kiểu dữ liệu có thể quy ra thành các số tự nhiên) bởi những thuật toán này có tốc độ rất cao. QuickSort, HeapSort, MergeSort và ShellSort là những thuật toán sắp xếp tổng quát, dãy khóa thuộc kiểu dữ liệu có thứ tự nào cũng có thể áp dụng được chứ không nhất thiết phải là các số. QuickSort gặp nhược điểm trong những trường hợp suy biến nhưng xác suất sảy ra trường hợp này thường nhỏ. HeapSort thì mã lệnh hơi phức tạp và khó cài đặt hơn, nhưng nếu cần chọn ra m khóa lớn nhất trong dãy khóa thì HeapSort sẽ không phải sắp lại toàn bộ dãy. MergeSort phải đòi hỏi thêm một không gian nhớ phụ, nên áp dụng nó trong trường hợp sắp xếp trên file. Còn Shellsort thì hơi khó trong việc đánh giá về thời gian thực thi, nó là sửa đổi của thuật toán sắp xếp chèn nhưng lại có tốc độ tốt, mã lệnh đơn giản và lượng bộ 17 nhớ cần huy động rất ít. Tuy nhiên, những nhược điểm của bốn phương pháp này quá nhỏ so với ưu điểm chung của chúng là nhanh và hiệu quả cao. Hơn nữa, chúng được đánh giá cao không chỉ vì tính tổng quát và tốc độ nhanh, mà còn là kết quả của những các tiếp cận khoa học đối với bài toán sắp xếp [2]. 1.2.2 Các cấu trúc dữ liệu cho bài toán sắp xếp Việc tổ chức dữ liệu cho các bài toán sắp xếp cũng là một trong các vấn đề quan trọng cần được quan tâm để hỗ trợ nâng cao hiệu quả thuật toán khi thực hiện. Thông thường, một tập các đối tượng cần sắp xếp là tập các bản ghi, mỗi bản ghi bao gồm một số trường khác nhau. Nhưng không phải toàn bộ các trường dữ liệu trong các bản ghi đều được xem xét đến trong quá trình sắp xếp mà chỉ là một trường nào đó (hay một vài trường nào đó) được chú ý tới. Trường như vậy được gọi là trường khóa. Việc sắp xếp sẽ được tiến hành dựa vào giá trị của khóa này. Khi sắp xếp, các bản ghi trong bảng sẽ được đặt lại vào các vị trí sao cho giá trị khóa tương ứng với chúng có đúng thứ tự đã ấn định. Vì kích thước của toàn bản ghi có thể rất lớn, nên nếu việc sắp xếp thực hiện trực tiếp trên các bản ghi sẽ đòi hỏi sự chuyển đổi vị trí của các bản ghi, kéo theo việc thường xuyên phải di chuyển, copy những vùng nhớ lớn, gây ra tổn phí khá nhiều thời gian. Để khắc phục tình trạng này, ta xây dựng một bảng khoá, mỗi bản ghi trong bảng ban đầu sẽ tương ứng với một bản ghi trong bảng khóa. Bảng khóa cũng gồm các bản ghi nhưng mỗi bản ghi chỉ gồm có hai trường: trường khóa và trường chứa liên kết tới một bản ghi ban đầu, tức là chứa một thông tin đủ để biết bản ghi tương ứng với nó trong bảng ban đầu là bản ghi nào. Sau đó việc sắp xếp được thực hiện trực tiếp trên bảng khóa, trong quá trình sắp xếp, bảng chính không hề bị ảnh hưởng gì, việc truy cập vào bảng ghi nào đó của bảng chính vẫn có thể được thực hiện bằng cách dựa vào trường liên kết của bản ghi tương ứng thuộc bảng khóa [2]. Do khóa có vai trò đặc biệt như vậy nên sau này, khi trình bày các giải thuật, ta sẽ coi khóa như đại diện cho các bản ghi và để cho đơn giản, ta chỉ nói tới giá trị của khóa mà thôi. 18