Đề tài: ỨNG DỤNG LẬP TRÌNH SONG SONG GIẢI QUYẾT BÀI TOÁN SẮP XẾP BẰNG PHƯƠNG PHÁP TRỘN (MERGE SORT)

Trong những năm gần đây, mặc dù nền Công nghệ thông tincủa thế giới ngày một phát triển. Tốc độ xử lí máy tính ngày càngtăng lên. Tuy nhiên, chúng ta cũng gặp phải khó khăn trong một sốbài toán có dữ liệu đầu vào lớn (bài toán dự báo thời tiết, dự báođộng đất, …). Với dữ liệu đầu vào là một con số rất lớn, dù máytính có tốc độ lớn, bộ nhớ nhiều vẫn vấp phải yêu cầu phải giảiquyết bài toán trong thời gian chấp nhận được.Trong nhiều năm qua, các nhà khoa học đã nghĩ...
Nội dung trích xuất từ tài liệu:
Đề tài: ỨNG DỤNG LẬP TRÌNH SONG SONG GIẢI QUYẾT BÀI TOÁN SẮP XẾP BẰNG PHƯƠNG PHÁP TRỘN (MERGE SORT) TIỂU LUẬN MÔN HỌC CÁC KỸ THUẬT HIỆN ĐẠI TRONG CNTTNội dung:ỨNG DỤNG LẬP TRÌNH SONG SONG GIẢI QUYẾT BÀI TOÁNSẮP XẾP BẰNG PHƯƠNG PHÁP TRỘN (MERGE SORT) Phú Thọ, tháng 05-2011 MỤC LỤCTIỂU LUẬN MÔN HỌC..................................................................................1 CÁC KỸ THUẬT HIỆN ĐẠI TRONG CNTT............................................. 1 2 LỜI M Ở Đ Ầ U Trong nh ữ ng năm g ầ n đây, m ặ c dù n ề n Công ngh ệ thông tinc ủ a th ế gi ớ i ngày m ộ t phát tri ể n. T ố c đ ộ x ử lí máy tính ngày càngtăng lên. Tuy nhiên, chúng ta cũng g ặ p ph ả i khó khăn trong m ột s ốbài toán có d ữ li ệ u đ ầ u vào l ớ n (bài toán d ự báo th ời ti ết, d ự báođ ộ ng đ ấ t, …). V ớ i d ữ li ệ u đ ầ u vào là m ộ t con s ố r ấ t l ớ n, dù máytính có t ố c đ ộ l ớ n, b ộ nh ớ nhi ề u v ẫ n v ấ p ph ả i yêu c ầ u ph ả i gi ả iquy ế t bài toán trong th ờ i gian ch ấ p nh ậ n đ ượ c. Trong nhi ề u năm qua, các nhà khoa h ọ c đã nghĩ ra bi ện phápgi ả n quy ế t hi ệ u qu ả đó là chia nh ỏ bài toán ra thành nhi ều bàitoán. Vi ệ c gi ả i quy ế t các bài toán nh ỏ đ ượ c ti ế n hành đ ồ ng th ờiv ớ i nhi ề u máy tính. K ế t qu ả c ủ a bài toán l ớ n s ẽ đ ượ c gi ả i quy ếtkhi t ấ t c ả các bài toán nh ỏ đã đ ượ c làm. Các máy tính ti ế n hành x ử lí song song đ ượ c k ế t n ố i v ớ i nhauthành các c ụ m tính toán t ố c đ ộ cao. 3 N Ộ I DUNG I.MÔ T Ả GI Ả I THU Ậ T SONG SONG1. Giới thiệu Hiện nay, để giải quyết các bài toán lớn người ta thường nghĩ đến việcsử dụng các siêu máy tính hoặc việc kết hợp nhiều máy tính với nhau để tínhtoán. Tuy nhiên, với phương pháp lập trình cổ điển thì không thể nào pháttriển được chương trình có thể tận dụng được sức mạnh của các hệ thốngđó. Đó chính là lý do lập trình song song ra đời. Lập trình song song là một công việc rất phức tạp so với lập trình tuầntự thông thường, người phát triển phải thực hiện một quá trình “song songhóa”, biến đổi các chương trình tuần tự thành chương trình song song có khảnănG tận dụng tối đa sức mạnh của hệ thống.2. Nguyên lý thiết kế thuật toán song song2.1. Cách thức xây dựng một chương trình song song và phân bố Phát triển thuật toán là một phần quan trọng trong việc giải quy ết v ấnđề khi sử dụng máy tính . Một thuật toán song song là một ph ương pháp gi ảiquyết vấn đề dựa trên việc sử dụng nhiều bộ xử lý . Tuy nhiên đ ể ch ỉ rađược một thuật toán song song không đơn giản chỉ ra từng bước cụ thể, mà làở một mức độ nào đó thuật toán song song phải được them vào tính đồng th ờivà người thiết kế ra thuật toán cũng phải chỉ ra tập hợp những bước xử lýđồng thời , điều này sẽ tận dụng được khả năng tính toán của các máy tínhsong song. Trên thực tế việc thiết kế ra một thuật toán song song là kháphức tạp,gồm các công việc: Chỉ ra phần của công việc có thể thực thi đồng thời Ánh xạ các phần của công việc vào nhiều bộ xử lý chạy song song Phân tán dữ liệu nhập, xuất và trung gian cùng với chương trình Quản lý truy cập vào dữ liệu chung giữa các bộ xử lý Đồng bộ hóa các bộ xử lý khi thực thi các chương trình song song2.2. Thiết kế thuật toán song song 4 Thuật toán song song là một tập các tiến trình (process) hoặc các tác vụ(task) có thể thực hiện đồng thời và có thể trao đổi dữ liệu với nhau để kếthợp cùng giải một bài toán đặt ra. Thiết kế giải thuật song song là chia bài toán thành các bài toán nhỏ hơnvà gán bài toán nhỏ cho các bộ vi xử lý khác nhau để thực hiện song song.Quátrình thiết kế giải thuật song song là quá trình song song hóa bài toán tuần tự. Nguyên lý cơ bản trong thiết kế giải thuật song song bao gồm:2.2.1. Nguyên lý lập lịch: Giảm tối thiểu các bộ xử lý sử dụng trong thuật toán sao cho thời giantính toán là không tăng (xét theo khía cạnh độ phức tạp). Nghĩa là, nếu độphức tạp tính toán của thuật toán là O(f(n)) thì thời gian thực hiện củachương trình có thể tăng khi số bộ xử lý giảm, và thời gian tính toán tổng thểtăng lên một hằng số nào đó - nhưng vẫn là O(f(n)).2.2.2. Nguyên lý hình ống: Nguyên lý này được áp dụng khi bài toán xuất hiện một dãy các thao tác{T1, T2, . . ., Tn },trong đó Ti+1 thực hiện sau khi Ti kết thúc.2.2.3. Nguyên lý chia để trị: Tức là chia bài toán thành những phần nhỏ hơn tương đối độc lập vớinhau và giải quyết chúng một cách song song. Tạo ra một mô hình cây phâncấp để phân cấp quá trình truyền thông và tính toán. - Tăng tính song song so với mô hình trước - Thời gian chạy giảm từ O(n) xuống O(logn)2.2.4. Nguyên lý đồ thị phụ th ...