Nghiên cứu tìm hiểu ứng dụng sóng đệ qui phân tán

- Tác giả luận văn ĐẶNG CHUNG KIÊN  Trang 2 MỤC LỤC Trang Trang phụ bìa 1 Lời cam đoan 2 Danh mục các ký hiệu, các chữ viết tắt 5 Danh mục các hình vẽ 7 PHẦN MỞ ĐẦU 8 PHẦN NỘI DUNG 10 CHƯƠNG I: KHÁI NIỆM VÀ HÌNH THỨC HÓA SÓNG ĐỆ QUY PHÂN TÁN.
- Khái niệm sóng đệ quy phân tán: 12 1.
- Sóng đệ quy - công cụ đồng bộ hóa 13 II.
- Công cụ thực hiện sóng đệ quy phân tán 14 III.
- Các dạng sóng đệ quy phân tán 16 1.
- Sóng đệ quy tuần tự 16 2.
- Sóng đệ quy trên cây bao phủ 17 3.
- Sóng đệ quy ngập lụt 18 IV.
- MÔ HÌNH TOÁN CỦA SÓNG ĐỆ QUY PHÂN TÁN 19 1.
- Ví dụ về mô hình toán sóng đệ quy phân tán 21 3.
- Xây dựng giải thuật phân tán bằng sóng đệ quy 22 1.
- Lựa chọn phương phức dò tìm các tiến trình lân cận 24 3.
- BÀI TOÁN TÌM ĐƯỜNG NGẮN NHẤT VÀ SÓNG ĐỆ QUY PHÂN TÁN 25 CHƯƠNG II: TÌM HIỂU MỘT SỐ BÀI TOÁN PHÂN TÁN 36 I.
- BÀI TOÁN SNAPSHOT TRONG HỆ THỐNG PHÂN TÁN 36 1.
- Thuật toán snapshot cho hệ thống có các kênh truyền theo mô hình FIFO 41 a.
- Thuật toán Chandy-Lamport 42 c.
- Chứng minh thuật toán 44 d.
- Sự kết thúc của thuật toán 48 e.
- Mã giả của thuật toán 48 4.
- Thuật toán snapshot cho hệ thống có kênh truyền không theo mô 50  Trang 3 hình FIFO a.
- Sơ lược về thuật toán snapshot trên hệ thống phi FIFO 50 b.
- Thuật toán Lai-Yang 51 II.
- Sơ lược về bài toán election trong hệ phân tán 52 2.
- Thuật toán Bully 53 3.
- Thuật toán Ring 55 CHƯƠNG III: ỨNG DỤNG SÓNG ĐỆ QUY TRONG VIỆC GIẢI QUYẾT CÁC BÀI TOÁN PHÂN TÁN 57 I.
- BỐI CẢNH THỰC HIỆN SÓNG ĐỆ QUY PHÂN TÁN: 57 II.
- ỨNG DỤNG SÓNG ĐỆ QUY TRONG BÀI TOÁN SNAPSHOT 57 III.
- ỨNG DUNG SÓNG ĐỆ QUY TRONG BÀI TOÁN ELECTION 62 IV.
- ĐÁNH GIÁ VÀ HIỆU CHỈNH THUẬT TOÁN SÓNG ĐẸ QUY PHÂN TÁN 64 CHƯƠNG IV: ĐỀ XUẤT MÔ HÌNH CÀI ĐẶT SÓNG ĐỆ QUY PHÂN TÁN 66 I.
- Các thành phần cần thiết khi triển khai sóng đệ quy phân tán 66 II.
- Đề xuất Message Passing Interface cho sóng đệ quy 67 1.
- Một chuỗi tuần tự các sự kiện trong các tiến trình của một hệ thống phân tán 1(,);0iiiS next S e i n.
- Trạng thái tiếp theo của trạng thái Si ijC Kênh truyền từ tiến trình i đến tiến trình j ijSC Trạng thái của kênh truyền ijC {},,iijiijGS LS SC= UU Trạng thái toàn cục của hệ thống FIFO First in first out client-server Mô hình máy chủ - máy khách CHƯƠNG III ()iΓ Tập hợp các node hàng xóm của i _()callers list i Tập hợp các node có lời gọi đến i CHƯƠNG IV _seq WaveDeadtime Thời gian chết của toàn bộ hệ thống khi thực hiện sóng đệ quy phân tán dạng tuần tự _flood WaveDeadtime Thời gian chết của toàn bộ hệ thống khi thực hiện sóng đệ quy phân tán ngập lụt ee _spanningtr WaveDeadtime Thời gian chết của toàn bộ hệ thống khi thực hiện sóng đệ quy phân tán trên cây bao phủ  Trang 5 MPI Message Passing Interface Java RMI Java Remote Method Invocation ISO International Organization for Standardization HPC High Performance Computer, máy tính hiệu năng cao MPICH2 High-performance and Widely Portable MPI, chuẩn MPI được thiết kế cho hiệu năng cao và khả năng áp dụng rộng rãi trên nhiều môi trường  Trang 6 DANH MỤC HÌNH VẼ Trang Hình 1: Pha đi và pha về trong sóng đệ quy phân tán 12 Hình 2: Ví dụ về mô hình sóng đệ quy phân tán 21 Hình 3: Loại bỏ vòng trong tìm đường ngắn nhất 29 Hình 4: Mạng bài toán tìm đường ngắn nhất 34 Hình 5: Sóng đi và về trong bài toán tìm đường ngắn nhất 34 Hình 6: Các thành phần cơ bản trong trạng thái toàn cục 36 Hình 7: bài toán đơn giản gồm hai tiến trình 39 Hình 8: Các chiều đi và về của thẻ trên các kênh 39 Hình 9: Một ví dụ đầy đủ về quá trình gửi nhận token 40 Hình 10: Ví dụ chuyển tiền trong hệ thống gồm 2 tài khoản 41 Hình 11: Quá trình nhận marker và ghi lại trạng thái 42 Hình 12: Thuật toán Chandy-Lamport 42 Hình 13: Quá trình gửi marker trên hệ thống 2 tài khoản 43 Hình 14: Một chu trình trên thuật toán Chandy-Lamport 43 Hình 15: Một ví dụ snapshot trong hệ thống ngân hàng 44 Hình 16: Lắt cắt thể hiện đúng trạng thái toàn cục hệ thống 45 Hình 17: Tính đúng đắn của thuật toán 46 Hình 18: Trạng thái marker trở về 46 Hình 19: Thuật toán Bully 54 Hình 20: Thuật toán Ring 56 Hình 21: Ví dụ về một mạng chạy thuật toán snapshot 57 Hình 22: Pha đi của sóng snapshot trên mạng 58 Hình 23: Mô hình cây của mạng thực hiện sóng snapshot 59 Hình 24: Mạng thực hiện thuật toán election 62 Hình 25: Pha đi và về của sóng áp dụng cho thuật toán election.
- Các hệ thống phân tán đang được phát triển ngày càng lớn mạnh, các ứng dụng phân tán đang có trong rất nhiều các hệ thống, do vậy việc nghiên cứu một phương pháp xử lý các bài toán phân tán là cần thiết.
- Sóng đệ quy phân tán là một công cụ mạnh trong việc giải quyết các bài toán phân tán.
- Lavalleé đã đề cập chi tiết về sóng đệ quy phân tán.
- 2005: Trong bài báo “Sóng đệ quy phân tán” của các tác giả Hà Quốc Trung, Marc Bùi đã tổng kết đưa ra phân loại sóng và mô hình toán học cho sóng đệ quy phân tán cũng như là các gợi ý về định hướng phát triển.
- Nghiên cứu các vấn đề liên quan đến sóng đệ quy phân tán như khái niệm, mô hình, khả năng áp dụng và cách thức cài đặt cho một ngôn ngữ cụ thể.
- TÓM TẮT LUẬN ĐIỂM CƠ BẢN, CÁC ĐÓNG GÓP CỦA TÁC GIẢ • Khái niệm sóng đệ quy phân tán, phân loại.
- Mô hình toán học sóng đệ quy phân tán.
- Quy trình xây dựng sóng đệ quy phân tán.
- Ứng dụng sóng đệ quy phân tán vào một số bài toán phân tán.
- Đề xuất mô hình cài đặt cho sóng đệ quy phân tán PHƯƠNG PHÁP NGHIÊN CỨU.
- Hà nội, ngày 10 tháng 10 năm 2010 Học viên ĐẶNG CHUNG KIÊN  Trang 9 PHẦN NỘI DUNG CHƯƠNG I: KHÁI NIỆM VÀ HÌNH THỨC HÓA SÓNG ĐỆ QUY PHÂN TÁN Trong các hệ thống song song, khối lượng tính toán được chia ra thực hiện trên nhiều bộ vi xử lý.
- Sóng đệ qui, một cấu trúc lập trình phân tán bằng các lời gọi đệ qui phân tán cho phép • Lựa chọn bộ vi xử lý trong khi chương trình song song đang được thực hiện.
- Nguyên lý cơ bản của sóng đệ qui là thực hiện song song các lời gọi thủ tục một cách tự động, cung cấp khả năng cài đặt các thuật toán đệ qui trên các hệ thống song song.
- RPC thay thế cho cơ chế gửi tin nhắn được sử dụng trong cách xây dựng các thuật toán dựa trên client-server và hơn nữa là các hệ điều hành phân tán hướng đối tượng.
- Trong thực tế RPC được xem như một công cụ chính cho việc thiết kế hướng đối tượng khi chương trình đầu ra phải chạy được trên môi trường phân tán.
- Cần một cấu trúc điều khiển phức tạp tương tự trong lập trình phân tán.
- Sự tính toán lan truyền hay sóng tính toán là khái niệm mới trong cấu trúc điều khiển phân tán, nó có thể được sử dụng để xây dựng giải pháp mới cho nhiều vấn đề phân tán.
- Trong lập trình tuần tự, sự lặp lại và đệ quy là hai kiểu lập trình bổ sung cho nhau.
- Thiết kế đệ quy dễ dàng trong các trường hợp có sự lặp lại.
- Bởi vậy áp dụng đệ quy trong giải pháp đệ quy phân tán sẽ cho ra một cấu trúc rất mạnh.
- Trong luận văn này chúng ta sẽ tìm hiểu khái niệm sóng đệ quy.
- Nó được định nghĩa bởi một thủ tục được gọi trong quá trình thực thi các sự thực thi tự nó nếu sóng đệ quy xảy ra.
- Chúng ta xem  Trang 10 xét đệ quy phân tán được thực thi ở xa là được thực hiện bởi một bộ xử lý ở xa bằng sử dụng một RPC.
- Điểm thú vị nhất của lập trình đệ quy phân tán là phong cách tự nhiên, nó đưa ra các thuật toán phân tán.
- Kiểu lập trình đệ quy phân tán không hạn chế số lượng các máy tính đơn lẻ phân tán.
- Sự giải quyết vấn đề phân tán sử dụng sóng tính toán lan truyền hoặc khái niệm phân tán lặp thể hiện trong giải pháp phân tán đệ quy cùng mới các tin nhắn phức tạp.
- Thông thường, việc này được thực hiện bằng các hệ thống hỗ trợ lập trình phân tán.
- Tuy nhiên, phân phối công việc ở mức thấp có nhược điểm là không tận dụng được các đặc điểm của bản thân thuật toán để thực hiện có hiệu quả trên cấu hình mạng.
- Cơ chế sóng phân tán cho phép thu thập các thông tin về hệ thống.
- Việc sử dụng cơ chế lời gọi thủ tục cho phép xây dựng các thuật toán rõ ràng, đơn giản, mạnh, nhưng lại làm giảm hiệu năng của thuật toán do sử dụng ngăn xếp hệ thống để lưu trữ các thông tin trung gian.
- Các giải thuật phân tán đệ qui thừa kế được khả năng biểu diễn, tính đơn giản, rõ ràng của các giải thuật đệ qui tuần tự và tránh được việc sử dụng ngăn xếp nên không ảnh hưởng đến hiệu năng của giải thuật.
- Các giải thuật phân tán đệ qui sử dụng cấu trúc lời gọi thủ tục từ xa (Remote Procedure Call - RPC) để thực hiện việc gọi các thủ tục trên các bộ vi xử lý khác nhau.
- Trang 11 Việc kết hợp cấu trúc lời gọi thủ tục từ xa với cơ chế sóng phân tán cho phép xây dựng các giải thuật phân tán đệ qui rõ ràng, đơn giản, cho phép thu thập thông tin của hệ thống và điều khiển quá trình phân tán công việc trong hệ thống.
- KHÁI NIỆM SÓNG ĐỆ QUY Phần này sẽ đưa ra khái niệm sóng đệ quy, đây là một phương pháp lập trình để viết những thuật toán phân tán.
- Cũng chú ý là thuật toán này được dùng để phát triển cho các máy tính có kiến trúc bộ nhớ kiểu MIMD trong họ các hệ thống phân tán.
- Một kỹ thuật cho việc thiết kế thuật toán phân tán là sóng đệ quy liên quan đến một khái niệm tính toán khuếch tán (diffusing computation).
- acebdfghacebdfgh Hình 1: Pha đi và pha về trong sóng đệ quy phân tán Trong hình, khi một sóng tới node h, sóng sẽ ngược lại nơi xuất phát.
- Cái nhìn về tổng quan về lịch sử khái niệm sóng đệ quy • Một công cụ đồng bộ hóa.
- Cuối cùng là một định nghĩa chính thức của thuật toán sóng.
- Lịch sử phát triển: Thuật toán sóng đầu tiên, vào năm 1982 Chang đã đưa ra trong một bài báo, một mô tả thuật toán phân tán Echo.
- Mô tả thuật toán tiếng vọng được tạo nên bởi các nguyên lý.
- Hoạt động cơ bản của thuật toán tiếng vọng là gửi đi các tin nhắn từ node này đến node khác trong một mạng.
- Thuật toán tiếng vọng hoạt động một cách song song và không đồng bộ sử dụng các tin nhắn mang thông tin.
- Chúng có thể bắt đầu hoặc kết thúc trong một hoặc nhiều node, các node phải hợp tác, nhất quán và khởi tạo các phần độc lập tham gia vào thuật toán.
- Với dạng thuật toán này, Chang đã mang tới một kỹ thuật mới trong tính toán phân tán là tính toán dạng sóng.
- Sau đó Raynal và Helary đã thể hiện thuật toán sóng đầu tiên như một công cụ đồng bộ bằng cách đưa ra một định nghĩa chính thức cho sóng.
- Sóng như một công cụ đồng bộ hóa: Raynal và Helary đã thể hiện một thuật toán để giải quyết vấn đề về graph, nó bao gồm việc xây dựng một cây bao phủ cho mạng các bộ xử lý.
- Thuật toán kết thúc khi node gốc nhận được cờ đã hoàn thành của các node kế thừa.
- Khái niệm sóng như trình bày của thuật toán cho thây hai loại đồng bộ hóa: Đồng bộ hóa địa phương: một tiến trình phải chờ cho đến khi nhận được tin nhắn lại của những node hàng xóm.
- Công cụ thực hiện sóng đệ quy phân tán: Trước khi đến khái niệm sóng đệ quy thì ta phải xem khái niệm thủ tục, trong quá trình thực thi thủ tục này gọi n các thực thi của nó ở xa một cách đồng thời.
- Từ đây nó thực hiện một sóng đệ quy dẫn đầy một cây như sau.
- Gốc và các lá liên quan đến khối thủ tục chờ tất cả các lời gọi đệ quy song song dừng.
- Lá liên quan đến thực thi hiện tại của thủ tục hoặc liên quan đến sự dừng thực thi không có lời gọi đệ quy.
- Một thủ tục sóng đệ quy thường được gắn với một cấu trúc dữ liệu.
- Để có thể thực hiện được các giải thuật sóng đệ quy, chúng ta cần có một số công cụ được sử dụng để biểu diễn.
- Công cụ này bao gồm câu lệnh par để thực hiện gọi thủ tục trên nhiều các tiến trình và cách thức gọi các tiến trình trên các bộ xử lý khác từ bộ xử lý hiện tại.
- Câu lệnh này kết thúc khi tất cả các luồng trên các tiến trình từ xa kết thúc và lệnh tiếp theo sau lệnh par sẽ được thực hiện tiếp theo.
- Việc thực thi của sóng đệ quy được xây dựng một mô hình cây của các tiến trình đang hoạt động trong mạng và quan tâm đến quan hệ giữa tiến trình gọi và tiến trình được gọi, theo ngôn ngữ thông dụng thì là quan hệ cha con, ở đây node gốc của cây chính là khởi đầu của sự tính toán.
- Với hai cấu trúc ở trên chúng ta có thể biểu diễn các lời gọi phân tán đệ quy như trong cấu trúc sóng đệ quy dưới đây.
- begin --Khối lệnh A tính toán tuần tự --Tiếp theo là lệnh điều kiện if then else thực hiện dừng sóng --đệ quy khi các điều kiện  Trang 15 --thỏa mãn if then --Lệnh par sau đó cho phép thực thi đồng thời trên mỗi.
- lời gọi đệ quy của thủ tục hiện tại par i in processor_group do .
- Các dạng sóng đệ quy phân tán 1.
- Sóng đệ quy tuần tự: Sóng đệ quy tuần tự là loại sóng đơn giản nhất sử dụng một lời gọi đệ quy trong một hệ thống phân tán là gọi cùng một thủ tục trên chỉ một tiến trình trên một bộ xử lý khác từ xa.
- Cây thực thi được giản lược thành một chuỗi các nhóm thủ tục trên một chuỗi các tiến trình.
- Tại bất kì một thời điểm chỉ có một thủ tục chạy gọi một thủ tục đệ quy trên một tiến trình khác.
- Trong lập trình phân tán, topology liên quan đến sóng đệ quy tuần tự là virtual ring, mỗi bộ xử lý được biết đến với bộ xử lý kế cận (bộ xử lý sẽ được gọi đệ quy) và bộ xử lý đã gọi bộ xử lý hiện tại.
- Bởi vậy sóng đệ quy tuần tự được định nghĩa bởi cấu trúc sau: type processor_identifier is

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt