ng 3 – X lý song song và phân tán
ậ
ươ
ử
Bài t p Ch
Do i = 1 to N
S1: S2: S3:
e[i] = x[i] – z[i]; a[i+1] = e[i] + 2*d[i]; a[i] = e[i];
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 : ộ ữ ệ ủ ự ụ ệ ị
End DEF(S1) = {e[i]};
S1
S2
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]}
O
|---|
Ph thu c dòng d li u: ữ ệ ụ ộ
S3
DEF(S1) ∩ USE(S2) ≠ Ø
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) ≠ Ø
ng v n i d ng tính toán hay không ề ộ ụ ươ ? Hãy bình lu nậ
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;
Câu 3 v kh năng th c hi n song song c a các chu trình đó. ề .2 : Hai chu trình sau có t ự ng đ ươ ủ ệ ả
ng đ ề ộ ươ
chu trình 1 khi tính chu b ở ướ ứ
end Hai chu trình trên không t ươ c th i không ph thu c vào giá tr a[i-1] c a b ộ ủ ướ ụ c th i l ị ứ ạ
i ph thu c vào giá tr a[i-1] c a b a[i] trình 2 khi tính a[i] ở c đó. Trong khi ở c đó. ng v n i dung tính toán. Vì ị ướ ộ c th i-1 tr ứ ủ ướ b ở ướ ụ c th i-1 tr ứ ướ
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 hai chu trình trên d u có kh năng th c hi n song song, nh ng t ớ ấ ự ệ ễ ậ ả ơ
Hoàng Tr n Thy Ng c ọ ầ Trang 1
ng 3 – X lý song song và phân tán
Bài t p Ch
ậ
ươ
ử
int a[Max]; read(a); for(i = 0; i < N; i++)
for(j = 0; j < i; j++){
a[i] = max(a[i], a[j]); a[j] = min(a[i], a[j]);
S1: S2:
}
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: ị ấ ả ộ ữ ệ ự ụ ạ ươ
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: ữ ệ ụ ộ
S1
S2
DEF(S1) ∩ USE(S2) ≠ Ø
Ph n ph thu c d li u: ộ ữ ệ ụ ả
O T
\
/
DEF(S1) ∩ USE(S1) ≠ Ø
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) ≠ Ø
for(i = 0; i < N; i++){
x = a[i] + b[i]; y[i] = 2 * x;
}
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. ả ộ ữ ệ ủ ộ ữ ệ ạ ỏ ụ ụ
c vi i nh sau đ có th lo i b ph thu c d li u và ể ượ t l ế ạ ể ạ ỏ ộ ữ ệ ư ụ ể ph n ph ả ụ
for(i = 0; i < N; i++){
y[i] = 2 * (a[i] + b[i]);
}
Hoàng Tr n Thy Ng c ọ ầ
Trang 2
Chu trình trên có th đ thu c d li u ộ ữ ệ
ng 3 – X lý song song và phân tán
ươ
ử
Bài t p Ch ậ
Câu 3 ng trình sau, xác đ nh các ph thu c d li u và v đ th ph ạ ươ ẽ ồ ị ữ ệ ụ ộ ị ụ
S1: A = B + C;
S2: S3: S4:
for(i = 0; i < N; i++){ D[i] = A + b[i]); S = b[i] * 5; T = T + S;
}
ng trình đó. .5 : Phân tích đo n ch thu c d li u c a đo n ch ộ ữ ệ ủ ạ ươ
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}
-----
S1
S2
S3
S4
T
Ph thu c dòng d li u: ữ ệ ụ ộ
DEF(S1) ∩ USE(S2) ≠ Ø
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) ≠ Ø
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
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ó. ế ươ ả ươ ộ ữ ệ ủ ẽ ồ ị ụ ậ
ng 3 – X lý song song và phân tán
ươ
ử
Bài t p Ch ậ
}
DEF(S1) = {a, b, c}; USE(S1) = Ø
DEF(S2) = Ø; USE(S2) = Ø
DEF(S3) = {deta}; USE(S3) = {a, b, c}
S1
DEF(S4) = Ø; USE(S4) = Ø
DEF(S5) = Ø; USE(S5) = {deta, a, b, c}
Ph thu c dòng d li u: ữ ệ ụ ộ
S2
S3
DEF(S1) ∩ USE(S3) ≠ Ø
DEF(S1) ∩ USE(S5) ≠ Ø
DEF(S3) ∩ USE(S5) ≠ Ø
S5
S4
|----| Ph thu c d li u vào: ộ ữ ệ ụ
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 ụ ộ
Hoàng Tr n Thy Ng c ọ ầ
Trang 4
S4, S5 ph thu c vào S3 ụ ộ
