Bài giảng Tính toán song song - Chương 2: Các vấn đề của hệ thống tính toán song song - Ngô Văn Thanh

TS. Ngô Văn Thanh, Viện Vật lý. Chuyên ngành : Công nghệ thông tin. 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:  Thời gian tính (chu trình):  Tốc độ:  Hiệu quả  Phần dư và chất lượng: p5p1 p1 p3p1 p5 p7 p8p7p6p5p4p3p2p1 @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:  Thời gian tính (chu trình):  Tốc độ:  Hiệu quả:  Phần dư và chất lượng: p5p1 p1 p3p1 p5 p7 p8p7p6p5p4p3p2p1 @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 c(i)=a(i)+b(i) For j=1,n sum=sum+c(j) For k=1,n a(k)=a(k)/sum b(k)=b(k)/sum Tính song song Tính song song Tính tuần tự @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)  Ánh xạ kiểu vòng tròn (cyclic) @2009, Ngô Văn Thanh - Viện Vật Lý A(6:10)  Á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ụ:  Ánh xạ (block,block): với mảng dữ liệu A(6,6) 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) P(1,2) chứa các phần tử: A(1,4:6), A(2,4:6), A(3,4:6) P(2,1) chứa các phần tử: A(4,1:3), A(5,1:3), A(6,1:3) P(2,2) chứa các phần tử: A(4,4:6), A(5,4:6), A(6,4:6)  Ánh xạ (cyclic,cyclic) A 1 2 3 4 5 6 1 P(1,1) P(1,2)2 3 4 P(2,1) P(2,1)5 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ý  Thuật toán cân bằng tải phân bố (distributed load balancing algorithms).  Các chu trình có thể tự tác động lẫn nhau để thực hiện các tác vụ của chương trình. Cuối cùng, các chu trình được đưa về một chu trình duy nhất.  Một processor có thể trao đổi thông tin với các processor bên cạnh nó.  Mỗi một processor có thể nhận các tác vụ từ các processor khác và nó cũng có thể gửi các tác vụ đến các processor xung quanh. @2009, Ngô Văn Thanh - Viện Vật Lý  Thuật toán chuyển tác vụ giữa các chu trình.  Sender initiated load balancing algorithm Một chu trình sẽ gửi các tác vụ đến các chu trình khác khi mà nó có quá nhiều tác vụ cần phải thực hiện. Để có thể chuyển các tác vụ thì nó phải được các chu trình nhận cho phép, tức là các chu trình nhận phải còn trống. Thuật toán này áp dụng tốt cho các hệ có tải thấp.  Receiver initiated load balancing algorithm Một chu trình có ít tác vụ hoặc không có các tác vụ thì nó có thể gửi yêu cầu đến các chu trình khác để nhận thêm các tác vụ. Thuật toán này áp dụng tốt cho các hệ có tải cao, tuy nhiên hạn chế của thuật toán này đó là khó xác định tải của các chu trình. @2009, Ngô Văn Thanh - Viện Vật Lý 2.5 Vấn đề lập lịch biểu trên hệ thống nhiều máy tính (multicomputers).  Xác định thứ tự gán các tác vụ lên các phần tử xử lý để có hiệu quả cao và tối ưu nhất.  Hiệu năng: liên quan đến chất lượng của việc gán các tác vụ. Thời gian thực hiện chương trình càng ngắn thì hiệu năng càng cao.  Hiệu quả (hiệu suất): liên quan đến thuật giải của việc lập lịch biểu, nó được tính dựa trên mức độ phức tạp của thuật toán. Thuật toán càng đơn giản thì hiệu quả càng cao.  Một chương trình lập lịch biểu bao gồm:  Các tác vụ của chương trình (program tasks).  Máy tính mục tiêu (target machine).  Lập lịch biểu (schedule).  Tác vụ chương trình: các ký hiệu  Tập hợp các tác vụ cần phải thực hiện  Thứ tự thực hiện các tác vụ: "<" ( tác vụ i được thực hiện trước tác vụ j)  Ma trận giao tiếp dữ liệu (là một ma trận ): số lượng dữ liệu chuyển từ tác vụ thứ i sang tác vụ thứ j.  Vector số lượng các phép tính cho mỗi một tác vụ : @2009, Ngô Văn Thanh - Viện Vật Lý Sơ đồ tác vụ G = (T, E) gồm một tập các node (tác vụ) T và các mũi tên E. Mũi tên (i, j) nối giữa hai tác vụ thể hiện tác vụ ti cần phải hoàn thành trước tác vụ tj. Mỗi một tác vụ ti có Ai phép tính (là các chỉ thị hoặc các toán tử). Mỗi một mũi tên nối giữa tác vụ ti và tj liên quan đến đại lượng Dij (kích thước hay lượng thông tin truyền từ ti sang tj). @2009, Ngô Văn Thanh - Viện Vật Lý  Máy tính mục tiêu (targer machine):  Gồm có m processor không đồng nhất được kết nối với nhau qua kết nối mạng cục bộ (interconnection network).  Mỗi một processor được ký hiệu là Pi và có tốc độ là Si.  Sơ đồ cho máy tính mục tiêu là các đường thẳng vô hướng nối giữa các processor, nó thể hiện tốc độ truyền dữ liệu Rij giữa hai processor Pi và Pj . (số đơn vị dữ liệu truyền đi trong một đơn vị thời gian).  Lập lịch biểu (schedule).  Dựa trên sơ đồ các tác vụ G = (T, E) và sơ đồ máy tính mục tiêu, xây dựng hàm ánh xạ f để ánh xạ mỗi phần tử tác vụ lên một phần tử xử lý.  Nếu : được lập biểu để thực hiện trên processor Pi tại thời điểm t.  Thời gian chạy và độ trễ do quá trình truyền dữ liệu: @2009, Ngô Văn Thanh - Viện Vật Lý 2.5.1 Giải thuật Graham's List Scheduling.  Gán và sắp xếp các tác vụ lên các processor với mức ưu tiên khác nhau.  Mức độ ưu tiên sẽ được tính bằng tổng số các node phía sau được liên kết với nó. Ví dụ như mức ưu tiên của node g là 3. Thuật toán: 1. Dựa vào sơ đồ các tác vụ, lập bảng mức ưu tiên cho các tác vụ, sắp xếp theo thứ tự giảm dần. 2. Gán các tác vụ lên các processor theo thứ tự giảm dần của mức ưu tiên. Ví dụ:  Tác vụ a có mức ưu tiên là 8, tác vụ b có mức ưu tiên là 6.  Gán các tác vụ lên các processor: Chu trình 1 gán tác vụ a và b. Chu trình 2 gán tác vụ c, d và e Chu trình 3 gán tác vụ g và f @2009, Ngô Văn Thanh - Viện Vật Lý 2.5.2 Giải thuật Coffman-Graham Scheduling.  Lập lịch biểu cho các tác vụ trên máy tính chỉ có 2 processor (kiểu shared memory parallel). Thuật toán: 1. Gán giá trị 1 cho một trong những tác vụ cuối x nào đó. 2. Giả sử có một tập hợp nhãn 1, 2, . . . , (j - 1) đã được gán cho các tác vụ. - Đặt S là tập các tác vụ chưa được gán nhãn. - Với mỗi một node x trong S, tính giá trị L(y1), L(y2), . . . , L(yk) là giá trị của nhãn đã được gán cho các node lân cận của x. - Định nghĩa hàm là tập hợp các phần tử theo thứ tự giảm dần của L(y): - Gán nhãn với các giá trị cho các node trong S theo thứ tự tăng dần của . tức là nếu thì ta sẽ gán j cho . 3. Thực hiện bước 2 cho đến khi tât cả các tác vụ được dán nhãn. @2009, Ngô Văn Thanh - Viện Vật Lý  Ví dụ:  Hai node j và k cuối cùng được gán nhãn 1 và 2.  Tại mức lân cận, xác định  Vì nên ta gán nhãn 3 cho i và 4 cho h.  Vì ta gán nhãn 5, 6, 7 cho các tác vụ g, e, f.  Tiếp tục áp dụng thuật toán cho đến khi tất cả các tác vụ được gắn nhãn.  Cuối cùng là sơ đồ phân bố các tác vụ lên các processor theo thứ tự giảm dần của nhãn. @2009, Ngô Văn Thanh - Viện Vật Lý 2.6 Vấn đề deadlocks.  Trong các quá trình truyền thông tin kiểu message passing, nếu một trong hai thông tin là phần nguồn của thông tin kia thì cả hai thông tin đều bị khóa.  Hiện tượng này xuất hiện khi các phần nguồn phụ thuộc lẫn nhau dạng vòng tròn. Phương pháp đơn giản nhất để giải quyết vấn đề deadlook là thay đổi lộ trình (hoặc loại bỏ lộ trình) đối với các thông tin bị khóa. @2009, Ngô Văn Thanh - Viện Vật Lý  Sơ đồ chờ - Wait-for graph (WFG):  Để xác định deadlock, người ta sử dụng WFG để tìm các vòng tròn phụ thuộc lẫn nhau giữa các thông tin.  Mũi tên nối từ P11 sang P21 có nghĩa là chu trình P11 bị khóa và nó chờ nguồn từ P21. @2009, Ngô Văn Thanh - Viện Vật Lý  Các mô hình deadlock:  Mô hình deadlock đơn: chu trình chỉ chờ duy nhất một nguồn: Mỗi một node trên sơ đồ chờ chỉ có một mũi tên đi ra: P44  Mô hình AND : một chu trình nào đó phải chờ đồng thời hai nguồn khác nhau từ 2 chu trình khác. Chu trình P11 và P24 thuộc mô hình AND. @2009, Ngô Văn Thanh - Viện Vật Lý  Mô hình OR : một chu trình nào đó chỉ chờ một trong các nguồn khác.  Giả sử tất cả các node trên hình vẽ đều là node OR, lúc đó P11 không phải là deadlock vì nó có thể nhận nguồn từ P21 hoặc P32. @2009, Ngô Văn Thanh - Viện Vật Lý