T R N G ĐI H C B ÁC H K H O A H À N IƯỜ Ạ Ọ Ộ
VI N CÔNG NGH THÔNG TIN VÀ TRUY N THÔNGỆ Ệ Ề
BÀI T P L N MÔN H CẬ Ớ Ọ
CÁC K THU T HI N ĐI TRONG CNTTỸ Ậ Ệ Ạ
MÔ PH NG HI U NĂNG CAOỎ Ệ
Đ tài: ề
“Conservative Synchronization of Large-Scale Network Simulations”
(Đng b th n tr ng trong mô ph ng m ng truy n thông quy mô l n)ồ ộ ậ ọ ỏ ạ ề ớ
- Gi ng viên h ng d nả ướ ẫ : TS. Ph m Đăng H iạ ả
- H c viên th c hi nọ ự ệ : H Th L i (CA150114)ồ ị ợ
Đoàn Vũ Giang (CA150108)
Nguy n Th Thu Huy n (CB140170)ễ ị ề
- Môn h cọ: Chuyên đ 2ề
- Mã h c ph nọ ầ : IT6190
- Chuyên ngành : Công ngh thông tinệ
Conservative Synchronization of Large-Scale Network Simulations
- Hà N i: 8/2015 -ộ
2
Conservative Synchronization of Large-Scale Network Simulations
M C L CỤ Ụ
L I M ĐUỜ Ở Ầ .............................................................................................................. 4
1. T NG QUANỔ ............................................................................................................ 5
2. GI I THI U BÀI BÁOỚ Ệ ............................................................................................ 5
3. PHÂN TÍCH CÁC MÔ HÌNH CMB ......................................................................... 6
3.1. Null – message ..................................................................................................... 7
3.2. Thu t toán lazy CMB null-message:ậ ................................................................... 8
3.3. T i u hoá thu t toán lazy null – messageố ư ậ .......................................................... 9
3.4. Đng b hóa mô ph ng quy mô l nồ ộ ỏ ớ ................................................................. 11
4. ÁP D NG MÔ HÌNH PHÂN TÍCH NULL MESSAGE Đ D ĐOÁN HI UỤ Ể Ự Ệ
SU T MÔ PH NGẤ Ỏ ..................................................................................................... 11
4.1. Mô hình đng c s (Baseline)ườ ơ ở ....................................................................... 11
4.2. Nh ng k ch b n khác nhau cho mô hình baseline ữ ị ả ........................................... 12
4.3. N n t ng ph n c ng và ph n m mề ả ầ ứ ầ ề ................................................................. 13
4.4. c l ng Null-messageƯớ ượ .................................................................................. 13
4.5. c tính ch s OverheadƯớ ỉ ố ................................................................................. 14
4.6. Kh năng m r ng c a thu t toán CMBả ở ộ ủ ậ .......................................................... 15
5. PH N M M MÔ PH NG NETWORK SIMULATION (NS)Ầ Ề Ỏ ............................... 16
5.1. Gi i thi u ph n m m mô ph ng NS ớ ệ ầ ề ỏ ............................................................... 16
5.2. Đi t ng đc mô ph ng:ố ượ ượ ỏ ............................................................................. 17
5.3. Dùng C++ và Otcl đ xây d ng NS:ể ự ............................................................... 18
5.4. C u trúc cây th m c NSấ ư ụ ................................................................................. 18
5.5. Môi tr ng làm c a NS:ườ ủ ................................................................................... 18
6. K T LU NẾ Ậ .............................................................................................................. 19
L I C M NỜ Ả Ơ ............................................................................................................ 20
3
Conservative Synchronization of Large-Scale Network Simulations
TÀI LI U THAM KH OỆ Ả ........................................................................................... 21
L I M ĐUỜ Ở Ầ
Mô ph ng tin h c (Computer simulation) là các ch ng trình máy tính, m ngỏ ọ ươ ạ
máy tính đ mô ph ng m t mô hình tr u t ng c a m t h th ng c th thôngể ỏ ộ ừ ượ ủ ộ ệ ố ụ ể
qua các hi n t ng, các s ki n trong th c t ho c s li u đã có nh các đi uệ ượ ự ệ ự ế ặ ố ệ ư ề
ki n th i ti t, các ph n ng hoá h c, các quá trình sinh h c và các s li u kinhệ ờ ế ả ứ ọ ọ ố ệ
t …. Quy mô c a s ki n đc mô ph ng b ng mô ph ng tin h c đã v t xaế ủ ự ệ ượ ỏ ằ ỏ ọ ượ
b t c đi u gì có th (ho c th m chí có th t ng t ng) so v i cách s d ngấ ứ ề ể ặ ậ ể ưở ượ ớ ử ụ
mô hình toán h c truy n th ng gi y và bút.ọ ề ố ấ
Đã có r t nhi u nh ng bài báo, nh ng cu c h i th o l n trao đi, nghiên c uấ ề ữ ữ ộ ộ ả ớ ổ ứ
v mô ph ng song song và phân tán nh Parallel and Distributed Simulation,ề ỏ ư
Winter Simulation Conference, Computer Simulation Methods and Applications,…
Các tác gi Alfred Park, Kalyan S. Perumalla và đc bi t là Richard M. Fujimotoả ặ ệ
là nh ng nhân t tích c c, đóng góp r t nhi u k t qu nghiên c u trong lĩnh v cữ ố ự ấ ề ế ả ứ ự
này. Trong đó có bài báo “Conservative Synchronization of Large-Scale
Network Simulations” (Đng b th n tr ng trong mô ph ng m ng truy nồ ộ ậ ọ ỏ ạ ề
thông quy mô l nớ) đc in trong K y u c a H i th o l n th 18 v mô ph ngượ ỷ ế ủ ộ ả ầ ứ ề ỏ
song song và phân tán (PADS'04), t p chí IEEE năm 2004.ạ
Trong ph m vi bài t p l n môn h c, ti u lu n s trình bày các n i dung đcạ ậ ớ ọ ể ậ ẽ ộ ượ
đ c p đn trong bài báo, trên c s c a chuyên đ v các thu t toán mô ph ngề ậ ế ơ ở ủ ề ề ậ ỏ
song song th n tr ng.ậ ọ
4
Conservative Synchronization of Large-Scale Network Simulations
1. T NG QUANỔ
K thu t mô ph ng song song theo s ki n r i r c hi n nay đã cho phép ngỹ ậ ỏ ự ệ ờ ạ ệ ứ
d ng v i các mô hình m ng truy n thông quy mô l n (ch a t i hàng tri u thi t bụ ớ ạ ề ớ ứ ớ ệ ế ị
đu cu i và thi t b chuy n m ch). Tuy nhiên, hi u su t mô ph ng song song có thầ ố ế ị ể ạ ệ ấ ỏ ể
b gi m xu ng đáng k n u không s d ng nh ng thu t toán đng b thích h p. ị ả ố ể ế ử ụ ữ ậ ồ ộ ợ
N i dung bài báo đã đa ra nh ng nét so sánh v hi u su t và kh năng mộ ư ữ ề ệ ấ ả ở
r ng c a 2 thu t toán synchronous (đng b ) và asynchronous (không đng b )ộ ủ ậ ồ ộ ồ ộ
trong mô ph ng m ng song song th n tr ng. Nhóm nghiên c u cũng phát tri n m tỏ ạ ậ ọ ứ ể ộ
mô hình phân tích đ đánh giá hi u qu và tính kh m c a các tham s xác đnhể ệ ả ả ở ủ ố ị
trong m t thu t toán khá n i ti ng có tên là Null-message. ộ ậ ổ ế
Bài báo cũng ch rõ r ng d li u th c nghi m đã ch ng minh tính chính xácỉ ằ ữ ệ ự ệ ứ
c a mô hình này. Vi c phân tích và đo l ng trên h th ng song song v i hàng trămủ ệ ườ ệ ố ớ
b vi x lý cho th y r ng đi v i các k ch b n mô ph ng mô hình m ng thu nh cóộ ử ấ ằ ố ớ ị ả ỏ ạ ỏ
s l ng kênh vào / ra xác đnh thì thu t toán null-message có kh năng m r ng t tố ượ ị ậ ả ở ộ ố
h n kh năng gi m s l ng tính toán giá tr toàn c c t i thi u (global reduction)ơ ả ả ố ượ ị ụ ố ể
d a trên các giao th c đng b .ự ứ ồ ộ
2. GI I THI U BÀI BÁOỚ Ệ
Mô ph ng song song ng m đnh s th c hi n ch m t ch ng trình mô ph ngỏ ầ ị ự ự ệ ỉ ộ ươ ỏ
trên m t t p các processors k t n i ch t ch (máy tính song song).ộ ậ ế ố ặ ẽ
Các ti n trình logic (LPs) trong mô ph ng song song b i các thu t toán th nế ỏ ở ậ ậ
tr ng s luôn đm b o đc nguyên t c causality, đi u đó có nghĩa là các messageọ ẽ ả ả ượ ắ ề
nh n đc b i ti n trình này đc x lý theo tr t t không gi m c a nhãn th iậ ượ ở ế ượ ử ậ ự ả ủ ờ
gian. Tuy nhiên, không có gì đm b o r ng các đng h c c b trong các ti n trìnhả ả ằ ồ ồ ụ ộ ế
khác nhau đã “đng gi ” v i nhau. Vì v y, đng b hóa trong mô ph ng cũng là đồ ờ ớ ậ ồ ộ ỏ ề
tài đc đ c p đn trong nhi u nghiên c u tr c đây.ượ ề ậ ế ề ứ ướ
Các thu t toán th n tr ng đc chia thành 2 lo i, đó là đng b và khôngậ ậ ọ ượ ạ ồ ộ
đng b . Các thu t toán không đng b không yêu c u đng b hóa giá tr GVTồ ộ ậ ồ ộ ầ ồ ộ ị
(global vitua time). Thu t toán null-message (đc phát tri n t thu t toán g cậ ượ ể ừ ậ ố
Chandy-Misra-Bryant) đã gi i quy t đc v n đ h y b b t c là m t ví d đi nả ế ượ ấ ề ủ ỏ ế ắ ộ ụ ể
hình v thu t toán không đng b . Bên c nh đó, các thu t toán đng b hóa sề ậ ồ ộ ạ ậ ồ ộ ử
5