- 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. - 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.. - 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. - 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 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. - Chƣơng 1 – TÍNH TOÁN SONG SONG. - 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.10), 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. - 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).. - 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. - Một số khái niệm về xử lý song song Định nghĩa về xƣ̉ lý 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. - Bộ nhớ. - Bộ xử lý. - 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. - 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. - Độ 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. - 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.. - 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. - 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ình 1.2: Mô hình máy SISD. - Mô hình SIMD ( Đơn luồng lệnh, đa dữ liệu. - 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.. - Hầu hết các hệ thống MIMD đều có bộ nhớ riêng và cũng có thể truy cập vào được bộ nhớ chung khi cần, do vậy giảm thiểu được sự trao đổi giữa các bộ xử lý trong hệ thống.. - Hình 1.4: Mô hình máy MIMD. - Đây là kiến trúc phức tạp nhất, nhưng nó là mô hình hỗ trợ xử lý song song cao nhất, bởi chúng có thể thực thi các lệnh khác nhau trên nhiều dòng dữ liệu khác nhau tại một thời điểm.. - Theo Flynn: có hai họ kiến trúc quan trọng cho các máy tính song song: SIMD và MIMD. - Mục tiêu của xử lý song song là khai thác đến mức tối đa các khả năng sử dụng của các thiết bị phần cứng nhằm giải quyết nhanh những bài toán đặt ra trong thực tế.. - Phân loại theo mô hình bộ nhớ. - Mô hình bộ nhớ chia sẻ. - Đặc điểm của máy tính song song loại này là các nút tính toán đều có thể truy nhập vào bộ nhớ dùng chung như là bộ nhó toàn cục. - Nhiều bộ xử lý hoạt động độc lập nhưng cùng sử dụng chung một bộ nhớ, mỗi sự thay đổi nội dung các ngăn nhớ đều được các bộ xử lý biết.. - Ưu điểm chính của mô hình này là cung cấp một vúng nhớ toàn cục do đó dễ dàng cho việc lập trình về mặt sử dụng bộ nhớ đồng thời việc trao đổi thông tin giữa các modul tính toán là tương đối nhanh chóng và dễ dàng.. - Hình 1.5: Máy tính chia sẻ bộ nhớ. - Nhược điểm của mô hình này chính là sự mất cân đối giữa CPU và bộ nhớ.. - Mô hình bộ nhớ phân tán. - Mô hình này yêu cầu một mạng truyền thông để kết nối các bộ nhớ của các bộ vi xử lý. - Ưu điểm của mô hình này là kích thước bộ nhớ cân bằng với số lượng các bộ xử lý.. - Hình 1.6: Máy tính bộ nhớ phân tán. - Nhược điểm chính của mô hình này chính là người lập trình phải tự thiết lập lấy phương thức trao đổi thông tin giữa các CPU trong quá trình tính toán mà việc này đôi khi là rất khó khăn.. - Mô hình bộ nhớ lai.. - Hầu hết các máy tính nhanh và lớn ngày nay đều xây dựng dựa trên sự kết hợp giữa kiến trúc chia sẻ bộ nhớ chung và bộ nhớ phân tán. - Sự kết hợp đó tạo nên một máy tính với tên gọi máy tính có bộ nhớ lai. - Song song hóa máy tính tuần tự. - Trong kiến trúc tuần tự có thể tận dụng tốc độ cực nhanh của bộ xử lý để thực hiện xử lý song song theo nguyên lý chia sẻ thời gian và chia sẻ tài nguyên.. - Bộ nhớ cache được xem như vùng đệm giữa bộ xử lý chính. - Sự song song hóa trong sự trao đổi dữ liệu theo cấu trúc phân cấp là cách khai thác chung để cải tiến hiệu quả xử lý của hệ hống. - Các hệ điều hành của máy tính đơn bộ xử lý cho phép thực hiện song song dựa vào cách tiếp cận phần mềm.. - Phần lớn các chương trình đều có hai phần: phần vào/ra và các thành phần tính toán trong quá trình xử lý. - Do vậy, về nguyên tắc việc phát triển những chương trình song song trên máy đơn bộ xử lý thực hiện được nếu có hệ điều hành cho phép nhiều tiến trình thực hiện, nghĩa là có thể xem hệ thống như là đa bộ xử lý.. - Các mô hình lập trình song song. - Việc đưa ra một mô hình máy tính chung cho việc lập trình giúp cho việc thiết kế giải thuật giải thuật trở nên đơn giản hơn. - Lập trình song song đưa thêm những khó khăn mới vào mô hình lập trình tuần tự. - Nếu chương trình được thực hiện ở mức thấp nhất thì không những số lệnh thực hiện là rất lớn mà nó còn phải quản lý trực tiếp quá trình thực hiện song song của hàng nghìn bộ xử lý và kết hợp hàng triệu tương tác liên bộ xử lý. - Bởi vậy khả năng trừu tượng và tính toán module là các đặc tính rất quan trọng trong lập trình song song. - Các mô hình thông dụng bao gồm:. - Mô hình chia sẻ bộ nhớ.. - Mô hình luồng.. - Mô hình truyền thông điệp.. - Mô hình song song dữ liệu.. - Mô hình chia sẻ bộ nhớ. - Trong mô hình này, nhiệm vụ cùng chia sẻ một không gian địa chỉ chung có thể được truy cập đọc ghi theo phương thức không đồng bộ.Các cơ chế khác nhau như khóa (locks) và semaphore được điều khiển để truy cập đến bộ nhớ toàn cục.. - Nhược điểm của mô hình này là khó giữ lại được tính nguyên thủy của dữ liệu khi mà nhiều bộ xử lý dùng cùng dữ liệu này.. - Lợi thế của mô hình là người lập trình không cần chỉ định việc truyền sữ liệu giữa các task. - Mô hình luồng. - Trong mô hình luồng chương trình chính được chia thành các nhiệm vụ. - Và bất kì luồng nào cũng có thể thực hiện bất kì thủ tục con nào tại cùng thời điểm với các luồng khác.Trong mô hình luồng các luồng kết nối với nhau thông qua bộ nhớ toàn cục. - Đoàn Văn Ban, Nguyễn Mậu Hân (2006), Xử lý song song và phân tán, NXB KHKT.