TAILIEUCHUNG - Xử lý song song và phân tán
Hai chu trình trên không tương đương về nội dung tính toán. Vì ở chu trình 1 khi tính a[i] ở bước thứ i không phụ thuộc vào giá trị a[i-1] của bước thứ i-1 trước đó. Trong khi ở chu trình 2 khi tính a[i] ở bước thứ i lại phụ thuộc vào giá trị a[i-1] của bước thứ i-1 trước đó. | Câu : Xác định sự phụ thuộc dữ liệu của các lệnh trong chu trình sau : Do i = 1 to N S1: e[i] = x[i] – z[i]; S2: a[i+1] = e[i] + 2*d[i]; S3: a[i] = e[i]; End DEF(S1) = {e[i]}; USE(S1) = {x[i], z[i]} DEF(S2) = {a[i+1]}; USE(S2) = {e[i], d[i]} DEF(S3) = {a[i]}; USE(S3) = {e[i]} Phụ thuộc dòng dữ liệu: DEF(S1) ∩ USE(S2) ≠ Ø DEF(S1) ∩ USE(S3) ≠ Ø Phụ thuộc dữ liệu ra: DEF(S2) ∩ DEF(S3) ≠ Ø Phụ thuộc dữ liệu vào: USE(S2) ∩ USE(S3) ≠ Ø Câu : Hai chu trình sau có tương đương về nội dụng tính toán hay không ? Hãy bình luận về khả năng thực hiện song song của các chu trình đó. 1. Do i = 1 to N a[i] = a[i+1] + i; end 2. Do i = N downto 1 a[i] = a[i+1] + i; end Hai chu trình trên không tương đương về nội dung tính toán. Vì ở chu trình 1 khi tính a[i] ở bước thứ i không phụ thuộc vào giá trị a[i-1] của bước thứ i-1 trước đó. Trong khi ở chu trình 2 khi tính a[i] ở bước thứ i lại phụ thuộc vào giá trị a[i-1] của bước thứ i-1 trước đó. Cả hai chu trình trên dều có khả năng thực hiện song song, nhưng từ nhận xét trên ta nhận thấy khả năng thực hiện song song cho chu trình 1 dễ dàng hơn so với chu trình 2. Câu : Xác định tất cả các sự phụ thuộc dữ liệu trong đoạn chương trình sau: int a[Max]; read(a); for(i = 0; i < N; i++) for(j = 0; j < i; j++){ S1: a[i] = max(a[i], a[j]); S2: a[j] = min(a[i], a[j]); } DEF(S1) = {a[i]}; USE(S1) = {a[i], a[j]} DEF(S1) = {a[j]}; USE(S1) = {a[i], a[j]} Phụ thuộc dòng dữ liệu: DEF(S1) ∩ USE(S2) ≠ Ø Phản phụ thuộc dữ liệu: DEF(S1) ∩ USE(S1) ≠ Ø DEF(S2) ∩ USE(S2) ≠ Ø DEF(S2) ∩ USE(S1) ≠ Ø Phụ thuộc dữ liệu ra: DEF(S2) ∩ DEF (S1) ≠ Ø Phụ thuộc dữ liệu vào: USE(S2) ∩ USE(S1) ≠ Ø Câu : Loại bỏ các phụ thuộc dữ liệu ra và phản phụ thuộc dữ liệu của các chu trình sau. for(i = 0; i < N; i++){ x = a[i] + b[i]; y[i] = 2 * x; } Chu trình trên có thể được viết lại như sau để có thể loại bỏ phụ thuộc dữ liệu và phản phụ thuộc dữ liệu for(i = 0; i < N; i++){ y[i] = 2 * (a[i] + b[i]); } Câu : Phân tích đoạn chương trình sau, xác định các phụ thuộc dữ liệu và vẽ đồ thị phụ thuộc dữ liệu của đoạn chương trình đó. S1: A = B + C; for(i = 0; i < N; i++){ S2: D[i] = A + b[i]); S3: S = b[i] * 5; S4: T = T + S; } DEF(S1) = {A}; USE(S1) = {B, C} DEF(S2) = {D[i]}; USE(S2) = {A, b[i]} DEF(S3) = {S}; USE(S3) = {b[i]} DEF(S4) = {T}; USE(S4) = {T, S} Phụ thuộc dòng dữ liệu: DEF(S1) ∩ USE(S2) ≠ Ø DEF(S3) ∩ USE(S4) ≠ Ø Phản phụ thuộc dữ liệu: DEF(S4) ∩ USE(S4) ≠ Ø Phụ thuộc dữ liệu vào: USE(S3) ∩ USE(S2) ≠ Ø Câu : Viết chương trình giải phương trình bậc 2 và vẽ đồ thị phụ thuộc dữ liệu của nó. S1: Read(a,b,c); If (a == 0){ S2: Write(‘Day khong phai phuong trinh bac 2’); }else{ S3: Deta = b*b - 4*a*c; If (deta < 0){ S4: Write(‘Phuong trinh vo nghiem’); }else{ S5: Write(‘Nghiem:’, (-b – sqrt(deta))/(2*a), (-b + sqrt(deta))/(2*a)); } } DEF(S1) = {a, b, c}; USE(S1) = Ø DEF(S2) = Ø; USE(S2) = Ø DEF(S3) = {deta}; USE(S3) = {a, b, c} DEF(S4) = Ø; USE(S4) = Ø DEF(S5) = Ø; USE(S5) = {deta, a, b, c} Phụ thuộc dòng dữ liệu: DEF(S1) ∩ USE(S3) ≠ Ø DEF(S1) ∩ USE(S5) ≠ Ø DEF(S3) ∩ USE(S5) ≠ Ø Phụ thuộc dữ liệu vào: USE(S5) ∩ USE(S3) ≠ Ø Phụ thuộc điều khiển dữ liệu: S2, S3 phụ thuộc vào S1 S4, S5 phụ thuộc vào S3 Bài tập Chương 3 – Xử lý song song và phân tán Hoàng Trần Thy Ngọc Trang 1
đang nạp các trang xem trước
