KIẾN TRÚC CÁC HỆ THỐNG TÍNH TOÁN - CHƯƠNG 5

Thuật toán song song Thuật toán tuần tự là cơ sở cho các thao tác để giảiquyết các vấn đề trong các máy tính tuần tự. Thuật toán song song là cơ sở, cho biết cách thức đểgiải quyết các vấn đề bằng cách sử dụng tính toánsong song.
Nội dung trích xuất từ tài liệu:
KIẾN TRÚC CÁC HỆ THỐNG TÍNH TOÁN - CHƯƠNG 5KIẾN TRÚC CÁC HỆ THỐNG TÍNH TOÁNNguyễn Phú BìnhTrần Trung KiênBộ môn KTMT - Khoa CNTTTrường ĐH Bách Khoa Hà Nội 1 Lưu ý của tác giả Không được tự ý sao chép hay quảng bá bài giảng này khi chưa được sự đồng ý của các tác giả. Địa chỉ liên hệ của các tác giả: Nguyễn Phú Bình Email: ngphubinh@yahoo.com Mobile: 0983533925 Website: http://phubinh.vicosoft.com/ktmt Trần Trung Kiên Email: trankien_bk@yahoo.com Mobile: 0914919392 Bộ môn Kỹ thuật Máy tính Khoa Công nghệ Thông tin Trường Đại học Bách Khoa Hà Nội C1- P322, Tel: 8696125 Website: http://ktmt.shorturl.com 2 Kiến trúc các hệ thống tính toánChương 5 Thuật toán song songNguyễn Phú Bình – Trần Trung KiênBộ môn Kỹ thuật Máy tính, Khoa Công nghệ Thông tinTrường Đại học Bách Khoa Hà NộiTài liệu tham khảo:Bài giảng tính toán song song (PGS,TS Nguyễn Đức Nghĩa) 3 Thuật toán tuần tự là cơ sở cho các thao tác để giải quyết các vấn đề trong các máy tính tuần tự. Thuật toán song song là cơ sở, cho biết cách thức để giải quyết các vấn đề bằng cách sử dụng tính toán song song. 4 Một thuật toán song song bao gồm toàn bộ (hoặc một trong số) các bước sau: Xác định được những phần công việc nào được thực hiện  đồng thời Ánh xạ các phần công việc tới các tiến trình để thực hiện đồng  thời Tổ chức dữ liệu vào, ra, và các dữ liệu trung gian  Quản lý việc truy cập dữ liệu dùng chung bởi nhiều bộ xử lý  Đồng bộ các bộ xử lý  5Những khái niệm cơ bản: Phân rã bài toán (Decomposition): là quá trình chia nhỏ một vấn đề lớn thành các phần nhỏ gọi là các nhiệm vụ/công việc nhỏ (task / subjob) Các nhiệm nhỏ (task / subjob) có độ lớn tùy ý 6 Ví dụ 1 :Phân rã bài toán nhân ma trận với véc tơ Ma trận A kích thước n,n Véc tơ b Kết quả được ma trận y với: y[i]= ∑nk=1 A[i.k] . b[k] 7 Chia công việc thành n task Mỗi task thực hiện tính y[i] (i từ 1 tới n) Các task này hoàn toàn độc lập với nhau và có thể thực hiện đồng thời 8 Độ thị về sự phụ thuộc lẫn nhau giữa các nhiệm công việc (task-dependency graph): 9 VD2: Thực hiện truy vấn cơ sở dữ liệu 10 Câu truy vấn: MODEL=Civic AND YEAR=2001 AND (COLOR=Green OR COLOR=White) 1112 Tiến trình (Process): là một quá trình xử lý để thực hiện 1 task Mapping: Cơ chế để ánh xạ các task tới các process 13 Các kỹ thuật phân rã (decomposition) bài toán: Phân rã đệ qui (Recursive decomposition)  Phân rã theo dữ liệu (Data decomposition)  Phân rã theo các khả năng có thể xảy ra  (exploratory decomposition) 14 Phân rã đệ qui Phân rã đệ qui: Bài toán được chia thành các task nhỏ hơn, mỗi task nhỏ đó lại được áp dụng cách chia tương tự như vậy. Ví dụ : Sắp xếp nhanh (quick sort): -Giả sử cần sắp xếp 1 dãy A -Chọn một phần tử x trong A làm mốc (chốt) và chia A thành 2 phần A0 và A1: A0 gồm các phần từ nhỏ hơn x, A1 gồm các phần tử không nhỏ hơn x. A0 và A1 lại tiếp tục áp dụng cách thức như trên cho đến khi mỗi phần chỉ gồm 1 phần tử 15Phân rã đệ qui 16 Phân rã theo dữ liệu Phân rã theo dữ liệu: Partitioning Output Data  Partitioning Input Data  Partitioning both Input and Output Data  Partitioning Intermediate Data  17 Phân rã theo dữ liệu Phân rã theo dữ liệu đầu ra: Các phần tử dữ liệu đầu ra có thể được tính độc lập nhau  VD1: Nhận 2 ma trận:Chia theo dữ liệu đầu ra 18 Phân rã theo dữ liệu VD2: 19Phân rã theo dữ liệu 20 ...