Bài giảng Tính toán song song (Parallel computing): Chương 2 - TS. Ngô Văn Thanh

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

Thêm vào BST

Báo xấu

110
lượt xem 11
download

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

Chương 2 trình bày các vấn đề của hệ thống tính toán song song. Nội dung chính trong chương này gồm: Hiệu suất của hệ thống xử lý song song, tốc độ (speedup) và hiệu quả (efficiency) của xử lý song song, ánh xạ dữ liệu trên máy tính song song, vấn đề cân bằng tải động trên hệ thống nhiều máy tính, vấn đề lập lịch biểu trên hệ thống nhiều máy tính (multicomputers), vấn đề deadlocks.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Tính toán song song (Parallel computing): Chương 2 - TS. Ngô Văn Thanh

TS. Ngô Văn Thanh, Viện Vật lý. Chuyên ngành : Công nghệ thông tin. http://iop.vast.ac.vn/~nvthanh/cours/parcomp/
Chương 2: Các vấn đề của hệ thống tính toán song song 2.1 Hiệu suất của hệ thống xử lý song song. 2.2 Tốc độ (speedup) và hiệu quả (efficiency) của xử lý song song 2.2.1 Tốc độ (speedup) của xử lý song song 2.2.2 Hiệu quả (efficiency) của xử lý song song 2.2.3 Định luật Amdhal và Gustafson-Barsis về tốc độ và hiệu quả của xử lý song song. 2.3 Ánh xạ dữ liệu trên máy tính song song 2.4 Vấn đề cân bằng tải động trên hệ thống nhiều máy tính (multicomputers) 2.5 Vấn đề lập lịch biểu trên hệ thống nhiều máy tính (multicomputers) 2.5.1 Giải thuật Graham's List Scheduling 2.5.2 Giải thuật Coffman-Graham Scheduling 2.6 Vấn đề deadlocks @2009, Ngô Văn Thanh - Viện Vật Lý
2.1 Hiệu suất của hệ thống xử lý song song  So sánh hiệu suất của các hệ thống xử lý song song.  Tìm ra giải pháp tối ưu nhất:  Tiết kiệm thời gian.  Tiết kiệm chi phí cho phần cứng. Định nghĩa các ký hiệu:  Tổng số các bộ vi xử lý:  Tổng số các đơn vị phép tính được thực hiện bởi processors:  Đại lượng này liên quan đến công và năng lượng tính toán.  Thời gian chạy trên processors:  với  với  Tốc độ (speed-up):  Hiệu quả (efficiency): @2009, Ngô Văn Thanh - Viện Vật Lý
 Phần dư (redundance):  Phần sử dụng (utilization):  Chất lượng (quality):  Các biểu thức liên hệ: @2009, Ngô Văn Thanh - Viện Vật Lý
 Ví dụ: phép tính tổng 16 số chạy trên 8 processors.  Tổng số các phép tính : chỉ tính thời gian thực hiện các phép cộng:  Tổng số các phép tính trên 8 processors: p1 p2 p3 p4 p5 p6 p7 p8 p1 p3 p5 p7  Thời gian tính (chu trình): p1 p5  Tốc độ: p1  Hiệu quả  Phần dư và chất lượng: @2009, Ngô Văn Thanh - Viện Vật Lý
 Tổng số các phép tính kể cả thời gian thực hiện phép cộng và thời gian truyền dữ liệu giữa các processors: 22  Kết quả tính trên các processor 2,4,6 và 8 được chuyển đến các processor 1,3,5 và 7 một cách tương ứng... Các thao tác này được thể hiện bằng các mũi tên màu đỏ. Các mũi tên vàng không mất thời gian chạy.  Tổng số các phép tính: p1 p2 p3 p4 p5 p6 p7 p8 p1 p3 p5 p7  Thời gian tính (chu trình): p1 p5  Tốc độ: p1  Hiệu quả:  Phần dư và chất lượng: @2009, Ngô Văn Thanh - Viện Vật Lý
2.2 Tốc độ và hiệu quả của xử lý song song 2.2.1 Tốc độ (speedup) của xử lý song song.  So sánh thời gian tính cho một tác vụ khi chạy trên máy tính đơn và đa processor.  Một tác vụ được chia thành tác vụ con, mỗi tác vụ con sẽ được thực hiện trên một processor.  Thời gian chạy của toàn bộ tác vụ trên một processor:  Thời gian chạy một tác vụ con trên một processor:  Các tác vụ được thực hiện đồng thời trên các processors cho nên thời gian thực hiện toàn bộ tác vụ đó cũng bằng  Định nghĩa hệ số tốc độ:  Nếu xét cả thời gian truyền thông tin cho mỗi processor là @2009, Ngô Văn Thanh - Viện Vật Lý
2.2.2 Hiệu quả (efficiency) của xử lý song song  Để chuyển đơn vị tỷ lệ cho hệ số tốc độ nằm trong khoảng từ 0 đến 1, người ta định nghĩa một đại lượng khác gọi là "hiệu quả ". Chương trình có những đoạn tính tuần tự.  Giả thiết ta có f phần tác vụ không thể chia thành các tác vụ con để chạy song song, lúc đó ta có (1 – f ) phần tác vụ được tính song song. For i=1,n Tính song c(i)=a(i)+b(i) song For j=1,n Tính tuần tự sum=sum+c(j) For k=1,n Tính song a(k)=a(k)/sum song b(k)=b(k)/sum @2009, Ngô Văn Thanh - Viện Vật Lý
 Thời gian thực hiện toàn bộ tác vụ:  Tốc độ:  Hiệu quả:  Nếu xét cả thời gian truyền thông tin cho mỗi processor:  Tốc độ cực đại:  Hiệu quả: @2009, Ngô Văn Thanh - Viện Vật Lý
2.2.3 Định luật Amdhal và Gustafson-Barsis về tốc độ và hiệu quả của xử lý song song. Định luật Amdhal.  Xét trường hợp  Ta có: ở đây giá trị của f không phụ thuộc vào số lượng processor của hệ song song (kích thước chương trình không đổi). Nếu f = 1: không có sự tăng tốc độ chạy trên hệ song song. Tốc độ cực đại của hệ song song tỷ lệ nghịch với hệ số f .  Tốc độ của hệ song song có p processor tăng khi tăng số processor nhưng bị giới hạn bởi số phần các tác vụ tính tuần tự trong chương trình.  Hiệu quả: @2009, Ngô Văn Thanh - Viện Vật Lý
@2009, Ngô Văn Thanh - Viện Vật Lý
Định luật Gustafson-Barsis.  Thời gian tính tuần tự và song song lần lượt là:  Thời gian tính trên một processor (tính tuần tự):  Thời gian tính trên hệ song song:  Theo định nghĩa speed-up, ta có:  Thời gian thực hiện chương trình là không đổi:  Ta có:  Ý nghĩa của tương đương với hệ số f trong định luật Amdhal. @2009, Ngô Văn Thanh - Viện Vật Lý
Ví dụ.  Xét một chương trình có thời gian thực hiện các tác vụ tuần tự là 0.63% và thời gian thực hiện các tác vụ đồng thời là 0.33%.  Chương trình tính trên 10 processors.  Áp dụng định luật Amdhal.  Áp dụng định luật Gustafson-Barsis.  Tốc độ tính bằng định luật Gustafson-Barsis cho kết quả cỡ gấp 2 lần so với kết quả tính bằng định luật Amdhal.  Định luật Amdhal không xét đến sự phụ thuộc của độ lớn của chương trình vào số lượng processor.  Định luật Gustafson-Barsis cho thấy độ lớn của chương trình tăng khi số lượng processor tăng. @2009, Ngô Văn Thanh - Viện Vật Lý
2.3 Ánh xạ dữ liệu trên máy tính song song Các kiểu ánh xạ  Ánh xạ mảng dữ liệu 1 chiều lên mảng processor 1 chiều.  Mảng dữ liệu một chiều A gồm n phần tử.  Mảng dữ liệu được ánh xạ lên p processor.  Số phần tử dữ liệu được thực hiện trên 1 processor: @2009, Ngô Văn Thanh - Viện Vật Lý
Ví dụ mảng A(1..20) có 20 phần tử ánh xạ lên 4 processor.  Ánh xạ kiểu khối (block) A(6:10)  Ánh xạ kiểu vòng tròn (cyclic) @2009, Ngô Văn Thanh - Viện Vật Lý
 Ánh xạ mảng dữ liệu 2 chiều lên mảng processor 1 chiều.  Mảng dữ liệu hai chiều A gồm (n × n) phần tử.  Mảng dữ liệu được ánh xạ lên p processor.  Số phần tử dữ liệu được thực hiện trên 1 processor:  Mỗi một cột hoặc một hàng của mảng được ánh xạ lên 1 processor. @2009, Ngô Văn Thanh - Viện Vật Lý
 Ánh xạ mảng dữ liệu 2 chiều lên mảng processor 2 chiều.  Mảng dữ liệu hai chiều A gồm (n × n) phần tử.  Mảng dữ liệu được ánh xạ lên q = (p × p) processor cũng là một mảng 2D.  Số phần tử dữ liệu được thực hiện trên 1 processor:  Các phần tử của mảng được ánh xạ kiểu (block,block), (cyclic,cyclic) hoặc là (block,cyclic). @2009, Ngô Văn Thanh - Viện Vật Lý
 Ví dụ: A 1 2 3 4 5 6  Ánh xạ (block,block): với mảng dữ liệu A(6,6) 1 và processor P(2,2) P(1,1) chứa các phần tử: A(1,1:3), A(2,1:3), A(3,1:3) 2 P(1,1) P(1,2) P(1,2) chứa các phần tử: A(1,4:6), A(2,4:6), A(3,4:6) 3 P(2,1) chứa các phần tử: A(4,1:3), A(5,1:3), A(6,1:3) 4 P(2,2) chứa các phần tử: A(4,4:6), A(5,4:6), A(6,4:6) 5 P(2,1) P(2,1)  Ánh xạ (cyclic,cyclic) 6 A 1 2 3 4 5 6 1 P(1,1) P(1,2) P(1,1) P(1,2) P(1,1) P(1,2) 2 P(2,1) P(2,2) P(2,1) P(2,2) P(2,1) P(2,2) 3 P(1,1) P(1,2) P(1,1) P(1,2) P(1,1) P(1,2) 4 P(2,1) P(2,2) P(2,1) P(2,2) P(2,1) P(2,2) 5 P(1,1) P(1,2) P(1,1) P(1,2) P(1,1) P(1,2) 6 P(2,1) P(2,2) P(2,1) P(2,2) P(2,1) P(2,2) @2009, Ngô Văn Thanh - Viện Vật Lý
2.4 Vấn đề cân bằng tải động trên hệ thống nhiều máy tính (multicomputers).  Cân bằng tải trên các node ngay trong quá trình chạy chương trình một cách tự động.  Phân bố các tác vụ trên các processor để nâng cao hiệu quả và tốc độ của hệ máy tính song song.  Mỗi một bài toán được chia thành các tác vụ và được thực hiện bởi các chu trình.  Các chu trình được ánh xạ lên các processor sao cho các processor làm việc liên tục.  Thông thường người ta chỉ ánh xạ một tác vụ lên một processor. @2009, Ngô Văn Thanh - Viện Vật Lý
Các thuật toán  Thuật toán cân bằng tải từ trung tâm (Centralized load balancing algorithms).  Thuật toán có kiểu cấu trúc chủ-khách (master-slave).  Thuật toán này áp dụng tốt cho trường hợp chỉ có ít processor khách.  Một processor chủ nắm giữ và điều khiển tất cả các tác vụ cần thực hiện.  Processor chủ gửi các tác vụ cần thực hiện đến các processor khách (slave). Khi một processor khách nào đó đã thực hiện xong tác vụ thì nó sẽ gửi yêu cầu đến processor chủ để nhận tác vụ mới. @2009, Ngô Văn Thanh - Viện Vật Lý