Đề 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)

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ÀITẬPLỚNMÔNHỌ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 ­ Học viên thực hiện ­ Môn học ­ Mã học phần ­ Chuyên ngành : TS. Phạm Đăng Hải : Hồ Thị Lợi (CA150114) Đoàn Vũ Giang (CA150108) Nguyễn Thị Thu Huyền (CB140170) : Chuyên đề 2 : IT6190 : 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 ... - tailieumienphi.vn