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

Chia sẻ: Nguyen Nhi | Ngày: | Loại File: PDF | Số trang:32

Thêm vào BST

Báo xấu

102
lượt xem 29
download

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

Thuật toán song song 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.

Chủ đề:

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

Lưu

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

KIẾN TRÚC CÁC HỆ THỐNG TÍNH TOÁN Nguyễn Phú Bình Trần Trung Kiên Bộ môn KTMT - Khoa CNTT Trườ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án Chương 5 Thuật toán song song Nguyễn Phú Bình – Trần Trung Kiên 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 Tà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ý  5
Nhữ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") 11
12
 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ử 15
Phâ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: 19
Phân rã theo dữ liệu 20