- BÀI GIẢNG KHÁI QUÁT GIẢI THUẬT SONG SONG ThS. - Trần Nguyên Hương Nguyễn Văn Ninh 1 Chương 1 - TỔNG QUAN XỬ LÝ SONG SONG 1.1. - Khái niệm 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. - Nói cách khác: 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 nhiều bộ xử lý để giải quyết một bài toán 1.2. - Vì sao phải xử lý song song Yêu cầu của người sử dụng. - Cần thực hiện một khối lượng lớn công việc + Thời gian xử lý phải nhanh Yêu cầu thực tế. - Trong thực tế có nhiều bài toán mà máy tính xử lý tuần tự (XLTT) kiểu von Neumann không đáp ứng được. - Sử dụng hệ thống nhiều BXL để thực hiện những tính toán nhanh hơn những hệ đơn BXL. - đòi hỏi phải xử lý một khối lượng dữ liệu rất lớn ,những vấn đề về xử lý ngôn ngữ tự nhiên, nhận dạng, xử lý ảnh ba chiều (3-D), dự báo thời tiết v.v. - Hầu hết những bài toán này, những máy tính xử lý tuần tự là không đáp ứng yêu cầu thực tế.do đó cần phải có những hệ thống máy tính thật mạnh mới đáp ứng được những yêu cầu của thực tế. - Mặc dù tốc độ xử lý của các Bộ xử lý tăng nhiều trong những năm qua, nhưng do giới hạn về vật lý nên khả năng tính toán của chúng không thể tăng mãi được. - Điều này dẫn tới là muốn tăng được khả năng tính toán của các hệ thống máy tính thì đích cuối cùng là phải khai thác được khả năng xử lý song song của chúng. - Ngày càng xuất hiện nhiều bài toán mà những hệ thống đơn một bộ xử lý không đáp ứng được yêu cầu xử lý về thời gian, do đó đòi hỏi phải sử dụng những hệ thống đa bộ xử lý và đòi hỏi phải xử lý song song. - Sự khác nhau cơ bản giữa XLSS và XLTT Trong tính toán song song, một số bộ xử lý cùng kết hợp với nhau để giải quyết cùng một vấn đề cho nên giảm được thời gian xử lý vì mỗi thời điểm có thể có 2 nhiều phép toán được thực hiện đồng thời. - Trong tính toán tuần tự với một bộ xử lý thì mỗi thời điểm chỉ thực hiện được một phép toán. - Mục đích của xử lý song song là tận dụng các khả năng của các hệ đa bộ xử lý để thực hiện những tính toán nhanh hơn trên cơ sở sử dụng nhiều bộ xử lý đồng thời. - Cùng với tốc độ xử lý nhanh hơn, việc xử lý song song cũng sẽ giải quyết được những bài toán lớn hơn. - Xử lý tuần tự Xử lý song song Mỗi thời điểm chỉ thực hiện Mỗi thời điểm có thể thực hiện được được một phép toán nhiềuphép toán Thời gian thực hiện phép toán Thời gian thực hiện phép toán nhanh chậm 1.4. - Tiêu chí để đánh giá 1 thuật toán song song Đối với thuật toán tuần tự. - Thời gian thực hiện thuật toán. - Đối với thuật toán song song • Các tiêu chuẩn như thuật toán tuần tự. - Những tham số về số BXL: số BXL, tốc độ xử lý. - Khái niệm hệ thống tính toán song song Máy tính song song là một tập các tài nguyên tính toán có khả năng truyền thông và kết hợp với nhau để giải quyết các bài toán lớn trong khoảng thời gian chấp nhận được.Tài nguyên tính toán: CPU, RAM, …Máy tính song song là cách tiếp cận phổ biến nhất để xây dựng các siêu máy tính.Hệ thống tính toán song song chính là một máy tính song song. - Phân loại hệ thống tính toán song song theo mô hình Flynn SISD (Single Instruction, Single Data): giống như máy tuần tự SIMD (Single Instruction, Multiple Data): song song hóa về mặt dữ liệu MISD: Multiple Instruction, Single Data: chia sẻ bộ nhớ MIMD: Multiple Instruction, Multiple Data: máy tính song song thực sự 1.7. - Chương trình song song 3 1.7.1. - Các bước tổng quát phát triển ứng dụng song song Song song hóa Các phân tích và bài toán tuần tự giải thuật song song Cài đặt bài toán Các thư viện hỗ song song trợ lập trình song song Biên dịch và chạy Các máy tính bài toán song song song song 1.7.2. - Phân loại chương trình song song Theo mô hình truyền thông điệp Mỗi tiến trình có một vùng nhớ riêng. - Việc trao đổi dữ liệu, kết quả thực hiện dưới dạng thông điệp. - Giải thuật song song 1.8.1. - Song song hóa bài toán tuần tự 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ơn và 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ự 1.8.2. - Khả năng song song hóa Không phải giải thuật nào cũng có khả năng song song hóa. - Những giải thuật không thể song song hóa:Các tham số đầu vào cho bước i+1 chính là các kết quả đầu ra của bước thứ i.Ví dụ : bài toán Fibonaci 1.8.2. - Trình tự song song hóa Mô hình 5 pha: Xác định rõ vấn đề Phân hoạch Truyền thông Gom kết Ánh xạ - Pha 1,2,3: tìm kiếm khả năng songsong. - Pha 4,5: tối ưu tính song song 5 1.9. - Một số ví dụ về ý tưởng song song 1.9.1. - Hiện nay, nhiều ngôn ngữ lập trình song song đang được sử dụng như: Posix, MPI, OpenMP, VPM , Fortran 90, CUBE C, Occam, C-Linda, PVM với C/C. - là công cụ quan trọng cho phép chúng ta cài đặt thuật toán song song trên những mô hình máy tính hổ trợ việc xử lý song song. - Xử lý song song là một vấn đề phức tạp, khó khăn trước mắt chính là sự thay đổi về tư duy thuật toán (lâu nay chúng ta đã quen với cách nhìn vấn đề một cách tuần tự. - nhưng những gì mà lập trình song song đem lại thì thật là to lớn, không thể phủ nhận. - Trong xử lý tuần tự: ta dùng một bộ xử lý duyệt từ phần tử đầu đến phần tử cuối của mảng. - Trong xử lý song song, giả sử ta có một mô hình song song m bộ xử lý, ta chia việc cho mỗi bộ xử lý đồng thực hiện tìm kiếm, một bộ xử lý tìm kiếm trên (n div m)phần tử. - Trong quá trình thực hiện, bộ xử lý nào tìm thấy phần tử a hoặc đã duyệt qua hết rồi nhưng không tìm thấy thì phải gửi thông điệp để hệ thống xử lý nhận biết, điều khiển quá trình xử lý. - Chúng ta dễ nhận thấy là độ phức tạp của xử lý song song có thể sẽ lớn hơn xử lý tuần tự rất nhiều, bởi vì cần có sự trao đổi thông tin và sự đồng bộ các tiến 6 trìnhtrong quá trình thực hiện xử lý bài toán,vấn đề chúng ta cần quan tâm ở đây chính là thời gian thực hiện chương trình. - Một trong những mục đích chính của xử lý song song là nghiên cứu, xây dựng những thuật toán thích hợp để cài đặt trên các máy tính song song, nghĩa là phát triển các thuật toán song song nhằm giải quyết các bài toán đặt ra trong thực tế. - 7 Chương 2 - KIẾN TRÚC MÁY TÍNH SONG SONG Máy tính được xây dựng từ các khối cơ sở. - BXL xử lý dữ liệu được lưu trữ trong bộ nhớ thông qua các chỉ thị (các câu lệnh). - Trong hệ thống dữ liệu được thực hiện theo cả hai chiều, đọc và ghi vào bộ nhớ. - Hình 2-1 mô tả hoạt động của mô hình máy tính kiểu von Neumann Hình 2-1: Sự liên kết giữa bộ nhớ và bộ xử lý 2.1. - Phân loại máy tính song song 2.1.1. - Mô hình SISD (Single Instruction stream, Single Data Stream - Đơn luồng lệnh, đơn luồng dữ liệu) Máy tính loại SISD chỉ có một CPU, ở mỗi thời điểm thực hiện một chỉ lệnh và chỉ đọc, ghi một mục dữ liệu. - Mô hình SIMD (Single Instruction Stream, Multiple Data Stream - Đơn luồng lệnh, đa luồng 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ý (nhiều hơn một đơn vị) thực hiện theo một luồng các câu lệnh. - Máy tính MISD có thể thực hiện nhiều chương trình (nhiều lệnh) trên cùng một mục dữ liệu, nên còn được gọi là MPSD (đa chương trình, đơn dữ liệu). - Nhóm 1: lớp các máy tính gồm nhiều đơn vị xử lý (CU) khác nhau có thể nhận được những chỉ lệnh khác nhau để thực hiện trên cùng một mục dữ liệu. - Đây là kiến trúc khó thực hiện. - Đâ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 và đã có nhiều máy tính được sản xuất theo kiến trúc này, ví dụ: BBN Butterfly, Alliant FX, iSPC của Intel, v.v. - Kiến trúc máy tính song song 2.2.1. - Xử lý theo nguyên lý hình ống trong CPU Nguyên lý hình ống (pipelined) dựa vào phương pháp phân đoạn hoặc chia nhỏ một tiến trình tính toán thành một số đoạn nhỏ hơn để thực hiện trong các pha liên tiếp. - Ví dụ, hình 2-6 mô tả một tiến trình được phân thành 4 giai đoạn thực hiện tuần tự, nhưng có thể thực hiện song song theo nguyên lý hình ống để tăng tốc độ tính toán khi phải thực hiện nhiều tiến trình như thế. - Đa chương trình và chia sẻ thời gian 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. - Chúng ta biết rằng 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ý. - Các hệ điều hành đa chương trình luân phiên thực hiện các chương trình khác nhau. - 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 BXL 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ý. - Mô hình trừu tượng của máy tính song song Mục đích: muốn thể hiện được những khả năng tính toán của MTSS mà không quan tâm đến những ràng buộc cụ thể của những máy tính có trong thực tế. - Máy tính truy cập ngẫu nhiên song song PRAM PRAM (Parallel random-access machine. - Hình 2-7 mô tả PRAM 16 Hình 2-7: PRAM Đây cũng là mô hình tổng quát cho máy tính song song kiểu MIMD 2.2.5. - GĐ2: Chuyển tải dữ liệu: chuyển dữ liệu từ bộ nhớ tới các phần tử xử lý PE thông qua mạng đọc (Read Network). - Thực hiện câu lệnh: sử dụng PE để thực hiện các câu lệnh. - Thực hiện việc thu hồi bộ nhớ và các thiết của thread có định danh inHandle. - 42 Chương 5 - THUẬT TOÁN SONG SONG 5.1. - Khái niệm thuật toán song song Những thuật toán, trong đó có một số thao tác có thể thực hiện đồng thời được gọi là thuật toán song song. - Speedup Speedup (hệ số tăng tốc): speedup của thuật toán song song là tỷ số giữa thời gian thực hiện trong tình huống xấu nhất của thuật toán tuần tự tốt nhất và thời gian thực hiện cũng công việc đó của thuật toán song song. - Efficiency Hiệu quả (Efficiency) của thuật toán song song được tính bằng 5.2.3. - Flop Flop: một đơn vị đo tốc độ của máy tính song song. - Scalability Tính quy mô (Scalability): một thuật toán được gọi là có tính quy mô nếu như mức độ song song hóa tăng lên theo tỷ lệ ít nhất là tuyến tính với sự tăng lên của kích thước bài toán. - Thuật toán song song Tối ưu về chi phí Thuật toán song song Tối ưu về chi phí (Cost optimal parallel algorithm) là thuật toán có chi phí (độ phức tạp, thời gian tính) tương đương với thuật toán tuần tự tốt nhất. - 5.3.Cơ chế điều khiển song song, dữ liệu song song và pepiline 5.3.1. - Cơ chế dữ liệu song song (Data Parallel): Cơ chế dữ liệu song song (Data Parallel): nhiều bộ xử lý đồng thời áp dụng cùng một thao tác lên nhiều mục dữ liệu khác nhau 5.3.2. - Cơ chế điều khiển song song (Control Parallel) Cơ chế điều khiển song song (Control Parallel): nhiều bộ xử lý đồng thời áp dụng nhiều thao tác khác nhau lên nhiều mục dữ liệu khác nhau 5.4. - Câu hỏi đặt ra trước khi thiết kế thuật toán song song? 1.Việc phân chia dữ liệu cho các tác vụ như thế nào? 2.Dữ liệu được truy cập như thế nào, 3.Những dữ liệu nào cần phải chia sẻ? 44 4.Phân các tác vụ cho các tiến trình (bộ xử lý) như thế nào? 5.Các tiến trình được đồng bộ hóa ra sao? 5.5. - Cách thiết kế thuật toán song song 1. - Thực hiện song song hoá những thuật toán tuần tự: Biến đổi những cấu trúc tuần tự để tận dụng được những khả năng song song tự nhiên của tất cả các thành phần trong hệ thống xử lý. - 2.Thiết kế những thuật toán song song mới phù hợp với kiến trúc song song. - 3.Xây dựng những thuật toán song song từ những thuật toán song song đã được xây dựng cho phù hợp với cấu hình tôpô và môi trường song song thực tế. - 5.6 Một số giải thuật song song 5.6.1 Nhân ma trận với vec tơ. - Vậy khi chuyển sang 45 giải thuật song song thì độ phức tạp về thời gian của giải thuật song song sẽ như thế nào? b. - Giải thuật song song. - Cho ma trận A (n x n) Cho vec tơ x(n x 1) Số bộ xử lý hệ thống sử dụng: p=n Kết quả của việc nhân ma trận A và vec tơ x được lưu vào vec tơ y. - Để thực hiện việc nhân ma trận A và vec tơ x, giải thuật thực hiện qua các bước sau: Bước 1. - Phân chia công việc Phân chia ma trận Giải thuật song song ở đây sử dụng phương pháp phân chia ma trận A thành các khối theo hàng 1 chiều (Việc phân thành các khối theo cột 1 chiều hoàn toàn tương tự.) Ma trận A có n hàng và chúng ta có n bộ xử lý, khi đó ta phân chia mỗi hàng của ma trận A là một khối 1 chiều, và mỗi hàng đó sẽ được giao cho 1 bộ xử lý, hay nói cách khác, bộ xử lý Pi(i=0..n-1) sẽ xử lý khối thứ i trên ma trận A. - Phân chia vec tơ x Vec tơ x có n phần tử nằm trên n hàng, do đó, mỗi phần tử trên một hàng của vec tơ sẽ được phân cho bộ xử lý tương ứng với nó. - Tức là bộ xử lý Pi(i=1..n) sẽ giữ phần tử thứ i trên vec tơ x. - Truyền thông điệp Mỗi bộ xử lý thứ i chỉ chứa 1 phần tử thứ i của vec tơ x, mà trong quá trình thực hiện nhân hàng thứ i của ma trận A với vec tơ x thì lại cần toàn bộ các phần tử của x vì vậy cần có một bước để truyền tất cả phần tử trên x ở các bộ xử lý đến tất cả các bộ xử lý. - Thực hiện tính toán. - Tại mỗi bộ xử lý Pi thực hiện công việc tính toán: c. - Đánh giá độ phức tạp của giải thuật song song. - Thời gian truyền các giá trị của vecto x đến tất cả các bộ xử lý: O(n) Thời gian để thực hiện phép nhân mỗi hàng của ma trận A với vecto x trên mỗi bộ xử lý: O(n). - Tổng thời gian để thực hiện là: O(n)+O(n)=O(n). - 46 Vậy thời gian thực hiện theo giải thuật song song là tối ưu hơn. - Trong giải thuật trên, chúng ta sử dụng P bộ xử lý cho ma trận vuông cấp n. - Bài toán đặt ra nếu số bộ xử lý P