Luận văn Thạc sĩ Khoa học: Một số phương pháp thiết kế thuật toán cơ bản trong tính toán song song và ứng dụng

Chia sẻ: Na Na | Ngày: | Loại File: DOC | Số trang:68

Thêm vào BST

Báo xấu

101
lượt xem 18
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong phạm vi luận văn này trình bày ba phần chính. Chương 1 trình bày tổng quan về xử lý song song, thuật toán song song và giới thiệu lập trình song song với MPI. Chương 2 trình bày về phương pháp thiết kế thuật toán tìm dãy con chung dài nhất trong tính toán song song. Chương 3 trình bày một số kết quả thực nghiệm trên dữ liệu cho chương trình song song tìm dãy con chung dài nhất.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học: Một số phương pháp thiết kế thuật toán cơ bản trong tính toán song song và ứng dụng

`ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN Ngô Thị Minh Nguyệt MỘT SỐ PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN CƠ BẢN TRONG TÍNH TOÁN SONG SONG VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ KHOA HỌC
Hà Nội Năm 2014 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN Ngô Thị Minh Nguyệt MỘT SỐ PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN CƠ BẢN TRONG TÍNH TOÁN SONG SONG VÀ ỨNG DỤNG 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ố: 62 46 01 10 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS. NGUY ỄN H ỮU ĐIỂN 2
Hà Nội Năm 2014 3
LỜI CẢM ƠN Trong quá trình tìm hiểu nghiên cứu để hoàn thành luận văn, tôi gặp không ít khó khăn, nhưng những lúc như vậy, tôi luôn nhận được sự động viên, khích lệ của thầy giáo, PGS. TS. Nguyễn Hữu Điển. Thầy đã tận tình hướng dẫn, định hướng cho tôi trong phương pháp nghiên cứu khoa học cũng như hỗ trợ tôi trong việc tìm tài liệu. Để có được những kết quả trong luận văn này, tôi xin gửi lời cảm ơn sâu sắc đến thầy giáo, PGS. TS. Nguyễn Hữu Điển, Trung Tâm Tính Toán Hiệu Năng Cao trường Đại học Khoa học Tự nhiên – Đại học Quốc gia Hà Nội. Tôi cũng xin gửi lời cảm ơn đến các thầy cô của tôi về sự dạy dỗ ân cần trong thời gian tôi học cao học tại trường Đại học KHTN ĐHQGHN. Tôi xin cảm ơn các thầy cô, các anh chị của Trung Tâm Tính Toán Hiệu Năng Cao đã tạo điều kiện và giúp đỡ tôi rất nhiều trong việc hoàn thành luận văn. Cuối cùng tôi xin cảm ơn gia đình, người thân và các bạn của tôi những người đã luôn bên cạnh, động viên và khích lệ tôi để có được kết quả như ngày hôm nay. Hà Nội, ngày 29 tháng 9 năm 2014 Người thực hiện, học viên Ngô Thị Minh Nguyệt Lớp Cao học BĐT 2008 – 2010. 4
MỤC LỤC Trang Trang phụ bìa.............................................................................................................. Mục lục....................................................................................................................... Danh mục các ký hiệu................................................................................................ Danh mục các bảng.................................................................................................... Danh mục các hình vẽ................................................................................................ ..................................................................................................................................... Danh mục các thuật toán............................................................................................ ..................................................................................................................................... MỞ ĐẦU ....................................................................................................... 15 Chương 1 – TÍNH TOÁN SONG SONG ................................................... 17 1.1. Tổng quan về xử lý song song .............................................................. 17 1.2. Các mô hình lập trình song song ........................................................... 23 1.3. Thiết kế và đánh giá thuật toán song song .......................................... 26 1.4. Mô hình lập trình truyền thông điệp – MPI song song ........................ 32 Chương 2 – SONG SONG HÓA THUẬT TOÁN TÌM XÂU CON CHUNG DÀI NHẤT ..................................................................................... 37 Chương 3 – KẾT QUẢ THỰC NGHIỆM ................................................ 57 KẾT LUẬN ................................................................................................... 66 TÀI LIỆU THAM KHẢO ........................................................................... 67 5
BẢNG THUẬT NGỮ VIẾT TẮT Thuật ngữ Tiếng Anh Nghĩa tiếng Việt CPU Central Processing Unit Bộ xử lý trung tâm DNA Deoxyribo nucleic acid Axít deoxyribosenucleic HPC High Performance Computing Tính toán/máy tính hiệu năng cao LCS Longest Common Subsequence Dãy con chung dài nhất. MIMD Multiple Instruction multiple Data Đa luồng lệnh đa luồng dữ liệu MISD Multiple Instruction Simple Data Đa luồng lệnh đơn luồng dữ liệu MPI Message Passing Interface Giao diện truyền thông điệp NUMA NonUniform Memory Access Truy cập bộ nhớ không đồng thời RNA Ribo nucleic acid Axít ribonucleic SIMD Simple Instruction Multiple Data Đơn luồng lệnh đa luồng dữ liệu SISD Simple Instruction simpleData Đơn luồng lệnh đơn luồng dữ liệu TCP Transmission Control Protocol Giao thức điều khiển truyền thông UDP User Datagram Protocol Giao thức gói người dùng UMA Uniform Memory Access Truy cập bộ nhớ đồng thời 6
DANH MỤC CÁC BẢNG Trang Trang 7 8 Bảng 2.1 Độ dài xâu ký tự của một số dữ liệu tin sinh học ....................... 39 Bảng 2.2 Ví dụ về các điểm trội trong ma trận phương án. ....................... 45 Bảng 2.3. Ví dụ về việc xây dựng lại ma trận phương án với các phần tử trội. .................................................................................................. 47 Bảng 2.4. Ví dụ về việc tìm các phần tử trội độc lập trên hai vùng khác nhau. ................................................................................................ 49 Bảng 2.4. Chia ô vùng tìm kiếm và xác định các vùng tìm kiếm đồng thời. 50 ......................................................................................................... Bảng 3.1. Dữ liệu thực nghiệm thuật toán ................................................... 57 Bảng 3.2. Bảng thống kê các loại amino axit [28] ........................................ 58 Bảng 3.3. Số phần tử trội trung bình đối với số xâu khác nhau trên bảng chữ cái 4 ký tự và độ dài xâu bằng 64: .......................................... 59 Bảng 3.4. Số phần tử trội trung bình đối với số xâu khác nhau trên bảng chữ cái 20 ký tự và độ dài xâu bằng 64: ........................................ 60 Bảng 3.5. Thời gian chạy thuật toán với độ dài xâu là 64 trên bảng chữ cái 4 ký tự (giây) .................................................................................. 60 Bảng 3.6. Thời gian chạy thuật toán với độ dài xâu là 64 trên bảng chữ cái 20 ký tự (giây): ................................................................................ 61 Bảng 3.7. Thời gian chạy thuật toán với độ dài xâu là 128 trên bảng chữ cái 4 ký tự (giây): .................................................................................. 62 7
Bảng 3.8. Thời gian chạy thuật toán với độ dài xâu là 128 trên bảng chữ cái 20 ký tự (giây): .......................................................................... 62 DANH MỤC CÁC HÌNH VẼ Trang Hình 1.1. Mô tả kiến trúc Von Neumann ....................................................... 17 Hình 1.2: Mô hình máy SISD .......................................................................... 19 Hình 1.3: Mô hình máy tính SIMD ................................................................. 20 Hình 1.4: Mô hình máy MIMD ....................................................................... 21 Hình 1.5: Máy tính chia sẻ bộ nhớ ................................................................. 22 Hình 1.6: Máy tính bộ nhớ phân tán ............................................................... 22 Hình 1.8: Mô hình truyền thông điệp ............................................................. 25 Hình 1.9: Mô hình lập trình phân hoạch dữ liệu ........................................... 26 Hình 1.10 Luật Amdahl .................................................................................. 32 Hình 1.11: Sự trao đổi thông điệp giữa hai tiến trình ................................... 33 Hình 1.12: Cấu trúc chương trình MPI .......................................................... 37 Hình 3.1. Thời gian chạy của thuật toán với 8 xâu độ dài 64 trên bảng chữ cái 4 và 20 ký tự ................................................................................ 63 Hình 3.2. Thời gian chạy của thuật toán với 2 xâu độ dài 4096 trên bảng chữ cái 20 ký tự ................................................................................ 63 Hình 3.3. Hệ số tăng tốc của thuật toán với 2 xâu độ dài 4096 trên bảng chữ cái 20 ký tự ................................................................................ 64 8
Hình 3.4. Hệ số tăng tốc của thuật toán với 8 xâu độ dài 64 trên bảng chữ cái 4 và 20 ký tự ................................................................................ 64 Hình 3.5. Hệ số hiệu quả của thuật toán với 8 xâu độ dài 64 trên bảng chữ cái 4 và 20 ký tự ................................................................................ 65 DANH MỤC CÁC THUẬT TOÁN Trang Thuật toán 2.1. Thuật toán tuần tự tìm dãy con chung dài nhất ................... 42 A ...................................................................................................................... 42 G ...................................................................................................................... 42 G ...................................................................................................................... 42 T ...................................................................................................................... 42 G ...................................................................................................................... 42 C ...................................................................................................................... 42 T ...................................................................................................................... 42 G ...................................................................................................................... 42 0 ....................................................................................................................... 42 1 ....................................................................................................................... 42 1 ....................................................................................................................... 42 1 ....................................................................................................................... 42 1 ....................................................................................................................... 42 9
1 ....................................................................................................................... 42 1 ....................................................................................................................... 42 C ...................................................................................................................... 42 0 ....................................................................................................................... 42 1 ....................................................................................................................... 42 1 ....................................................................................................................... 42 1 ....................................................................................................................... 42 1 ....................................................................................................................... 42 2 ....................................................................................................................... 42 1 ....................................................................................................................... 42 C ...................................................................................................................... 42 0 ....................................................................................................................... 42 1 ....................................................................................................................... 42 1 ....................................................................................................................... 42 1 ....................................................................................................................... 42 1 ....................................................................................................................... 42 2 ....................................................................................................................... 42 1 ....................................................................................................................... 42 T ...................................................................................................................... 42 0 ....................................................................................................................... 42 1 ....................................................................................................................... 42 1 ....................................................................................................................... 42 2 ....................................................................................................................... 42 10
2 ....................................................................................................................... 42 2 ....................................................................................................................... 42 3 ....................................................................................................................... 42 A ...................................................................................................................... 43 1 ....................................................................................................................... 43 1 ....................................................................................................................... 43 1 ....................................................................................................................... 43 2 ....................................................................................................................... 43 2 ....................................................................................................................... 43 2 ....................................................................................................................... 43 3 ....................................................................................................................... 43 C ...................................................................................................................... 43 0 ....................................................................................................................... 43 1 ....................................................................................................................... 43 1 ....................................................................................................................... 43 2 ....................................................................................................................... 43 2 ....................................................................................................................... 43 3 ....................................................................................................................... 43 3 ....................................................................................................................... 43 A ...................................................................................................................... 43 G ...................................................................................................................... 43 G ...................................................................................................................... 43 T ...................................................................................................................... 43 11
G ...................................................................................................................... 43 C ...................................................................................................................... 43 T ...................................................................................................................... 43 G ...................................................................................................................... 43 0 ......................................................................................................................43 Õ 1 ...................................................................................................................43 ←1 ....................................................................................................................43 ←1 ....................................................................................................................43 ←1 ....................................................................................................................43 ←1 ....................................................................................................................43 ←1 ....................................................................................................................43 C ...................................................................................................................... 43 0 ......................................................................................................................43 1 ......................................................................................................................43 1 ......................................................................................................................43 1 ......................................................................................................................43 1 ......................................................................................................................43 Õ 2 ...................................................................................................................43 1 ......................................................................................................................43 C ...................................................................................................................... 43 0 ......................................................................................................................43 1 ......................................................................................................................43 12
1 ......................................................................................................................43 1 ......................................................................................................................43 1 ......................................................................................................................43 2 .......................................................................................................................43 1 ......................................................................................................................43 T ...................................................................................................................... 43 0 ......................................................................................................................43 1 ......................................................................................................................43 1 ......................................................................................................................43 Õ 2 ...................................................................................................................43 ←2 ....................................................................................................................43 2 ......................................................................................................................43 Õ 3 ...................................................................................................................43 A ...................................................................................................................... 43 Õ 1 ...................................................................................................................43 1 ......................................................................................................................43 1 ......................................................................................................................43 2 ......................................................................................................................43 2 ......................................................................................................................43 2 ......................................................................................................................43 3 ......................................................................................................................43 C ...................................................................................................................... 43 13
1 ......................................................................................................................43 1 ......................................................................................................................43 1 ......................................................................................................................43 2 ......................................................................................................................43 2 ......................................................................................................................43 Õ 3 ...................................................................................................................43 3 ......................................................................................................................43 Thuật toán 2.2. Thuật toán tuần tự in ra dãy con chung dài nhất ................. 44 Thuật toán 2.3. Thuật toán tìm phần tử trội ................................................. 48 Thuật toán 2.4. Thuật toán song song tìm xâu con chung dài nhất .............. 55 14
MỞ ĐẦU Nhân loại ngày nay đang chứng kiến sự phát triển mạnh mẽ của ngành Công nghệ thông tin, một trong những ngành mũi nhọn của nhiều quốc gia trên thế giới. Sự phát triển vượt bậc của nó là kết quả tất yếu của sự phát triển các thiết bị phần cứng cũng như phần mềm tiện ích. Từ những máy tính đơn giản, tốc độ xử lý chậm, và chỉ được sử dụng trong một số lĩnh vực kỹ thuật nhất định, thì ngày nay chúng đã có khả năng tính toán và tốc độ xử lý vượt trội trở thành một công cụ không thể thiếu trong mọi lĩnh vực của đời sống. Những máy tính ra đời đầu tiên, do hạn chế về tốc độ xử lý và cơ chế vào ra dữ liệu nên việc lập trình rất khó khăn. Điều này làm cho máy tính không có khả năng sử dụng dễ dàng và phổ cập, nó chỉ được ứng dụng trong một số lĩnh vực khoa học đặc biệt. Ngày nay, cùng với sự phát triển mạnh mẽ của thiết bị lưu trữ, bộ nhớ, tốc độ xử lý và các thiết bị ngoại vi,… máy tính đã trở nên thân thiện hơn với người sử dụng, cũng như tốc độ tính toán nhanh hơn rất nhiều. Nhờ đó mà rất nhiều bài toán lớn đã có khả năng thực thi và nhiều ứng dụng được đưa ra. Tuy nhiên, một thực tế là còn rất nhiều vấn đề lớn với số lượng cần tính toán khổng lồ mà một máy tính thông thường không thể giải quyết được. Vào thập kỷ 70, các nhà khoa học đã đưa ra ý tưởng về cấu trúc song song nhằm kết hợp sức mạnh của nhiều bộ xử lý trên một máy tính, hoặc kết hợp nhiều máy tính với nhau thông qua mạng máy tính tạo thành máy song song ảo. Ngoài việc tính nhanh, các máy tính song song có độ an toàn cao hơn máy tính đơn, khi một 15
vài bộ xử lý hỏng thì máy tính song song vẫn có thể hoạt động được trong khi máy tính đơn thì không làm được điều đó. Hiện nay trên thế giới đã có những máy tính song song chứa đến hàng nghìn bộ xử lý. Để khai thác tiềm năng và sức mạnh của máy tính song song, cùng với việc thiết kế kiến trúc song song ta còn phải nghiên cứu những vấn đề quan trọng khác như hệ điều hành hỗ trợ xử lý song song, các ngôn ngữ lập trình và thuật toán song song. Việc nghiên cứu thiết kế các máy tính song song, và các thuật toán song song cũng như các ngôn ngữ lập trình hỗ trợ lập trình song song bắt đầu được quan tâm từ những năm 70, cho đến nay các ứng dụng của chúng đã lan rộng khắp các lĩnh vực của đời sống như đánh giá khả năng rủi ro về tài chính: dùng để mô hình hoá các xu hướng trên thị trường… Hỗ trợ quyết định như phân tích thị trường, dự báo thời tiết… Trí tuệ nhân tạo như thiết kế robot… Xử lý ảnh ứng dụng trong công nghệ nhận dạng… Điều khiển tự động… Trong đó bài toán có liên quan tới sắp xếp đóng một vai trò quan trọng, hay gặp trong các lời giải các bài toán tìm kiếm, tra cứu, … Do vậy việc nghiên cứu các thuật toán sắp xếp cơ bản, đặc biệt là các thuật toán song song trên bài toán sắp xếp là rất cần thiết. Trong phạm vi luận văn này trình bày ba phần chính, Chương 1 trình bày tổng quan về xử lý song song, thuật toán song song và giới thiệu lập trình song song với MPI , Chương 2 trình bày về phương pháp thiết kế thuật toán tìm dãy con chung dài nhất trong tính toán song song; Chương 3 trình bày một số kết quả thực nghiệm trên dữ liệu cho chương trình song song tìm dãy con chung dài nhât. Với thời gian tiếp cận vấn đề và lượng thông tin còn hạn chế, luận văn còn nhiều thiếu sót. Tôi rất mong nhận được sự góp ý của các thầy, các cô và các anh/chị để có thể tiếp tục phát triển đề tài đã nghiên cứu và đạt được kết quả. 16
Chương 1 – TÍNH TOÁN SONG SONG 1.1. Tổng quan về xử lý 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 (Hình 1.11.1), với một đơn vị xử lý được nối với một vùng lưu trữ làm bộ nhớ và tại một thời điểm chỉ có một lệnh được thực thi. [14] Bộ nhớ Câu lệnh Ghi dữ liệu Đọc dữ liệu Bộ xử lý Hình 1.1. Mô tả kiến trúc Von Neumann Với những bài toán yêu cầu về khả năng tính toán và lưu trữ lớn thì mô hình kiến trúc này còn hạn chế. Để tăng cường sức mạnh tính toán giải quyết các bài toán lớn có độ tính toán cao, người ta đưa ra kiến trúc mới, với ý tưởng kết hợp nhiều bộ xử lý vào trong một máy tính, hay gọi là xử lý song song hoặc kết hợp sức mạnh tính toán của nhiều máy tính dựa trên kết nối mạng (máy tính song song). 17
Kể từ lúc này, để khai thác được sức mạnh tiềm tàng trong mô hình máy tính nhiều bộ xử lý song song, cũng như trong mô hình mạng máy tính xử lý song song thì việc xây dựng thiết kế giải thuật song song là điều quan trọng. Giải thuật song song có thể phân rã công việc trên các phần tử xử lý khác nhau 1.1.1. Một số khái niệm về xử lý song song Định nghĩa vê x ̀ ử ly song song ́ Tính toán song song hay xử lý song song: là quá trình xử lý thông tin trong đó nhiều đơn vị dữ liệu được xử lý đồng thời bởi một hay nhiều bộ xử lý để giải quyết một bài toán. [1] Máy tính song song là tập hợp các bộ xử lý kết nối với nhau theo một kiến trúc xác định để cùng hợp tác hoạt động và trao đổi dữ liệu. [1] Phân biệt xử lý song song và xử lý tuần tự Trong tính toán tuần tự với một bộ xử lý thì tại mỗi thời điểm chỉ được thực hiện một phép toán. Trong tính toán song song thì nhiều bộ xử lý cùng kết hợp với nhau để giải quyết cùng một bài toán cho nên giảm được thời gian xử lý vì mỗi thời điểm có thể thực hiện đồng thời nhiều phép toán. Mục đích của xử lý song song Thực hiện tính toán nhanh trên cơ sở sử dụng nhiều bộ xử lý đồng thời. Cùng với tốc độ xử lý nhanh, việc xử lý song song cũng sẽ giải được những bài toán phức tạp yêu cầu khối lượng tính toán lớn. Vấn đề xử lý song song Liên quan trực tiếp đến kiến trúc máy tính, phần mềm hệ thống (hệ điều hành), giải thuật và ngôn ngữ lập trình, … Độ phức tạp 18
Độ phức tạp của tính toán song song không chỉ phụ thuộc vào kích cỡ của dữ liệu đầu vào mà còn phụ thuộc vào kiến trúc máy tính song song và số lượng các bộ xử lý được phép sử dụng trong hệ thống. Cài đặt giải thuật song song Để cài đặt các giải thuật song song trên các máy tính song song, phải sử dụng những ngôn ngữ lập trình song song như: OpenMP với C/C++, MPI với C/C++, v.v.. 1.1.2. Phân loại các kiến trúc của máy tinh song song 1.1.2.1. Phân loại theo kiến trúc máy tính của Flynn. Một trong những phân loại hay được nhắc tới là của Flynn – 1966 [6]. Michael Flynn phân các kiến trúc máy tính thành bốn loại dựa vào sự phân phối luông dữ liệu (data stream ) và phân phối các luồng lệnh ( instruction stream) trên mỗi bộ xử lý. Mô hình SISD (đơn luồng lệnh, đơn luồng dữ liệu) Đây chính là kiến trúc tuần tự Von Neuman , máy tính SISD chỉ có một CPU, các dòng lệnh được thực hiện một cách tuần tự. Hệ thống SISD (hình 1.2: trong đó tại mỗi thời điểm chỉ thực hiện một lệnh trên một mục dữ liệu) Hình 1.2: Mô hình máy SISD Mô hình SIMD (Đơn luồng lệnh, đa dữ liệu ) 19
Máy tính loại SIMD có một đơn vị điều khiển để điều khiển nhiều đơn vị xử lý thực hiện theo một luồng các câu lệnh. CPU phát sinh tín hiệu điều khiển tới tất cả các phần tử xử lý, những bộ xử lý này cùng thực hiện một phép toán trên các mục dữ liệu khác nhau. Hình 1.3: Mô hình máy tính SIMD Mô hình MISD (Đa luồng lệnh, đơn dữ liệu) Máy tính MISD có thể thực hiện nhiều nhiều lệnh trên cùng một mục dữ liệu, Các máy tính yêu cầu mỗi đơn vị xử lý (PU) nhận những lệnh khác nhau để thực hiện trên cùng một mục dữ liệu. 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 gọi là kiến trúc hình ống xử lýtheo vector thông qua một dãy các bước, trong đó mỗi bước thực hiện một chức năng và sau đó chuyển kết quảcho PU thực hiện bước tiếp theo Mô hình MIMD (đa luồng lệnh, đa luồng dữ liệu) Máy tính loại MIMD còn gọi là đa bộ xử lý, trong đó mỗi bộ xử lý có thể thực hiện những luồng lệnh khác nhau trên các luồng dữ liệu riêng. 20