MỞ ĐẦU. Lap Trinh Song Song. Lap trinh song song là ØÌ?. Kiến trúc máy tính song song.----- 5: tt E1 EE2112121 11 tre 5 3.
Các mô hình lập trình song song. Thuật toán song song. SH HH HH HH HH HH nà 14 2. Ứng dụng MPI.
Ưu nhược điểm. Ứng Dụng Hadoop. sc tr HH HH rờn 16 3. Ưu nhược điểm.
T211 1121551551558 8E nntn HH HHrye 16 CHƯƠNG 2: CÀI ĐẶT 19 Non 0i 8n -4. Cài đặt MSMpISefUp. Q Lọ HH1re 23 SVTH:Nguyén Duy Thang Lép:19CNTTD Lập Trình Song Song GVHD:Nguyén Dinh Lau IL. Cài đặt Hadoop.
2222122111121 112111 111121112111 1811 18111011111 11ha 23 CHƯƠNG 3: CHẠY CHƯƠNG TRÌNH. 5° 52s s s ecs es escse 48 L. Chạy chương trình MPI bằng VS 2022.-- c1 E211 1t E1 rryey 48 IL Chạy MapReduceTDiikstra Trên Hadoop. Chạy WordCount Trên Hadoop.- 222 1211112221111 21112 re 62 SVTH:Nguyên Duy Thang Lớp:19CNTTD Lập Trình Song Song GVHD:Nguyén Dinh Lau SVTH:Nguyên Duy Thang 1 Lớp:19CNTTD Lập Trình Song Song GVHD:Nguyén Dinh Lau MO DAU I.
Dat van dé Ly thuyét đồ thị là một lĩnh vực đã xuất hiện từ lâu trong toán học, tin học và có nhiều ứng dụng trong thực tế. Những tư tưởng cơ bản của lý thuyết đồ thị xuất hiện vào những năm đầu của thế ky 18 bởi nhà toán học Thụy Sĩ Leonhard Euler trong bài bao về bảy cây cầu ở Königsberg. Từ đó lý thuyết đồ thị ngày càng khẳng định vị tri quan trọng của mình trong việc áp dụng đề giải các bài toán thực tế nhờ vào việc ngày càng tìm ra và chứng minh được các định lý, công thức và thuật toán. Trong các bài toán ứng dụng thực tế, bài toán tìm đường đi ngắn nhất giữa cặp đỉnh của một đồ thị liên thông được ứng dụng rất nhiều và có ý nghĩa hết sức to lớn, ví dụ: chọn hành trình tiết kiệm nhất trên mạng giao thông, lập lịch thi công các công đoạn trong một công trình thi công lớn, lựa chọn đường truyền tin.
Tuy nhiên, đối với những bài toán phức tạp với số lượng đữ liệu lớn và phân tán thì thuật toán tìm đường đi ngắn nhất tuần tự xử lý rất lâu hoặc có những trường hợp thuật toán tuần tự không thực hiện được. Điều này đòi hỏi phải phân tích dữ liệu, tìm sự phụ thuộc dữ liệu giữa các bước của thuật toán, phân tích câu lệnh, tìm hiểu các mô hình xử lý song song, hệ thông máy tính và ngôn ngữ lập trình để song song hóa các thuật toán tuần tự tương ứng. MPI (Message Passing Interface) là thư viện hỗ trợ lập trình song song trong ngôn ngữ C. MPI được phát triển bởi một điển đàn mở quốc tế, bao gồm nhiều tổ chức và phòng thí nghiệm của chính phủ.
MPI nhanh chóng được ứng dụng rộng rãi và trở thành một trong những mô hình được sử dụng phổ biến cho việc lập trình các hệ thống song song. Xuất phát từ đó tôi quyết định chọn đề tài “Song song hóa thuật toán tùn đường đi ngắn nhất giữa mọi cặp đỉnh sử dụng thư viện M4P?" làm đề tài tốt nghiệp luận văn cao học. SVTH:Nguyên Duy Thang 2 Lớp:19CNTTD Lập Trình Song Song GVHD:Nguyén Dinh Lau II. Mục đích Nghiên cứu và song song hóa thuật toán Floyd_ Warshall cho bài toán tìm đường đi ngắn nhất trên nguồn đữ liệu lớn và phân tán, từ đó nâng cao hiệu quả của việc xử lý đữ liệu.
Noi dung Trong luận văn này gồm có 3 nội dung: - Nội dung I: Crới thiệu - Nội dung 2: Cài Đặt - Nội dung 3: Chạy chương trình IV. Phương pháp nghiên cứu - Nghiên cứu các tài liệu về cơ sở lý thuyết: Lý thuyết đồ thị, xử lý song song. - Sử dụng phương pháp phân tích, so sánh và đánh giá các thuật toán tìm đường đi ngắn nhất. -Tiến hành hướng dẫn cách cài đặt MPI và Hadoop -Cách chạy một số bài tập liên quan SVTH:Nguyên Duy Thang 3 Lớp:19CNTTD Lập Trình Song Song GVHD:Nguyén Dinh Lau CHUONG 1: MO DAU I.
Lap Trinh Song Song 1. Lap trinh song song 1a gi? - Những van đề về xử lý ngôn ngữ tự nhiên, nhận dạng, xử lý ảnh ba chiều, dự báo thời tiết, mô hình và mô phỏng những hệ thống lớn trong thực tế đều đòi hỏi phải xử lý dữ liệu với tốc độ rất cao và khối lượng đỡ liệu rất lớn - Do đó, cần phải có những hệ thông máy tính thật mạnh mới thực hiện được những yêu cầu trong thực tế một cách nhanh chóng và hiệu quả. Điều này còn gặp nhiều khó khăn do khả năng giới hạn về vật lý. Vì vậy, hướng xử lý song song là đùng các hệ thống máy tính đa bộ xử lý hoặc bộ xử lý đa nhân được lựa chọn đề giải quyết các bài toán đặt ra.
- Xử lý song song là quá trình xử lý gồm nhiều tiến trình được kích hoạt đồng thời và cùng tham gia giải quyết một vấn đề, nói chung là thực hiện tính toán trên những hệ thông đa bộ xử lý - Tính toán song song là một hình thức tính toán trong đó nhiều phép tính được thực hiện đồng thời, hoạt động trên nguyên tắc là những vấn đề lớn đều có thê chia thành nhiều phần nhỏ hơn đề giải quyết đồng thời trên các bộ xử lý Một chương trình máy tính, về bản chất là một loạt những câu lệnh được thực hiện bởi một bộ xử lý. Những câu lệnh này sẽ được sắp xép lại và kết hợp thành các nhóm mà sau đó được thực hiện song song mà không thay đối kết quả của chương trình. Đây được gọi là song song cấp câu lệnh. Một công việc phức tạp hơn so với lập trình tuần tự thông thường, người phát triển phải thực hiện một quá trình “song song hóa”, biến đôi các chương trình tuần tự thành chương trình song song có khả năng tận dụng tối đa sức mạnh của hệ thống Lập trình song song bào gồm các bước : -Phân hủy một thuật toán hay các dữ liệu đầu vào.
-Phân chia nhiệm vụ cho các bộ phận để làm việc trong bộ vị xử lý cùng một lúc. -Phối hợp và trao đổi giữa các bộ vi xử lý. SVTH:Nguyên Duy Thang 4 Lớp:19CNTTD Lập Trình Song Song GVHD:Nguyén Dinh Lau 2. Kién tric may tinh song song - Những van đề về xử lý ngôn ngữ tự nhiên, nhận dạng, xử lý ảnh ba chiều, dự báo thời tiết, mô hình và mô phỏng những hệ thống lớn trong thực tế đều đòi hỏi phải xử lý dữ liệu với tốc độ rất cao và khối lượng đỡ liệu rất lớn - Do đó, cần phải có những hệ thông máy tính thật mạnh mới thực hiện được những yêu cầu trong thực tế một cách nhanh chóng và hiệu quả.
Điều này còn gặp nhiều khó khăn do khả năng giới hạn về vật lý. Vì vậy, hướng xử lý song song là đùng các hệ thống máy tính đa bộ xử lý hoặc bộ xử lý đa nhân được lựa chọn đề giải quyết các bài toán đặt ra. Các mô hình lập trình song song Việc đưa ra một mô hình máy tính chung cho việc lập trình giúp cho việc thiết kế giải thuật trở nên đơn giản hơn. Lập trình song song đưa thêm những khó khăn mới vào mô hình lập trình tuần tự.
Nêu chương trình được thực hiện ở mức thấp nhất thì không những số lệnh thực hiện là rất lớn mà nó còn phải trực tiếp quản lý quá trình thực hiện song song của hàng nghìn bộ xử lý và kết hợp hàng triệu tương tác liên bộ xử lý. Bởi vậy khả năng trừu tượng và tính toán module là các đặc tính rất quan trọng trong lập trình song song. Các mô hình thông dụng bao gồm: - M6 hinh chia sẽ bộ nhớ. - - Mô hình luỗng.
- _ Mô hình truyền thông điệp. - Mô hình song song đữ liệu. Mô hình chia sẽ bộ nhớ Trong mô hình này, nhiệm vụ cùng chia sẽ một không gian địa chí chung có thê được truy cập đọc ghi theo phương thức không đồng bộ. Các cơ chế khác nhau như khóa (locks) và semaphore được điều khiển đề truy cập đến bộ nhớ toàn cục.
Nhược điểm của mô hình này là khó giữ lại được tính nguyên thủy của dữ liệu khi mà nhiều bộ xử lý dùng cũng đữ liệu này. Lợi thế của mô hình là người lập trình không cần chỉ định việc truyền đữ liệu giữa các task; chương trình được phát triển thường được đơn giản hóa. Mô hình luồng Trong mô hình luồng chương trình chính được chia thành các nhiệm vụ. Mỗi nhiệm vụ được thực hiện bởi các luồng một cách đồng thời.
Mỗi một luồng có dữ liệu SVTH:Nguyên Duy Thang 5 Lớp:19CNTTD Lập Trình Song Song GVHD:Nguyén Dinh Lau riêng của nó va chia sẽ dữ liệu toàn cục của chương trình chính. Các nhiệm vụ đưa cho mỗi luỗng là các thủ tục con của chương trình chính. Bất kỳ luồng nào cũng có thê thực hiện bất kì thử tục con nào tại cùng thời điểm với các luồng khác. Trong mô hình luồng các luồng kết nối với nhau thông qua bộ nhớ toàn cục với việc kết nối này thì chương trình phải được xây dựng một cách đồng bộ đề tránh cùng một lúc có nhiều luồng cùng cập nhập một vị trí trong bộ nhớ toàn cục.
Mô hình luống Trong mô hình luồng chương trình chính được chia thành các nhiệm vụ. Mỗi nhiệm vụ được thực hiện bởi các luồng một cách đồng thời. Mỗi một luồng có dữ liệu riêng của nó và chia sẽ dữ liệu toàn cục của chương trình chính. Các nhiệm vụ đưa cho mỗi luỗng là các thủ tục con của chương trình chính.
Bất kỳ luồng nào cũng có thê thực hiện bất kì thử tục con nào tại cùng thời điểm với các luồng khác. Trong mô hình luồng các luồng kết nối với nhau thông qua bộ nhớ toàn cục với việc kết nối này thì chương trình phải được xây dựng một cách đồng bộ đề tránh cùng một lúc có nhiều luồng cùng cập nhập một vị trí trong bộ nhớ toàn cục. Mô hình truyền thông điệp Trong mô hình truyền thông điệp chương trình song song được chia thành các tác nhiệm. Mỗi tập các tác nhiệm sử dụng bộ nhớ cục bộ riêng của chúng trong quá trình tính toán.
Nhiều tác nhiệm có thê năm trên cùng một máy cũng như năm trên nhiều máy. Máy A Máy B Tác vụ 0 Mane Tac vy | Gửi dữ liệu Nhận dữ liệu Các tác nhiệm trao đổi dữ liệu thông qua truyền thông bằng cách gửi và nhận các thông điệp. Có nhiều thư viện truyền thông điệp, nhưng chúng khác nhau đáng kẻ, gây khó khăn cho các nhà lập trình trong việc phát triển các ứng dụng di động. MPI Forum được SVTH:Nguyên Duy Thang 6 Lớp:19CNTTD Lập Trình Song Song GVHD:Nguyén Dinh Lau lập ra với mục đích thiết lập một chuẩn cho việc triển khai mô hình truyền thông điệp.