Bài giảng Tính toán song song và phân toán - Chương 6: Đánh giá thuật giải song song

11/16/12

6. Đánh giá thuật giải song song

Tính toán song song và phân tán PGS.TS. Trần Văn Lăng tvlang@vast-‐hcm.ac.vn lang@lhu.edu.vn

6.1 Độ phức tạp thời gian

1.  Độ phức tạp thời gian 2.  Speedup 3.  Eﬃciency 4.  Định luật Amdahl 5.  Chi phí thời gian

•  Để đánh gía thuật giải song song thường căn cứ •  T(n) = O(f(n)) nếu có số dương C và n0 sao cho T(n) < Cf(n), với các n > n0

•  T(n) = Ω(f(n)) nếu có số dương C và n0 sao cho T(n) vào: –  Thời gian Ynh toán (hay Time Complexity) –  Yêu cầu số bộ xử lý (hay Processor Complexity) > Cf(n), với các n > n0

11/16/12

Ngoài ra,

•  T(n) = o(f(n)) nếu với mọi số dương C, tồn tại n0 sao cho T(n) < Cf(n), với các n > n0 •  T(n) = θ(f(n)) nếu có các số dương C1, C2, n1, n2 sao cho T(n) < C1f(n), với tất cả các n > n1 và T(n) > C2f(n), với tất cả các n > n2. •  T(n) = ω(f(n)) nếu với mọi số dương C, tồn tại n0 •  Khi đó T(n) = θ(f(n)) nếu và chỉ nếu T(n) = O(f(n)) sao cho T(n) > Cf(n), với các n > n0 và T(n) = Ω(f(n))

Khi đó,

•  Và, T(n) = O(f(n)) tương đương f(n) = Ω(T(n))

•  Một thuật giải bao gồm 2 phần, phần thứ nhất có độ phức tạp là O(f1(n)), phần thứ hai là O(f2(n)).

•  Khi đó, thuật giải sẽ có độ phức tạp là •  T(n)=o(f(n)) tương đương f(n)= ω(T(n)) •  T(n)=o(f(n)) suy ra T(n)=O(g(n)) •  T(n)= ω(f(n)) suy ra T(n)= Ω(f(n)) O(Max{f1(n),f2(n)})

11/16/12

lim

= n ∞→

nT )( )( nf

•  Xét •  Một thuật giải là sự lồng nhau của 2 phần, phần thứ nhất có độ phức tạp là O(f1(n)), phần thứ hai là O(f2(n)).

•  Khi đó, thuật giải sẽ có độ phức tạp là •  Nếu L = 0, điều đó có nghĩa f(n) tăng nhanh hơn O(f1(n)xf2(n)) T(n), nên T(n) = o(g(n))

•  Nếu L = ∞, thì T(n) = ω(f(n)) •  Lếu L khác không và hữu hạn, i.e. T(n) và f(n) tăng cùng cấp độ, nên T(n) = θ(f(n))

lim n ∞→

nT )( )( nf

n 2

+ 2 n

1 2

•  Hoặc T(n) = n100, f(n) = 2n, thì T(n) = o(2n) và f(n) = ω(n100).

nT )(

nf )(

nn ( + 2

•  Xét •  Khi đó

f (100) (0)

f (x) = f (0) +

" f (0) +

" " f (0) + ... +

•  Ta có thể chứng minh điều này bằng lấy giới hạn của tỷ số T(n) và f(n), sau đó dùng khai triển L'Hopital đến số hạng thứ 100, với

x 2 2!

x100 100!

x 1!

xf )(

)( xf ʹ′

d dx

€

•  Vậy T(n) = θ(n2) •  Tương tự, P(n) là đa thức bậc m, thì P(n) = θ(nm)

11/16/12

6.2 Speedup

•  Thuật giải tuần tự với độ phức tạp theo thời gian •  Speedup của hệ thống song song không phải là

là Ts(n).

•  Thuật giải song song trên P bộ xử lý có độ phức

tạp là Tp(n)

•  Khi đó, speedup Sp(n) được định nghĩa

6.3 Eﬃciency

một số cố định. Mà phụ thuộc vào kích thước bài toán và số bộ xử lý. Thực chất là hàm của (n,P). •  Người ta thường phân Ych để đánh giá định Ynh của thuật giải song song bằng cách cố định n hoặc cố định P để vẽ các đường cong tương ứng là giá trị của speedup. Sp(n) = Ts(n)/Tp(n)

•  Eﬃciency (hiệu suất) có giá trị tối đa là 1. •  Eﬃciency cung cấp dấu hiệu về sự tận dụng có

•  Cố định n, vẽ đồ thị đường cong speedup theo P -‐ một trục là P, trục còn lại là speedup. Qua đó có thể phân Ych hiệu năng của thuật giải khi số bộ xử lý tăng lên. hiệu quả của các bộ xử lý. •  Chính vì vậy, eﬃciency Ep(n): •  Cố định P, vẽ đồ thị đường cong speedup theo n. Ep(n) = Ts(n)/pTp(n) = Sp(n)/p

Qua đó có thể nghiên cứu dáng điệu của thuật giải khi kích thước bài toán tăng lên.

11/16/12

Ví dụ: Thuật giải sàn Eratosthenses

–  Lấy số (cid:145)ếp theo còn trên sàn (là số

3).

–  Quay trở lại bước thứ hai cho đến

•  Mục (cid:145)êu (cid:146)m các số nguyên tố nhỏ hơn hay bằng

khi t2 > N.

–  Các số còn lại trên sàn là số nguyên

tố.

Thuật giải tuần tự

số nguyên dương N cho trước. –  Bắt đầu tứ số nguyên tố thứ nhất t (số 2). –  Sàn bỏ các bội của số t này kể tứ t2 cho đến N.

•  Minh họa, với N = 1000, các số

nguyên tố nhỏ hơn là 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31.

i = t2 While i <= N { Sàn số thứ i trong dãy; i = i + t; }

•  Thuật giải để sàn một số nguyên tố t nào đó được minh họa như sau:

11/16/12

Chi phí để sàn từng số nguyên tố

Số nguyên tố

Thời gian

499

331

196

137

1 −+ t

⎡ ⎢ ⎢

⎤ ⎥ ⎥

Trường thợp thứ I

•  Chi phí thời gian thực hiện của thuật giải được Ynh theo công thức:

•  Chi phí tuần tự là: 1411 •  Chi phí song song được Ynh theo số task tham gia. •  Trường hợp có 2 task tham gia giải quyết. –  Task 1: Sàn các bội của 2, 7, 17, 23, 29, 31. –  Task 2: Sàn các bội của 3, 5, 11, 13, 19.

•  Khi đó chi phí thời gian là 706 •  Speedup = 1411/706 = 1,9985

11/16/12

Trường hợp thứ II

Trường hợp thứ III

–  Task 1: Sàn các bội của 2. –  Task 2: Sàn các bội của 3, 11, 19, 29, 31. –  Task 3: Sàn các bội của 5, 7, 13, 17, 23.

–  Task 1: Sàn các bội của 2. –  Task 2: Sàn các bội của 3, ... –  Task 3: Sàn các bội của 5, ... –  Task 4: Sàn các bội của 7, ... –  ...

•  Trường hợp có 3 task tham gia giải quyết. •  Trường hợp có nhiều hơn 3 task.

•  Khi đó chi phí thời gian là 499. •  Speedup = 1411/499 = 2,8276

Kết luận

Ví dụ: Kết quả theo biểu thức

•  Khi đó chi phí thời gian vẫn là 499. •  Speedup = 1411/499 = 2,8276

Case

N. of tasks

Speedup

Efficiency

•  Xét bài toán có kích thước N trên máy P bộ xử lý. Thuật giải tuần tự có thời gian thực hiện là N + N2.

•  Giả sử có 3 thuật giải song song:

1

1,9985

0,9993

2

2,8276

0,9425

–  T1p(N) = N2/P + N –  T2p(N) = (N + N2)/P + 100 –  T3p(N) = (N + N2)/P + 0.6P2

3

2,8276

0,7069

4

2,8276

0,5655

11/16/12

•  Khi P khá lớn, thuật giải T1p, T2p có dạng như sau:

)1(

)( n

khi

⎯→⎯

∞→

NN + N

NN + 2 PNN +

)3(

)( n

khi

⎯→⎯

∞→

6,0

NN + ( ) 2 PNN +

)( n

khi

∞→

⎯→⎯

)2( SP

100

NN + 100

NN + ( ) 2 PNN

•  Xét khi N=100, P=12, Speedup = 10,8 •  Khi P tăng lên, thuật giải T3p rất xấu do

100

•  Tứ đây, với N=100 hai thuật giải T1p, T2p có

N >⇔

P 1

N P

100 P −

100

+⇔+

( PNNPNN >

)

N +⇔ P

N P

Speedup như nhau. •  Với P > 1 và khi đó nếu

•  Thì thuật giải T2p tốt hơn T1p

11/16/12

6.4 Định luật Amdahl

•  Trong một vài chương trình có nhiều đoạn khác nhau, có thể có những đoạn dễ dàng song song hóa, nhưng có những đoạn chỉ thực hiện tuần tự.

•  Khi đó, đoạn tuần tự không thể song song được, gọi là (cid:146)nh trạng bo(cid:159)le-‐neck (thắt cổ chai). •  Định luật: Một chương trình bao gồm hai đoạn, một đoạn chỉ có thể thực hiện tuần tự và một đoạn hoàn toàn có thể song song hóa. Nếu đoạn tuần tự (cid:145)êu phí phần f của tổng thời gian thi hành chương trình, thì speedup của thuật giải song song không vượt quá 1/f.

•  Để hình dung, chia thời gian thi hành Ts(n) của thuật giải tuần tự (ban đầu) thành f phần.

•  Khi đó có thể viết

n )(

)

1( −+

nT )( S

fT S

nTf )( S

−

)( n

)( nT p

fT S

) )( nTf S p

•  Nếu thuật giải luôn luôn cần 1/f tuần tự, phần còn lại có thể song song, thì thời gian thi hành thuật giải song song Tp(n) của cùng bài toán trên p bộ xử lý là:

11/16/12

)( nS p

1 1

)( nT S 1( −

≤

∀

)( nS p

)( nT S nT )( p

)( n

fT S

1 f

)

1 1( −+

− p

) )( nTf S p

6.5 Chi phí thời gian

•  Từ đây, độ tăng tốc speedup là •  Khi p khá lớn, Speedup bị chặn trên bởi 1/f

1/f

•  Chẳng hạn, phần tuần tự là 10% thì speedup tối đa •  Chi phí thời gian của thuật giải song song thông là 10.

thường bao gồm: –  Thời gian thi hành (execu,on ,me) –  Thời gian Ynh toán (computa,on ,me) –  Thời gian giao (cid:145)ếp (communica,on ,me) –  Thời gian chờ/nhàn rỗi (idle ,me)

11/16/12

Thời gian thi hành

Tuy nhiên, đôi khi

•  Thời gian thi hành T của thuật giải song song bao

•  Còn lấy tổng thời gian Ynh toán, thời gian giao (cid:145)ếp và thời gian chờ đợi của một (cid:145)ến trình thứ i bất kỳ nào đó.

T = Tcomp

i + Tcomm

i + Tidle

i comm

i comp

i idle

gồm: –  Thời gian Ynh toán –  Thời gian giao (cid:145)ếp –  Thời gian chờ

•  Thời gian của (cid:145)ến trình thực hiện chậm nhất { T

}

max i

€

Thời gian Ynh toán

•  Hoặc trung bình của tổng thời gian Ynh toán, giao •  Thời gian Ynh toán của thuật giải Tcomp là thời gian (cid:145)ếp và chờ trên tất cả các process (task). sử dụng cho những thao tác Ynh toán.

T =

Tcomp + Tcomm + Tidle

•  Thời gian Ynh toán thường phụ thuộc vào kích thước bài toán.

)

(

P−1

Tcomm

Tidle

∑ + Tcomp

∑

1 P 1 P

i=0

& ( '

# % $

11/16/12

Thời gian giao (cid:145)ếp

•  Thời gian giao (cid:145)ếp Tcomm là thời gian mà những

task sử dụng cho việc truyền các thông điệp giữa các task với nhau. •  Kích thước được biểu diễn bằng một tham số N, hoặc được biểu diễn bằng một tập hợp các tham số N1, N2, ..., Nm.

Thời gian chờ

•  Nếu thuật giải song song lặp lại việc Ynh toán, thì thời gian Ynh toán cũng sẽ phụ thuộc vào số task hay số process. •  Chi phí cuả việc gởi thông điệp giữa hai task được định vị trên những processor khác nhau có thể biểu diễn bằng hai tham số:

–  Thời gian khởi động việc truyền thông điệp ts, –  Và thời gian truyền L dữ liệu twL (trong đó tw là thời

gian truyền 1 dữ liệu

•  Một processor thường rãnh rỗi do việc thiếu công việc Ynh toán hoặc thiếu dữ liệu.

•  Vậy Tcomm = ts + twL •  Trong trường hợp thứ nhất, thời gian rãnh rỗi này có thể ngăn chặn bằng cách sử dụng kỹ thuật load balancing.

11/16/12

•  Kỹ thuật này được biết như là overlapping computa,on and communica,on, •  Trường hợp thứ hai, processor ở (cid:146)nh trạng nhàn rỗi do việc Ynh toán và truyền thông điệp đòi hỏi những dữ liệu từ xa.

•  Khi đó một Ynh toán địa phương được thực hiện đồng thời với những Ynh toán và giao (cid:145)ếp tứ xa. •  Thời gian này có thể tránh được bằng cách cho

Ví dụ: Minh họa thời gian

processor thực hiện những Ynh toán và giao (cid:145)ếp khác.

•  Hoặc tạo ra nhiều task trên một processor. Khi

•  Chúng ta xem xét một miền gồm N x N x Z điểm lưới, trong đó Z là số điểm theo phương thẳng đứng, N là số điểm theo hai phương ngang. một task làm trở ngại việc đợi dữ liệu tứ xa, nó có thể chuyển sang một task khác mà dữ liệu đã sẵn sàng thực hiện.

•  Một task tương ứng một miền con gồm N x (N/P) x Z điểm lưới, với P là số bộ xử lý (chia miền theo một phương ngang). •  Cách này (cid:145)ện lợi vì đơn giản, nhưng chỉ có hiệu qủa nếu như chi phí thực hiện một task mới ít hơn chi phí thời gian nhàn rỗi

11/16/12

•  Giả sử ở mỗi bước thời gian, mỗi task thực hiện cùng một Ynh toán tại mỗi điểm lưới.

•  Khi đó thời gian Ynh toán là •  Đối với thời gian truyền dữ liệu, mỗi task sẽ giao (cid:145)ếp với hai task lân cận (hai mặt), trong đó mỗi mặt gồm NZ phần tử, nên mỗi task trao đổi 2NZ dữ liệu.

•  Khi đó tổng chi phí truyền (cid:145)n (gửi và nhận) trên P

Tcomp = tcN2Z Trong đó tc là thời gian Ynh toán trung bình cho một điểm lưới. bộ xử lý sẽ là Tcomm = 2P(ts + tw2NZ)

•  Eﬃciency của thuật giải như sau: •  Giả sử P chia hết N,số lượng Ynh toán trên mỗi điểm lưới là hằng, thời gian chờ không đáng kể.

2 ZNt c PT

2 ZtN

NZt

2 ZNt c 2 tP +

comp

comm

2 t

NZt

+ P

2 ZN P

•  Chi phí thời gian:

11/16/12

•  Với thuật giải có chi phí thời gian và hiệu năng như

chi phí chuyển đổi giữa hai miếng dữ liệu.

–  Thời gian thi hành tăng khi tăng N, Z, tc, ts và tw.

trên, nhận xét rằng: –  Hiệu suất sẽ giảm đi khi tăng P, ts và tw. –  Hiệu suất sẽ tăng lên khi tăng N, Z và tc. –  Thời gian thi hành giảm khi tăng P nhưng bị chặn bởi

Bài giảng Tính toán song song và phân toán - Chương 6: Đánh giá thuật giải song song