Xử lý song song và phân tán

Chia sẻ: Nguyễn Duy Thuận | Ngày: | Loại File: DOC | Số trang:4

0
444
lượt xem
98
download

Xử lý song song và phân tán

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

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 đó.

Chủ đề:
Lưu

Nội dung Text: Xử lý song song và phân tán

  1. Bài tập Chương 3 – Xử lý song song và phân tán Câu 3.1: 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]} S1 S2 DEF(S2) = {a[i+1]}; USE(S2) = {e[i], d[i]} DEF(S3) = {a[i]}; USE(S3) = {e[i]} O Phụ thuộc dòng dữ liệu: |---| DEF(S1) ∩ USE(S2) ≠ Ø S3 DEF(S1) ∩ USE(S3) ≠ Ø Đồ thị phụ thuộc dữ liệu 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 3.2: 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. Hoàng Trần Thy Ngọc Trang 1
  2. Bài t ập Chương 3 – Xử lý song song và phân tán Câu 3.3: 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) ≠ Ø S1 S2 Phản phụ thuộc dữ liệu: O DEF(S1) ∩ USE(S1) ≠ Ø / T \ DEF(S2) ∩ USE(S2) ≠ Ø Đồ thị phụ thuộc dữ liệu 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 3.4: 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]); } Hoàng Tr ần Thy Ngọc Trang 2
  3. Bài t ập Chương 3 – Xử lý song song và phân tán Câu 3.5: 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) ≠ Ø S1 S2 T S3 S4 ----- DEF(S3) ∩ USE(S4) ≠ Ø Đồ thị phụ thuộc dữ liệu 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 3.5: 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)); } Hoàng Tr ần Thy Ngọc Trang 3
  4. Bài t ập Chương 3 – Xử lý song song và phân tán } DEF(S1) = {a, b, c}; USE(S1) = Ø DEF(S2) = Ø; USE(S2) = Ø DEF(S3) = {deta}; USE(S3) = {a, b, c} DEF(S4) = Ø; USE(S4) = Ø S1 DEF(S5) = Ø; USE(S5) = {deta, a, b, c} Phụ thuộc dòng dữ liệu: DEF(S1) ∩ USE(S3) ≠ Ø S2 S3 DEF(S1) ∩ USE(S5) ≠ Ø DEF(S3) ∩ USE(S5) ≠ Ø Phụ thuộc dữ liệu vào: |----| S5 S4 USE(S5) ∩ USE(S3) ≠ Ø Phụ thuộc điều khiển dữ liệu: Đồ thị phụ thuộc dữ liệu S2, S3 phụ thuộc vào S1 S4, S5 phụ thuộc vào S3 Hoàng Tr ần Thy Ngọc Trang 4
Đồng bộ tài khoản