Đề cương: Tính toán song song

Chia sẻ: Nguyễn Đức Mạnh | Ngày: | Loại File: DOCX | Số trang:20

Thêm vào BST

Báo xấu

75
lượt xem 6
download

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

Nhằm giúp các bạn có thêm tài liệu phục vụ nhu cầu học tập và nghiên cứu, mời các bạn cùng tham khảo nội dung đề cương "Tính toán song song" dưới đây. Nội dung đề cương cung cấp cho các bạn 14 câu hỏi bài tập về: Các mẫu thiết kế thuật toán song song, độ phức tạp của thuật toán song song, tbày mô hình phân loại Flynn,...

Chủ đề:

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

Lưu

Nội dung Text: Đề cương: Tính toán song song

Câu 1: Khái niệm xử lý tuần tự, xử lý song song, lập trình song song? - 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. - Lập trình song song: là việc lập trình sử dụng một ngôn ngữ có hỗ trợ xử lý song các lệnh trong một chương trình. Câu 2: Phân tích các nguyên nhân làm cho xử lý song song ngày càng trở nên cần thiết? Tồn tại nhiều bài toán có khối lượng tính toán rất lớn, vượt quá khả năng xử lý của một chíp đơn - CPU không thể tăng tốc độ tới vô hạn. - Chi phí sản xuất phần cứng CPU giảm thấp, cho phép chế tạo những siêu máy tính với giá thành và kích thước chấp nhận được. Câu 3: Các khái niệm máy tính song song, siêu máy tính, thông lượng, tốc độ xử lý song song? Máy tính song song: là một máy tính có nhiều bộ xử lý, có khả năng phối hợp với nhau để giải quyết bài toán. Siêu máy tính: là một máy tính đa năng có khả năng giải quyết bài toán với tốc độ tính toán cao. Thông lượng: là lưu lượng dữ liệu được truyền tải qua thiết bị trong một đơn vị thời gian. Tốc độ: là tỉ số giữa thời gian cần thiết để xử lý một thuật toán tuần tự tốt nhất trên thời gian xủ lý xen kẽ hoặc song song trên cùng một máy. Câu 4: Phân biệt khái niệm song song dữ liệu, song song điều khiển, dây chuyền. Cho ví dụ? Song song dữ liệu. Dữ liệu được phân qua các nút khác nhau để được xử lý. Các thao tác xử lý là như nhau trên cac luồng dữ liệu khác nhau. Được áp dụng với những bài toán có kích thước dữ liệu lớn. Song song điều khiển. - Nhiều đợn vị xử lý khác nhau tác động lên nhiều đơn vị dữ liệu khác nhau một cách đồng thời.
Dây truyền: - Qua giai đoạn 1 giai đoạn 2 giai đoạn 3….. giai đoạn n thì công việc, hay bài toán được hoàn thành. Giai đoạn 1 giai đoạn n: là một dây truyền. VÍ DỤ Câu 5: Phân biệt các hình thức song song: cấp bít, cấp lệnh, dữ liệu, tác vụ? Song song cấp bít - 1970 – 1986: tăng tốc trong kiến trúc máy tính bằng cách tăng gấp đôi kích cỡ từ máy (tăng khối lượng thông tin bxl có thể thao tác trên một chu kỳ). - Làm giảm số chỉ lệnh bxl phải thực thi hoạt động trên các biến có size lớn hơn độ dài từ Song song cấp lệnh: - Các câu lệnh được sắp xếp thành một nhóm lệnh và được thực thi song song mà không ảnh hưởng đến kết quả. - Đường liên kết câu lệnh đa công đoạn trong bộ xử lý hiện đại. - Đường liên kết n công đoạn có thể thực thi n câu lệnh ở những giai đoạn khác nhau. - Bộ xử lý siêu vô hướng: các lệnh được nhóm khi giữa chúng không có phụ thuộc dữ liệu. Song song dữ liệu. - Dữ liệu được phân qua các nút khác nhau để được xử lý. - Các thao tác xử lý là như nhau trên cac luồng dữ liệu khác nhau. - Được áp dụng với những bài toán có kích thước dữ liệu lớn. Song song tác vụ. - Là thuộc tính của một chương trình mà các phép tính hoàn toàn giống nhau được thực hiện trên những bộ dữ liệu khác nhau hoặc giống nhau.
Câu 6: Trình bày mô hình phân loại 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ự Câu 7: Trình bày các mô hình máy tính SISD, SIMD, MISD, MIMD, Systolic Processors? Cho ví dụ. Phân loại dựa trên tương tác giữa các dữ liệu và câu lệnh. Có bốn mô hình: SISD, SIMD, MISD, MIMD. Mô hình SISD: Mô hình một lệnh một luồng dữ liệu(máy tuần tự). Mô hình máy tính tuần tự Von Neuman: tại một thời điểm chỉ một lệnh được thực hiện. Đặc điểm:  Chỉ có một CPU.  Tại một thời điểm chỉ có một lệnh được thực hiện, một mục dữ liệu được truy xuất.  Một thanh ghi(bộ đếm chương trình) nạp địa chỉ nhóm lệnh tiếp theo.  Các lệnh được thực hiện một cách tuần tự. Ngày nay thì mô hình SISD được áp dụng cho destop và lato.
Các lệnh cũng có thể được xử lý đồng thời theo cơ chế xen kẽ dòng mã lệnh. Máy SISD cũng có thể có nhiều đơn vị: bộ xử lý toán học, bộ vecto, bộ xử lý đồ họa, các đơn vị xử lý vào ra. Tất cả các đơn vị xử lý đều được điều khiển bởi một bộ xử lý đơn. Mô hình SIMD. Đặc điểm:  Một đơn vị điều khiển(CU) điều khiển tất các các bộ xử lý p1, p2, p3…pn.  Mỗi bộ xử lý có một luồng dữ liệu riêng.  Các bộ xử lý thực hiện cùng một lệnh trên những mục dữ liệu khác nhau. Là mô hình đơn địa chỉ và đa dữ liệu.
Có thể thao tác trên các dữ liệu dạng vecto, ma trận. Các máy tính có mô hình dạng SIMD ILLIAC IV, DAP,ConnectionMachine CM–2, card xử lý đồ họa CPU. Máy tính SIMD với bộ nhớ phân tán:  Cấu trúc: gồm một bộ điều khiển và các bộ xử lý.  Các bộ xử lý hoạt động như các bộ tính toán số học thực hiện các phép toán +,-, *, /;  Mỗi bộ tính số học có vùng nhớ riêng khi hoạt động và chỉ được truy cập vào đó.  Ưu điểm: Có thể dễ dàng mở rộng bộ nhớ toàn cục, bộ nhớ riêng của từng bộ xử lý.  Nhược điểm: tốn thời gian cho việc trao đổi thông tin. Máy tình SIMD với bộ nhớ chia sẻ:  Thiết kế dựa trên sự kết hợp giữa các bộ xử lý và các modun nhớ.  Các vùng nhớ riêng của các bộ xử lý thì được thay thế bởi các modun nhớ trong bộ nhớ chung.  Các modun nhớ được chia sẻ cho các bxl qua mạng liên kết hoặc thiết bị chuyển mạch.  Ưu điểm: trao đổi thông tin nhanh giữa các bộ xử lý.  Nhược điểm: khó mở rộng các mo dun nhớ vì bị giới hạn bởi không gian địa chỉ của máy tính. Máy tính SIMD với hỗ trợ của pipeline.  Xây dựng dựa trên sự kết hợp hoạt động giữa bộ xử lý hỗ trợ bởi pipeline và bộ nhở dùng chung.
 Xử lý pipeline đọc các lệnh từ các dòng mã lệnh khác nhau và cùng thực hiện chúng trên bộ xử lý. Nhiều luồng lệnh một luồng dữ liệu. Đặc điểm của mô hình SIMD:  Một dòng dữ liệu chung duy nhất cho tất các các bxl.  Mỗi bộ xử lý thực hiện những lệnh riêng độc lập trên luồng dữ liệu đó. Xử lý Pipeline. Vd: SGK. Mô hình MISD(multiple intruction stream, single dât stream) Nhiều luồng lệnh một luông dữ liệu. Đặc điểm.  Một dòng dữ liệu chung duy nhất cho tất cả các bộ xử lý.  Mỗi bxl thực hiện những lệnh riêng, độc lập trên mục dữ liệu đó. Xử lí theo nguyên lí pipeline.
Mô hình MIMD. Nhiều luồng lệnh, nhiều luồng dữ liệu. Đặc điểm:  Kiến trúc phức tạp nhất, phổ biến nhất.  Số bxl khá lớn.  Mỗi bxl có chức năng không đồng bộ và độc lập với nhau.  Tại một thời điểm những bxl khác nhau thực hiện các lệnh khác nhau trên các mục dữ liệu khác nhau. Phân loại: có 3 loại. + Hệ đa xử lý với bộ nhớ phân tán, + Hệ đa xử lý dùng chung bộ nhớ. + Hệ đa xử lý với bộ nhớ dùng chung phân tán. Hệ đa xử lý với bộ nhớ phân tán( Multi processor system with distributed memory)  Hệ máy tính song song kết nối qua môi trường mạng( multicomputer system).  Các bxl chỉ được truy cập vào vùng nhớ cục bộ
 Dữ liệu được trao đổi qua mạng theo mô hình truyền thông điệp.  Ưu điểm: hệ thống có quy mô lớn.  Nhược điểm: khó khăn khi truyền dữ liệu.  NORMA (No remote memory access model) Hệ đa xử lý với bộ nhớ dùng chung (Multi processor system with Shared memory)  Máy tính có nhiều bộ xử lý.  Các bộ xử lý có thể truy cập vào vùng nhớ toàn cục.  Vùng nhớ toàn cục được quản lý tập trung, gồm nhiều modun nhớ.  Vùng nhớ được phân địa chỉ theo một quy tắc thống nhất.  Các bộ xử lý liên lạc qua vùng nhớ chung.
 Ưu điểm: thuận lợi khi trao đổi dữ liệu, nhanh.  Nhược điểm: việc mở rộng quy mô khó.  UMA(Uniform Memory Access Model) Hệ đa xử lý với bộ nhớ dùng chung phân tán (Multi processor system with Distributed shared memory)  Về mặt vật lý, mỗi bxl có vùng nhớ riêng  Các bxl kết nối với nhau qua mạng liên kết và có vùng nhớ chung.  NUMA (Non Uniform Memory Access model) Câu 8:Định nghĩa đồ thị phụ thuộc và ý nghĩa của nó? Đồ thị phụ thuộc: +) Tập đỉnh: biểu diễn các thao tác thực hiện trong thuật toán
+) Tập cạnh: dữ liệu được sử dụng trong thao tác, có thể là input, output, kq trung gian Đồ thị phụ thuộc có thể vô hướng hoặc có hướng +) Vô hướng: khi cạnh nối hai đỉnh không biểu diễn sự phụ thuộc dữ liệu vào/ ra. +) Có hướng: cạnh biểu thị sự phụ thuộc dữ liệu giữa các thao tác Câu 10: Phân lớp EREW, CREW, ERCW, CRCW trong mô hình PRAM Một số mô hình Pram (Li&Yesha,1989) o EREW (Exclusive Read, Exclusive Write): độc quyền đọc, độc quyền ghi.Không cho phép 2 bộ xử lý đọc hoặc ghi đồng thời vào cùng một ô nhớ. o CREW (Concurrent Read Exclusive Write): đồng thời đọc, độc quyền ghi. Các bộ xử lý có thể đọc đồng thời, nhưng không được phép ghi đồng thời vào một ô nhớ. o ERCW (Exclusive Read Concurent Write): độc quyền đọc, đồng thời ghi. Các bộ xử lý có thể ghi đồng thời, nhưng không được phép đọc đồng thời từ một ô nhớ. o CRCW (Concurent Read Concurent Write): đồng thời đọc và đòng thời ghi. Các bộ xử lý có thể đồng thời đọc ghi vào một ô nhớ. Mô hình CRCW ghi dữ liệu như sau:  Thông thường (Common): tại cùng một thời điểm tất cả các bộ xử lí phải ghi cùng một giá trị vào cùng một địa chỉ trong nhớ toàn cục.  Ngẫu nhiên (arbitrary): tại cùng một thời điểm, nếu có nhiều bộ xử lí đồng thời ghi vào một địa chỉ trong bộ nhớ toàn cục, thì môt trong số bộ xử lí đó được chọn ngẫu nhiên sẽ được ghi giá trị vào ô nhớ đó.
 Ưu tiên (priority): tại cùng một thời điểm nếu có nhiều bộ xử lí đồng thời ghi vào một địa chỉ trong bộ nhớ toàn cục, thì bộ xử lí có chỉ số nhỏ nhất sẽ được ghi giá trị vào ô nhớ đó. Một thuật toán được thiết kế cho mô hình yếu hơn có thể được thực hiện trên mô hình mạnh hơn với độ phức tạp T(n) và W(n) không thay đổi Một thuật toán được thiết kế cho mô hình mạnh hơn có thể được mô phỏng trên mô hình yếu hơn với: o Tiệm cận nhiều bộ xử lý hơn (nhiềuviệc) o Hoặc với tiệm cận nhiều thời gian hơn Ưu điểm của Pram o Sử dụng các mô hình cơ bản đồng thời o Mô hình rõ ràng:  Xác định các thao tác tại mỗi bước  Lập lịch các thao tác trên các bộ xử lý o Lược đồ thiết kế mạnh mẽ Câu 11: Khái niệm giá (cost) của quá trính tính toán trên PRAM? Giá (cost) của một quá trình tính toán trên PRAM - Giá = Độ phức tạp tính toán × Số lượng bộ xử lý tham gia tính - Trong đó độ phức tạp tính toán hay thời gian tính chính là số bước thực hiện thao tác cơ bản (với giả thiết rằng thực hiện một thao tác cơ bản tốn một đơn vị thời gian) Câu 12: Khái niệm thuật toán song song? Trình bày các pha của thuật toán song song trên mô hình PRAM? Khái niệm thuật toán song song: là một tập các tiến trình hoặc các tác vụ có thể thực hiện đồng thời và có thể trao đổi dữ liệu với nhau để kết hợp cùng giải một bài toán đặt ra
Thuật toán song song trên mô hình PRAM gồm hai pha: +) Kích hoạt các bộ xử lý +) Các bxl thực hiện cv một cách song song Câu 13: Độ phức tạp của thuật toán song song? Phân tích độ phức tạp trên: +) T(n)? (Time) +) P(n)? (Processor) +) W(n)? (Total work) Ví dụ: +) T(n) = Q(logn) +) P(n) = Q(n) +) W(n) = Q(nlogn) A1 hiệu quả hơn A2 nếu W1(n) = o(W2(n) không kể đếnT(n) của chúng Ví dụ: ◦ W1(n) = Q(n), W2(n) = Q(n*logn), khi đó A1 hiệu quả hơn Giả sử có A1 và A2 là hai thuật toán song song cho cùng một bài toán +) A1 : W1(n) work inT1(n) time +) A1 : W2(n) work inT2(n) time +) Nếu W1(n) và W2(n) cùng tiệm cận tới một hàm, khi đó A1 hiệu quả hơn A2 nếu T1(n) = o(T2(n)) Ví dụ:
W1(n) = W2(n) = Q(n) T1(n) = Q(logn);T2(n) = Q(log2n) Khi đóA1 hiệu quả hơnA2 Mô hình song song có giới hạn: việc tổng hợp và phân tích một thuật toán song song dưới mô hình có P bộ xử lý (P> 1, cố định) Mô hình song song không giới hạn: số bộ xử lý Pkhông giới hạn Nâng cao hiệu quả của thuật toán song song: +) Giảm số lượng bộ xử lý +) Giảm độ phức tạp thời gian Nick Pippenger NC: Nick’s class +) Lớp các bài toán quyết định có thể xử lý trong thời gian hàm logarit trên máy tính song song với một số đa thức các bộ xử lý. ◦ Bài toán thuộc NC nếu tồn tại c, k > 0 nếu được giải quyết trong thời gian Q(logcn) sử dụng Q(nk) bộ xử lý. Câu 14: Các mẫu thiết kế thuật toán song song? CÂY NHỊ PHÂN Ý tưởng: Xây dựng cây nhị phân cân bằng trên dữ liệu vào, thực hiện tính toán từ dưới lên. Bài toán tính tổng: Input: mảng a có n phần tử với n=2k Out: S=a1+a2+...+a Thực hiện:
n/2 phần tử xử lý thực hiện tính tổng các cặp (a1, a2), (a3, a4), ..., (an-1, an) – thực hiện trong 1 bước tính. n/4 phần tử xử lý thực hiện n/4 cặp dữ liệu,... Thuật toán Begin p=n/2 While p>0 do For i =1 to p do A(i)=A(2i-1)+A(2i); p=p/2; EndWhile End. Độ phức tạp: Với p bộ xử lý Vòng while thực hiện logn lần T(n)=O(logN) với O(N) bộxử lý trên EREW pram. Ví dụ:
POINTER JUMPING Là quá trình xử lý song song nhanh của các cấu trúc dữ liệu được liên kết (list, tree). Ý tưởng: vẽ cây có các cạnh hướng từ con tới cha.
Bài toán List Ranking: Cho danh sách liên kết đơn có n phần tử Tính hạng của mỗi phần tử (là khoảng cách từ phần tử đó tới cuối danh sách).
Thuật toán tuần tự: Độ phức tạp O(n). Song song: Gọi d là hạng của nút node: Node.d=0 nếu node.next=nil; Node.d=node.next.d +1 nếu ngược lại. Gán mỗi BXL cho mỗi node. Với mỗi node i, tính: i.d=i.d + i.next.d; i.next = i.next.next; //pointer jumping Thuật toán: List_Ranking(L) for each node i, in parallel do if i.next=nil then i.d=0; else i.d=1; while exists a node i, such that i.next!= nil do for each node i, in parallel do if i.next!=nil then i.d=i.d+i.next.d; i.next=i.next.next; Ví dụ:
Phân tích: Mỗi bước nhảy làm số danh sách xen kẽ tăng gấp đôi và độ dài của chúng giảm một nửa. Sau [logn] bước, mỗi danh sách chứa đúng 1 node.
T(n)=O(n). Nhận xét: Đồng bộ hóa rất quan trọng (bước 8: i.next=i.next.next) Thuật toán EREW W(n)= O(nlogn) vì thời gian thực thi O(logn) với O(n) bộ xử lý. Bài toán tìm đường đi giữa gốc và các nút trên cây: Dựa trên quan hệ cha–con. Thời gian: logh với h là độ cao của cây. CREW. CHIA ĐỂ TRỊ Ý tưởng: Chia bài toán ban đầu thành các bài toán con nhỏ hơn,cùng dạng. Giải quyết từng bài toán con một cách đệ quy.
Tổng hợp lời giải. Bài toán tính tổng n phần tử trong A[1..n]. Thuật toán song song: độ phức tạp O(logn) với O(n) bộ xử lý. Chia để trị Chia cá phần tử của mảng vào n/logn nhóm,mỗi nhóm có logn phần tử: k=logn; r=n/logn; rk=n=2k. r nhóm: {Nhóm 1: A1A2…Alogn Nhóm 2: Alogn+1…A2logn …} o Phân mỗi nhóm cho 1 bộ xử lý, thực hiện cộng riêng với thời gian O(logn). o Cộng kết quả các bxl với nhau theo thuật toán song song đã làm. o Độ phức tạp: O(log(n/logn) ≡ O(logn) với O(n/logn) bộ xử lý. o Mô hình: EREW PRAM.