Bối cảnh và vấn đề nghiên cứu

Lý thuyết đồ thị là một phân ngành toán học và khoa học máy tính có lịch sử phát triển từ thế kỷ 18, khởi nguồn từ công trình của nhà toán học Leonhard Euler giải quyết bài toán bảy cây cầu ở Königsberg. 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ác cặp đỉnh của một đồ thị liên thông đóng vai trò thiết yếu trong việc tối ưu hóa mạng lưới giao thông, lập lịch thi công các công đoạn trong dự án xây dựng quy mô lớn, cũng như định tuyến truyền gói tin trong mạng máy tính.

Khi kích thước đồ thị tăng lên và dữ liệu có tính chất phân tán quy mô lớn, các thuật toán xử lý tuần tự truyền thống bộc lộ rõ hạn chế về hiệu năng: thời gian thực thi kéo dài hoặc không thể xử lý do giới hạn phần cứng của một máy tính đơn lẻ. Để khắc phục giới hạn vật lý của bộ xử lý đơn, tính toán song song và phân tán trên hệ thống đa nhân (multi-core) hoặc cụm máy tính (cluster) trở thành giải pháp tối ưu.

Đồ án tập trung vào các mục tiêu và nhiệm vụ nghiên cứu sau:

  1. Nghiên cứu tổng quan về tính toán song song, kiến trúc máy tính song song, các mô hình lập trình và nguyên lý thiết kế giải thuật song song.
  2. Tìm hiểu và phân tích hai nền tảng xử lý dữ liệu và tính toán phân tán phổ biến: Giao diện truyền thông điệp MPI (Message Passing Interface) và hệ sinh thái xử lý dữ liệu lớn Apache Hadoop.
  3. Xây dựng tài liệu hướng dẫn kỹ thuật chi tiết về quy trình cài đặt, thiết lập môi trường và cấu hình các biến hệ thống cho MS-MPI trên Microsoft Visual Studio 2022 và Apache Hadoop trên hệ điều hành Windows.
  4. Triển khai thực nghiệm chạy các chương trình mẫu: chương trình MPI cơ bản, bài toán đếm từ (WordCount) và thuật toán tìm đường đi ngắn nhất trên nền tảng đã cài đặt.

Đối tượng và phạm vi nghiên cứu:

  • Đối tượng: Các mô hình tính toán song song, thư viện MS-MPI, hệ thống phân tán Apache Hadoop (gồm HDFS, MapReduce, YARN) và thuật toán tìm đường đi ngắn nhất (Floyd-Warshall, Dijkstra).
  • Phạm vi không gian và công nghệ: Triển khai thực nghiệm trên hệ điều hành Windows 64-bit, sử dụng môi trường phát triển Microsoft Visual Studio 2022 cho mã nguồn C/C++ với MS-MPI SDK, và Java SE Development Kit (JDK 8) kết hợp Hadoop 3.0 / Hadoop 2.6 cho mô hình MapReduce.

Cơ sở lý thuyết và phương pháp

1. Khung lý thuyết tính toán song song

Tính toán song song là hình thức tính toán trong đó nhiều phép tính hoặc tiến trình được thực hiện đồng thời, dựa trên nguyên tắc chia nhỏ bài toán lớn thành các phần độc lập để gán cho các bộ xử lý thực thi cùng lúc.

Đồ án phân loại và hệ thống hóa 4 mô hình lập trình song song cơ bản:

  • Mô hình chia sẻ bộ nhớ (Shared Memory Model): Các tiến trình/tác vụ cùng chia sẻ một không gian địa chỉ chung, sử dụng các cơ chế đồng bộ như khóa (locks) và semaphore để kiểm soát truy cập bộ nhớ toàn cục.
  • Mô hình luồng (Thread Model): Chương trình chính phân tách thành các luồng thực thi đồng thời; mỗi luồng có không gian dữ liệu riêng cục bộ nhưng cùng chia sẻ vùng nhớ chung của tiến trình cha.
  • Mô hình truyền thông điệp (Message Passing Model): Mỗi tác vụ sở hữu vùng nhớ cục bộ độc lập và trao đổi thông tin qua việc gửi (send) và nhận (receive) thông điệp mạng. Chuẩn công nghiệp phổ biến nhất là MPI.
  • Mô hình song song dữ liệu (Data Parallel Model): Cùng một tập thao tác/câu lệnh được áp dụng đồng thời trên các phân vùng khác nhau của một cấu trúc dữ liệu lớn (mảng, khối).

Quy trình thiết kế thuật toán song song bao gồm 4 công đoạn:

  1. Phân rã (Partitioning): Chia nhỏ khối lượng tính toán và dữ liệu thành tập hợp các tác vụ độc lập.
  2. Truyền thông (Communication): Xác định luồng dữ liệu cần trao đổi giữa các tác vụ.
  3. Tích tụ (Agglomeration): Gộp các tác vụ nhỏ thành tác vụ lớn hơn nhằm cân đối chi phí truyền thông và mức độ song song hóa.
  4. Ánh xạ (Mapping): Gán các tác vụ đã tích tụ vào từng bộ xử lý vật lý cụ thể.

Đồ án tổng hợp 5 nguyên lý thiết kế thuật toán song song: nguyên lý lập lịch, nguyên lý hình ống (pipelining), nguyên lý chia để trị (divide and conquer), nguyên lý đồ thị phụ thuộc dữ liệu và nguyên lý điều kiện tương tranh.

2. Mô hình toán học đánh giá hiệu năng

Hiệu năng của thuật toán song song trên hệ thống có $p$ bộ xử lý giải quyết bài toán kích thước $n$ được đánh giá qua các chỉ số:

  • Thời gian thực thi song song ($t_p$): $$t_p = t_{comp} + t_{comm}$$ Trong đó $t_{comp}$ là thời gian tính toán thực tế của tiến trình phức tạp nhất, $t_{comm}$ là tổng thời gian truyền thông điệp.
  • Thời gian truyền thông ($t_{comm}$): $$t_{comm} = t_{startup} + n \cdot t_{data}$$ Với $t_{startup}$ là thời gian trễ đóng/mở gói thông điệp, $t_{data}$ là thời gian truyền một đơn vị dữ liệu và $n$ là khối lượng dữ liệu trao đổi.
  • Hệ số tăng tốc (Speedup - $S_p$): $$S_p = \frac{t_s}{t_p}$$ (Với $t_s$ là thời gian thực thi tuần tự tối ưu).
  • Luật Amdahl về giới hạn tăng tốc: Nếu $P$ là tỷ lệ mã nguồn có thể song song hóa, hệ số tăng tốc tối đa với $N$ bộ xử lý là: $$S_p \le \frac{1}{(1-P) + \frac{P}{N}}$$
  • Hiệu suất tính toán song song ($E_p$): $$E_p = \frac{S_p}{p}$$

3. Khung công nghệ MPI và Apache Hadoop

  • MPI (Message Passing Interface): Chuẩn giao tiếp truyền thông điệp dành cho các ngôn ngữ C, C++, Fortran, Ada; cung cấp các hàm giao tiếp điểm-điểm (point-to-point) và giao tiếp tập hợp (collective communication).
  • Apache Hadoop: Nền tảng mã nguồn mở bằng Java cho phép lưu trữ và xử lý phân tán dữ liệu quy mô lớn theo mô hình cụm máy tính. Kiến trúc gồm 4 module cốt lõi:
    • Hadoop Common: Thư viện nền tảng và tiện ích hệ điều hành.
    • Hadoop YARN: Khung quản lý tài nguyên cụm và điều phối tiến trình.
    • HDFS (Hadoop Distributed File System): Hệ thống tập tin phân tán cung cấp truy cập thông lượng cao.
    • Hadoop MapReduce: Khung lập trình và thực thi tính toán song song trên tập dữ liệu lớn.

4. Phương pháp nghiên cứu

Đồ án áp dụng phương pháp nghiên cứu lý thuyết kết hợp thực nghiệm kỹ thuật:

  • Thu thập và phân tích tài liệu chuyên khảo về lý thuyết đồ thị và xử lý song song/phân tán.
  • Triển khai xây dựng môi trường, cài đặt phần mềm và thiết lập cấu hình tham số trực tiếp trên máy trạm Windows.
  • Biên dịch và chạy thử nghiệm mã nguồn để đối chiếu kết quả đầu ra.

Thiết kế và triển khai

Hệ thống thực nghiệm được thiết kế và cấu hình trên môi trường Windows 64-bit với các thành phần công nghệ:

Thành phần Phiên bản / Công cụ Vai trò trong hệ thống
Môi trường IDE Microsoft Visual Studio 2022 Community Soạn thảo, liên kết thư viện và biên dịch mã nguồn C/C++
Thư viện song song Microsoft MPI (MS-MPI SDK & Setup) Cung cấp header (mpi.h), thư viện liên kết (msmpi.lib) và trình thực thi mpiexec.exe
Máy ảo Java Java SE Development Kit (JDK) 8u201 / 8u351 Môi trường thực thi Java bắt buộc cho hệ sinh thái Hadoop
Nền tảng phân tán Apache Hadoop 3.0.0 / 2.6.0 Hệ thống tệp phân tán HDFS và công cụ tính toán MapReduce
Tiện ích Windows Apache Hadoop Winutils (winutils.exe) Cung cấp các nhị phân tương thích POSIX/Linux cho Hadoop trên Windows

Quy trình cấu hình kỹ thuật

1. Cấu hình Visual Studio 2022 cho Microsoft MPI

Để biên dịch được chương trình MPI trên nền tảng C++, người phát triển phải cấu hình các thuộc tính của project trong Visual Studio:

  • Include Directories: Bổ sung đường dẫn chứa tập tin tiêu đề: C:\Program Files (x86)\Microsoft SDKs\MPI\Include;$(IncludePath).
  • Library Directories: Bổ sung đường dẫn chứa tập tin thư viện cho nền tảng x64: C:\Program Files (x86)\Microsoft SDKs\MPI\Lib\x64;$(LibraryPath).
  • Linker Input (Additional Dependencies): Bổ sung msmpi.lib.
  • System Environment Variable: Bổ sung đường dẫn nhị phân C:\Program Files\Microsoft MPI\Bin vào biến PATH của hệ điều hành.

2. Cấu hình Apache Hadoop trên Windows

Quy trình cấu hình Hadoop gồm các bước liên kết môi trường và chỉnh sửa các tệp tin cấu hình XML:

  • Thiết lập biến môi trường:
    • JAVA_HOME: Trỏ tới thư mục cài đặt JDK không chứa khoảng trắng (ví dụ: C:\jdk1.8.0_201 hoặc C:\Java\jdk1.8.0_351).
    • HADOOP_HOME: Trỏ tới thư mục giải nén Hadoop (ví dụ: C:\hadoop-3.0 hoặc C:\hadoop-2.6).
    • Cập nhật biến PATH với các giá trị %JAVA_HOME%\bin, %HADOOP_HOME%\bin, %HADOOP_HOME%\sbin.
  • Cấu hình core-site.xml: Chỉ định cổng kết nối HDFS mặc định: 
    <configuration>
  <property>
    <name>fs.defaultFS</name>
    <value>hdfs://localhost:9000</value>
  </property>
</configuration>
  • Cấu hình mapred-site.xml: Thiết lập dịch vụ theo dõi tác vụ MapReduce: 
    <configuration>
  <property>
    <name>mapred.tracker</name>
    <value>localhost:9001</value>
  </property>
</configuration>
  • Cấu hình hdfs-site.xml: Thiết lập hệ số nhân bản dữ liệu và đường dẫn lưu trữ cục bộ cho NameNode và DataNode: 
    <configuration>
  <property>
    <name>dfs.replication</name>
    <value>1</value>
  </property>
  <property>
    <name>dfs.namenode.name.dir</name>
    <value>C:\hadoop-2.6\data\namenode</value>
  </property>
  <property>
    <name>dfs.datanode.data.dir</name>
    <value>C:\hadoop-2.6\data\datanode</value>
  </property>
</configuration>
  • Cấu hình yarn-site.xml: Định cấu hình dịch vụ phụ trợ cho MapReduce Shuffle: 
    <configuration>
  <property>
    <name>yarn.nodemanager.aux-services</name>
    <value>mapreduce_shuffle</value>
  </property>
  <property>
    <name>yarn.nodemanager.aux-services.mapreduce.shuffle.class</name>
    <value>org.apache.hadoop.mapred.ShuffleHandler</value>
  </property>
</configuration>
  • Cấu hình hadoop-env.cmd: Gán tường minh đường dẫn Java: set JAVA_HOME=C:\jdk1.8.0_201.
  • Khởi tạo hệ thống tập tin: Thực thi lệnh hdfs namenode -format để khởi tạo cấu trúc dữ liệu cho NameNode trước lần chạy đầu tiên.

Nội dung chính theo từng chương

Chương 1: Mở đầu

Chương 1 thiết lập khung lý thuyết hoàn chỉnh về lĩnh vực lập trình song song và phân tán:

  • Trình bày định nghĩa tính toán song song, phân tích sự cần thiết của việc tận dụng kiến trúc đa lõi nhằm giải quyết bài toán khối lượng tính toán lớn (như xử lý ngôn ngữ tự nhiên, xử lý ảnh 3D, dự báo thời tiết).
  • Phân tích chi tiết 4 mô hình lập trình song song: Chia sẻ bộ nhớ, mô hình luồng, truyền thông điệp và song song dữ liệu.
  • Làm rõ quy trình thiết kế giải thuật song song qua 4 giai đoạn (Phân rã, Truyền thông, Tích tụ, Ánh xạ) và 5 nguyên lý kỹ thuật.
  • Xây dựng mô hình toán học đo lường độ phức tạp, biểu thức tính thời gian truyền thông, chi phí tính toán, hệ số tăng tốc $S_p$, hiệu suất $E_p$ và phân tích giới hạn của luật Amdahl.
  • Giới thiệu tổng quan kiến trúc, ưu điểm, nhược điểm của chuẩn truyền thông điệp MPI và hệ sinh thái phân tán Apache Hadoop (Common, HDFS, YARN, MapReduce).

Chương 2: Cài đặt

Chương 2 đóng vai trò là phần tài liệu hướng dẫn kỹ thuật chi tiết từng thao tác thực tế:

  • Cài đặt MS-MPI: Hướng dẫn cài đặt Visual Studio 2022 gói Desktop development with C++, cài đặt MSMPISDK.msi và MSMpiSetup.exe.
  • Cài đặt JDK: Hướng dẫn tải và cài đặt Java Development Kit 8u201 từ nền tảng Oracle, thiết lập biến môi trường JAVA_HOME và cấu hình hệ thống để xác thực qua lệnh java -version và javac -version.
  • Cài đặt Hadoop: Hướng dẫn giải nén gói nhị phân Hadoop vào ổ đĩa hệ thống, tích hợp bộ công cụ winutils.exe, cấu hình các biến môi trường HADOOP_HOME, điều chỉnh 5 tập tin cấu hình hệ thống (core-site.xml, mapred-site.xml, hdfs-site.xml, yarn-site.xml, hadoop-env.cmd), và thực hiện định dạng NameNode (hdfs namenode -format).

Chương 3: Chạy chương trình

Chương 3 trình bày các bước biên dịch, thực thi và kiểm thử kết quả đầu ra của các ứng dụng mẫu:

  • Thực thi chương trình MPI:
    • Soạn thảo mã nguồn kiểm tra giao tiếp cơ bản MPI_Init, MPI_Comm_size, MPI_Comm_rank, MPI_Finalize trong Visual Studio 2022.
    • Biên dịch tạo tệp thực thi MPI_lau2.exe.
    • Khởi chạy chương trình song song 4 tiến trình thông qua câu lệnh: 
      mpiexec -np 4 MPI_lau2.exe
    • Xác nhận kết quả in ra màn hình console hiển thị kích thước nhóm (SIZE = 4) và định danh riêng của từng tiến trình (RANK = 0, 1, 2, 3).
  • Thực thi chương trình WordCount trên Hadoop:
    • Khởi động hệ thống Hadoop và kiểm tra trạng thái các tiến trình dịch vụ thông qua lệnh jps.
    • Tạo thư mục trên hệ thống tệp phân tán HDFS: hadoop fs -mkdir /input.
    • Đẩy tệp dữ liệu văn bản mẫu vào HDFS: hadoop fs -put C:/data.txt /input/.
    • Kiểm tra nội dung tệp bằng lệnh hadoop fs -cat /input/data.txt.
    • Kích hoạt tác vụ MapReduce từ gói tệp mẫu hadoop-mapreduce-examples-*.jar với lớp wordcount /input /out.
    • Đọc kết quả phân tích tần suất xuất hiện của các từ khóa đầu ra từ thư mục /out bằng lệnh hadoop fs -cat /out/*.

Kết quả và đóng góp

Kết quả chính

  • Xây dựng thành công tài liệu hướng dẫn kỹ thuật: Cung cấp quy trình chi tiết, có minh chứng bằng hình ảnh thao tác từng bước cho việc cài đặt và cấu hình môi trường lập trình song song MPI và phân tán Hadoop trên nền tảng hệ điều hành Windows.
  • Thực nghiệm hoàn chỉnh mã nguồn MPI: Biên dịch thành công mã nguồn C++ sử dụng thư viện MS-MPI trên Visual Studio 2022 và thực thi đa tiến trình độc lập với tham số -np 4.
  • Thực nghiệm hoàn chỉnh quy trình MapReduce: Triển khai thành công luồng xử lý dữ liệu hoàn chỉnh của tác vụ WordCount trên HDFS từ bước nhập dữ liệu đầu vào (/input), thực thi tính toán phân tán, đến xuất kết quả thống kê tần suất từ khóa (/out).
  • Khẳng định tính ưu việt của giải thuật song song: Khái quát hóa việc song song hóa thuật toán tìm đường đi ngắn nhất Floyd-Warshall trên nền tảng MPI cho hiệu quả xử lý vượt trội so với phương pháp tuần tự cổ điển khi xử lý dữ liệu lớn.

Đóng góp của đề tài

  • Hệ thống hóa toàn diện các kiến thức nền tảng về tính toán song song, mô hình kiến trúc máy tính và công thức đánh giá định lượng hiệu năng thuật toán.
  • Đưa ra giải pháp cài đặt và tích hợp trực tiếp các công cụ phân tán/song song (thường vốn được tối ưu cho môi trường Linux) lên môi trường Windows, giúp giảm bớt rào cản kỹ thuật cho sinh viên và người mới bắt đầu tiếp cận môn học Lập trình song song.

Hạn chế và hướng nghiên cứu tiếp

Hạn chế

  • Quy mô môi trường thực nghiệm: Hệ thống Hadoop và MPI được cài đặt và vận hành trên một máy tính cá nhân đơn lẻ ở chế độ giả lập phân tán (pseudo-distributed / standalone mode), chưa phản ánh toàn diện các vấn đề về độ trễ mạng vật lý thực tế trên các cụm máy chủ lớn.
  • Vấn đề an toàn và bảo mật: Nền tảng Hadoop mặc định không tích hợp cơ chế mã hóa dữ liệu trên đường truyền mạng hoặc kiểm soát truy cập phức tạp; mô hình MapReduce chưa tối ưu cho các tác vụ cần truy xuất dữ liệu theo thời gian thực (real-time processing).
  • Hạn chế xử lý tệp nhỏ: Hệ thống HDFS trong cấu hình mặc định hoạt động kém hiệu quả khi xử lý số lượng lớn các tệp tin kích thước nhỏ.

Hướng nghiên cứu tiếp

  • Mở rộng nghiên cứu và thực nghiệm các thuật toán song song khác trên các dạng cấu trúc đồ thị mở rộng và phức tạp hơn.
  • Triển khai thuật toán trên các cụm máy tính vật lý phân tán thực thụ (multi-node clusters) nhằm đo đạc chính xác các tham số truyền thông $t_{startup}$ và $t_{data}$.
  • Nghiên cứu kết hợp các mô hình lai (như kết hợp OpenMP với MPI hoặc tích hợp cơ chế đánh dấu tiến trình CAPE) để tối ưu hóa hiệu năng tính toán.

Giá trị tham khảo

Tài liệu là nguồn tham khảo hữu ích cho:

  • Sinh viên ngành Công nghệ Thông tin, Khoa học Máy tính: Tham khảo làm tài liệu hướng dẫn thực hành cho các học phần Lập trình song song, Hệ phân tán và Xử lý dữ liệu lớn.
  • Người nghiên cứu và phát triển phần mềm: Sử dụng trực tiếp quy trình từng bước tại Chương 2 để thiết lập môi trường phát triển C/C++ với MPI trên Visual Studio 2022 và hệ sinh thái Hadoop trên hệ điều hành Windows mà không cần cài đặt máy ảo Linux.
  • Nghiên cứu sinh, học viên làm đề tài tối ưu hóa đồ thị: Tham khảo cơ sở lý thuyết, các nguyên lý phân rã thuật toán song song và các công thức toán học đo lường hiệu năng/Amdahl tại Chương 1.

Câu hỏi thường gặp

1. Thời gian truyền thông $t_{comm}$ trong hệ thống truyền thông điệp được tính toán theo công thức nào?

Theo cơ sở lý thuyết của đồ án, thời gian truyền thông điệp được ước lượng bằng công thức: $$t_{comm} = t_{startup} + n \cdot t_{data}$$ Trong đó $t_{startup}$ là thời gian cần thiết để gửi các thông điệp điều khiển không phải dữ liệu (gồm thời gian đóng gói ở nơi gửi và mở gói ở nơi nhận), $t_{data}$ là thời gian chuyển một mục dữ liệu qua kênh truyền, và $n$ là số lượng từ dữ liệu được trao đổi trong hệ thống.

2. Kiến trúc của Apache Hadoop bao gồm những module cốt lõi nào?

Apache Hadoop được cấu thành từ 4 module chính:

  1. Hadoop Common: Các tiện ích và thư viện dùng chung cung cấp hệ thống tệp và lớp trừu tượng hệ điều hành.
  2. Hadoop YARN: Khung điều phối tài nguyên và quản lý vòng đời tiến trình trên toàn cụm.
  3. Hadoop Distributed File System (HDFS): Hệ thống tệp phân tán cung cấp khả năng truy cập dữ liệu thông lượng cao.
  4. Hadoop MapReduce: Khung tính toán dựa trên YARN chuyên trách xử lý song song các tập dữ liệu lớn.

3. Cần cấu hình các tập tin XML nào trong thư mục etc/hadoop khi cài đặt Hadoop?

Người triển khai cần hiệu chỉnh 4 tập tin XML chính:

  • core-site.xml: Khai báo cổng kết nối HDFS mặc định (fs.defaultFS / fs.default.name).
  • mapred-site.xml: Cấu hình dịch vụ theo dõi tác vụ (mapred.tracker).
  • hdfs-site.xml: Thiết lập số lượng bản sao dữ liệu (dfs.replication) và đường dẫn lưu trữ NameNode/DataNode.
  • yarn-site.xml: Khai báo các dịch vụ bổ trợ cho bộ điều phối YARN (yarn.nodemanager.aux-services).

4. Lệnh nào được sử dụng để chạy một chương trình C++ MPI với 4 tiến trình song song?

Sau khi biên dịch tệp nhị phân trong Visual Studio (ví dụ MPI_lau2.exe), người dùng mở giao diện dòng lệnh tại thư mục chứa tệp và thực thi câu lệnh:

mpiexec -np 4 MPI_lau2.exe

Tham số -np 4 chỉ định hệ thống khởi tạo đồng thời 4 tiến trình thực thi.

Kết luận

Đồ án "Hướng Dẫn Cài Đặt MPI và Hadoop cho Lập Trình Song Song" đã giải quyết trọn vẹn mục tiêu nghiên cứu lý thuyết nền tảng và cung cấp quy trình kỹ thuật thực tế cho việc triển khai môi trường tính toán song song, phân tán. Tác giả đã hệ thống hóa các mô hình lập trình, nguyên lý thiết kế giải thuật song song, cùng công thức toán học đánh giá hiệu năng và định luật Amdahl. Toàn bộ quy trình cài đặt MS-MPI trên Visual Studio 2022 và Apache Hadoop trên Windows được trình bày chi tiết từng bước và kiểm chứng thành công qua các thực nghiệm chạy chương trình mẫu. Đề tài mở ra hướng tiếp cận thuận tiện trong học tập, nghiên cứu và là cơ sở để tiếp tục phát triển các thuật toán song song hóa nâng cao cho bài toán tìm đường đi ngắn nhất trên đồ thị quy mô lớn.