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

Trong giai đoạn đầu thập niên 2000, nhu cầu tính toán trong các lĩnh vực khoa học và công nghệ tăng trưởng nhanh chóng. Để đáp ứng yêu cầu này, các nhà sản xuất vi xử lý liên tục đẩy mạnh tốc độ xung nhịp của bộ vi xử lý trung tâm (CPU). Điển hình trong giai đoạn 2001 - 2003, tốc độ của dòng vi xử lý Pentium 4 đã tăng gấp đôi từ 1.5 GHz lên 3.0 GHz. Tuy nhiên, hiệu năng thực tế không tăng tương xứng với mức gia tăng xung nhịp, đồng thời việc tăng xung nhịp nhanh chóng chạm phải ngưỡng giới hạn vật lý. Cụ thể, từ năm 2003 đến 2005, tốc độ CPU chỉ tăng thêm từ 3.0 GHz lên 3.8 GHz. Vấn đề nhiệt lượng tỏa ra quá cao khiến các giải pháp tản nhiệt không thể đáp ứng được khả năng làm mát khi CPU hoạt động ở mức xung nhịp tới hạn.

Trước bế tắc của việc tăng xung nhịp đơn nhân, các nhà nghiên cứu vi xử lý chuyển hướng sang phát triển công nghệ đa lõi, nhiều lõi và tích hợp cơ chế xử lý song song nhằm tăng hiệu năng tổng thể và tiết kiệm năng lượng. Bên cạnh CPU đa lõi, bộ xử lý đồ họa (GPU) vốn ban đầu chỉ phục vụ tăng tốc xử lý hình ảnh và trò chơi 3D đã có bước phát triển vượt bậc. Kể từ thế hệ GPU NV30 của NVIDIA, phần cứng đồ họa bắt đầu hỗ trợ tính toán dấu chấm động đơn và xử lý hàng ngàn lệnh, mở ra xu hướng tính toán đa mục đích trên GPU (GPGPU).

Năm 2007, hãng NVIDIA giới thiệu công nghệ CUDA (Compute Unified Device Architecture - Kiến trúc thiết bị hợp nhất cho tính toán), cho phép các lập trình viên sử dụng ngôn ngữ lập trình C để điều khiển trực tiếp GPU trong các bài toán tính toán hiệu năng cao. Nhằm giải quyết các bài toán dữ liệu lớn, độ phức tạp tính toán cao và giảm thiểu thời gian thực thi, nhóm tác giả đã chọn đề tài nghiên cứu: "Xây dựng thuật toán song song tìm đường đi ngắn nhất với CUDA".

Mục tiêu nghiên cứu của đề tài gồm:

  1. Nghiên cứu cơ sở lý thuyết về tính toán song song và công nghệ lập trình CUDA trên phần cứng GPU.
  2. Tìm hiểu và phân tích cấu trúc của các thuật toán tìm đường đi ngắn nhất kinh điển trên đồ thị (Dijkstra, Ford-Bellman, Floyd).
  3. Xây dựng, cài đặt phiên bản song song của các thuật toán tìm đường đi ngắn nhất bằng CUDA, từ đó chạy thử nghiệm, đánh giá và so sánh hiệu năng thực thi với các thuật toán tuần tự truyền thống trên CPU.

Đối tượng nghiên cứu của đề tài là lý thuyết tính toán song song, các giải thuật tìm đường đi ngắn nhất và kỹ thuật lập trình song song trên GPU qua nền tảng CUDA. Phạm vi nghiên cứu tập trung vào việc chuyển đổi từ mã nguồn tuần tự sang mã nguồn song song cho ba thuật toán Dijkstra, Ford-Bellman và Floyd trên các tập dữ liệu đồ thị có kích thước lớn.

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

Khung lý thuyết và mô hình tính toán

Khóa luận xây dựng nội dung dựa trên các nền tảng lý thuyết tính toán song song và lý thuyết đồ thị:

  • Kiến trúc phần cứng song song: Phân tích mô hình máy tính truyền thống Von Neumann và sự ra đời của các kiến trúc đa xử lý (Multiprocessor) và máy tính song song (Multicomputer). Áp dụng phân loại kiến trúc của Michael Flynn (1966) dựa trên dòng lệnh (instruction stream) và dòng dữ liệu (data stream):
    • SISD (Single Instruction Single Data): Đơn dòng lệnh, đơn dòng dữ liệu.
    • SIMD (Single Instruction Multiple Data): Đơn dòng lệnh, đa dòng dữ liệu (mô hình chủ đạo của GPU).
    • MISD (Multiple Instruction Single Data): Đa dòng lệnh, đơn dòng dữ liệu.
    • MIMD (Multiple Instruction Multiple Data): Đa dòng lệnh, đa dòng dữ liệu.
  • Mô hình bộ nhớ: Phân biệt hệ thống bộ nhớ chia sẻ (Shared Memory - bao gồm lớp truy cập đồng nhất UMA) và hệ thống bộ nhớ phân tán (Distributed Memory).
  • Mô hình lập trình song song: Mô hình truyền thông điệp (Message Passing) dành cho hệ phân tán và mô hình song song dữ liệu (Data Parallel) áp dụng cho các cấu trúc dữ liệu dạng mảng hoặc khối.
  • Nguyên lý thiết kế giải thuật song song: Nhận diện tính phụ thuộc dữ liệu (Data Dependency) để xác định các đoạn mã có thể song song hóa (ví dụ: phép cộng hai mảng độc lập) và các đoạn mã không thể song song hóa (ví dụ: tính dãy số Fibonacci $F(k+2) = F(k+1) + F(k)$).
  • Thuật toán tìm đường đi ngắn nhất trên đồ thị $G = (V, E)$:
    • Thuật toán Dijkstra: Tìm đường đi ngắn nhất từ một đỉnh xuất phát trên đồ thị có trọng số không âm bằng kỹ thuật gán nhãn tạm thời và cố định.
    • Thuật toán Ford-Bellman: Tìm đường đi ngắn nhất từ một đỉnh xuất phát, có khả năng xử lý đồ thị có trọng số âm (không chứa chu trình âm).
    • Thuật toán Floyd: Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị bằng phương pháp quy hoạch động với ma trận trọng số.
Tiêu chí so sánh Lập trình tính toán tuần tự Lập trình tính toán song song
Môi trường thực thi Chạy trên một bộ xử lý đơn (Single processor) Chạy trên hai hoặc nhiều bộ xử lý đồng thời
Thực thi chỉ thị Các câu lệnh được thực hiện tuần tự, lần lượt Các chỉ thị được các bộ xử lý thực hiện đồng thời
Xử lý dữ liệu Mỗi chỉ thị thao tác trên một thành phần dữ liệu Mỗi chỉ thị có thể thao tác trên nhiều thành phần dữ liệu
Nhiệm vụ lập trình viên Đảm bảo viết đúng mã lệnh theo giải thuật Xác định giải thuật, chỉ ra các đoạn mã chạy song song và quản lý luồng
Phạm vi áp dụng Bài toán dữ liệu nhỏ, độ phức tạp trung bình Bài toán dữ liệu lớn, độ phức tạp cao, yêu cầu xử lý nhanh

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

Đề tài kết hợp hai phương pháp nghiên cứu chính:

  1. Phương pháp nghiên cứu lý thuyết: Thu thập, tổng hợp và phân tích tài liệu chuyên khảo về tính toán song song, tài liệu kỹ thuật về công nghệ CUDA từ NVIDIA và các giáo trình thuật toán đồ thị. Trích lọc các nguyên lý phân chia dữ liệu để làm cơ sở thiết kế thuật toán song song.
  2. Phương pháp thực nghiệm:
    • Lập trình cài đặt thuật toán bằng ngôn ngữ C cho phiên bản tuần tự chạy trên CPU và CUDA C cho phiên bản song song chạy trên GPU.
    • Chạy thử nghiệm trên các bộ dữ liệu đồ thị có quy mô đỉnh khác nhau (từ vài trăm đến 15.000 đỉnh).
    • Đo lường và ghi nhận thời gian thực thi (execution time) để phân tích sự chênh lệch hiệu năng giữa hai phương pháp.

Thiết kế và triển khai

Kiến trúc phần mềm và phần cứng CUDA

Hệ thống tính toán CUDA phân định rõ ràng vai trò giữa hai thành phần:

  • Host: Bộ vi xử lý trung tâm (CPU) cùng bộ nhớ hệ thống (Host Memory/DRAM), chịu trách nhiệm điều phối, quản lý luồng chương trình chính và chuẩn bị dữ liệu.
  • Device: Bộ xử lý đồ họa (GPU) cùng bộ nhớ riêng trên card (Device Memory/DRAM), đóng vai trò bộ đồng xử lý đa luồng mức cao để thực thi các phép toán tính toán nặng.

Quy trình thực thi chương trình CUDA diễn ra qua ba bước:

  1. Cấp phát bộ nhớ trên Device (cudaMalloc) và sao chép dữ liệu từ Host sang Device (cudaMemcpy với cờ cudaMemcpyHostToDevice).
  2. Kích hoạt hàm nhân (kernel) trên Device với cấu hình thực thi xác định để xử lý song song dữ liệu.
  3. Sao chép dữ liệu kết quả từ Device về lại bộ nhớ Host (cudaMemcpy với cờ cudaMemcpyDeviceToHost) và giải phóng vùng nhớ.
+---------------+      cudaMemcpy (Host to Device)      +-----------------+
|  Host (CPU)   | ------------------------------------> |   Device (GPU)  |
| System Memory | <------------------------------------ |  Device Memory  |
+---------------+      cudaMemcpy (Device to Host)      +-----------------+

Phân cấp bộ nhớ và mô hình luồng

Mô hình bộ nhớ trên GPU bao gồm:

  • Registers: Bộ nhớ thanh ghi tốc độ cao nhất, cấp phát riêng cho từng luồng.
  • Local Memory: Bộ nhớ cục bộ của từng luồng.
  • Shared Memory: Bộ nhớ chia sẻ dùng chung cho các luồng trong cùng một khối (block), có tốc độ truy xuất nhanh và độ trễ thấp.
  • Global Memory: Bộ nhớ toàn cục có dung lượng lớn nhất trên DRAM của GPU, tất cả các luồng trong lưới (grid) đều có thể đọc/ghi nhưng có độ trễ cao.
  • Constant Memory & Texture Memory: Các vùng nhớ chỉ đọc được tối ưu hóa cho việc truy xuất dữ liệu hằng số hoặc dữ liệu hình ảnh.

Không gian thực thi của CUDA được tổ chức theo cấu trúc phân cấp:

  • Thread (Luồng): Đơn vị thực thi cơ bản, được định danh bằng chỉ số nội hợp threadIdx.
  • Block (Khối luồng): Tập hợp các luồng có thể chia sẻ bộ nhớ dùng chung và đồng bộ hóa; định danh bằng blockIdx, kích thước xác định bởi blockDim.
  • Grid (Lưới): Tập hợp các khối luồng cùng thực thi một kernel; kích thước xác định bởi gridDim.

Cú pháp gọi hàm kernel từ phía Host có dạng:

TenHamKernel<<<Dg, Db, Ns>>>(tham_so_1, tham_so_2, ...);

Trong đó Dg là kích thước của lưới (kiểu dim3), Db là kích thước của từng khối (kiểu dim3), và Ns là kích thước bộ nhớ chia sẻ động cấp phát thêm.

Kỹ thuật song song hóa các thuật toán đồ thị

  1. Thuật toán Dijkstra: Song song hóa quá trình tìm kiếm đỉnh có nhãn tạm thời nhỏ nhất và cập nhật nhãn cho các đỉnh kề. Ánh xạ các luồng tương ứng với các đỉnh của đồ thị để cập nhật khoảng cách đồng thời.
  2. Thuật toán Ford-Bellman:
    • Triển khai 1 chiều (1D): Sử dụng một lưới khối 1D và các luồng 1D để duyệt qua các đỉnh/cung nhằm thực hiện phép làm ngắn (relax) cạnh đồ thị.
    • Triển khai 2 chiều (2D): Tổ chức lưới và khối theo dạng ma trận 2D (tidX, tidY) dựa trên chỉ số blockIdx và threadIdx để duyệt đồng thời các cặp đỉnh trên ma trận kề: $$\text{index} = \text{tidY} \times n + \text{tidX}$$
  3. Thuật toán Floyd: Biến đổi thuật toán quy hoạch động với 3 vòng lặp tuần tự $O(N^3)$. Vòng lặp ngoài cùng theo đỉnh trung gian $k$ được giữ nguyên theo từng bước lặp, trong khi hai vòng lặp duyệt các cặp đỉnh $(i, j)$ được ánh xạ trực tiếp thành một lưới luồng 2D trên GPU. Mỗi luồng phụ trách tính toán và cập nhật giá trị cho một phần tử của ma trận khoảng cách $D[i, j] = \min(D[i, j], D[i, k] + D[k, j])$.

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

CHƯƠNG 1: TỔNG QUAN VỀ TÍNH TOÁN SONG SONG VÀ GPU

Chương 1 trình bày toàn diện lịch sử phát triển của kiến trúc máy tính từ mô hình Von Neumann đơn luồng đến các hệ thống máy tính song song. Nội dung tập trung phân tích lý do chuyển dịch sang tính toán song song do các giới hạn nhiệt độ và hiệu năng của CPU đơn lõi. Tác giả trình bày chi tiết phân loại kiến trúc máy tính của Flynn (SISD, SIMD, MISD, MIMD), các mô hình kiến trúc bộ nhớ chia sẻ (Shared Memory) và bộ nhớ phân tán (Distributed Memory).

Chương này cũng phân tích hai mô hình lập trình song song chính là mô hình truyền thông điệp (Message Passing) và mô hình song song dữ liệu (Data Parallel). Nguyên lý thiết kế giải thuật song song được xây dựng dựa trên việc phân chia bài toán, quản lý truy cập dữ liệu, phân chia tác vụ và đồng bộ tiến trình. Tác giả đưa ra các ví dụ cụ thể về bài toán có thể song song hóa (cộng hai mảng số nguyên) và bài toán không thể song song hóa do phụ thuộc dữ liệu tuần tự (dãy số Fibonacci).

Phần sau của chương giới thiệu lịch sử phát triển phần cứng GPU từ những con chip xử lý 2D thập niên 1970 - 1980 (ANTIC, Amiga, S3 86C911), sự hình thành của các API đồ họa (OpenGL, DirectX) đến các dòng GPU hiện đại hỗ trợ đổ bóng lập trình được. Cuối chương, tác giả so sánh kiến trúc giữa CPU và GPU: CPU dành phần lớn diện tích chip cho khối điều khiển và bộ nhớ đệm Cache để tối ưu hóa việc xử lý tuần tự, trong khi GPU dành phần lớn diện tích cho các đơn vị tính toán số học (ALU) phục vụ xử lý song song khối lượng lớn phép toán dấu chấm động.

CHƯƠNG 2: TÌM HIỂU VỀ CUDA VÀ THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT

Chương 2 đi sâu vào công nghệ CUDA của NVIDIA, bao gồm kiến trúc bộ phần mềm (Driver, API, Runtime, các thư viện CUBLAS, CUFFT) và các ứng dụng thực tiễn trong ngành công nghiệp trò chơi (PhysX, APEX) và xử lý video số (vReveal, Badaboom). Cơ chế hoạt động của chương trình CUDA theo mô hình SIMD được phân tích cùng với mô hình bộ nhớ phân cấp (Registers, Local, Shared, Global, Constant, Texture Memory).

Tác giả giải thích các phần mở rộng cú pháp của CUDA C so với C tiêu chuẩn:

  • Từ khóa định phạm vi hàm: __device__ (hàm chạy trên thiết bị, gọi từ thiết bị), __global__ (hàm kernel chạy trên thiết bị, gọi từ host), __host__ (hàm chạy trên host).
  • Từ khóa định phạm vi biến: __device__ (biến toàn cục trên thiết bị), __shared__ (biến trên bộ nhớ chia sẻ của khối).
  • Các biến nội hợp định danh luồng: gridDim, blockDim, blockIdx, threadIdx.
  • Quy trình biên dịch mã nguồn thông qua trình biên dịch NVCC.

Chương này minh họa cụ thể ba ví dụ lập trình CUDA: phép cộng hai số nguyên, phép cộng hai mảng số nguyên (sử dụng nhiều khối đơn luồng, một khối đa luồng hoặc kết hợp khối và luồng) và phép cộng hai ma trận vuông sử dụng lưới luồng 2D.

Phần cuối chương hệ thống hóa lý thuyết đồ thị cho bài toán tìm đường đi ngắn nhất, định nghĩa đường đi cơ bản, chu trình âm, ma trận trọng số và nguyên lý gán nhãn. Tác giả trình bày chi tiết thuật toán Dijkstra (cho đồ thị trọng số không âm), thuật toán Ford-Bellman (cho đồ thị có trọng số bất kỳ) và thuật toán Floyd (cho tất cả các cặp đỉnh), đồng thời tổng hợp tình hình nghiên cứu thuật toán song song trên thế giới và trong nước.

CHƯƠNG 3: XÂY DỰNG THUẬT TOÁN SONG SONG TÌM ĐƯỜNG ĐI NGẮN NHẤT VỚI CUDA

Chương 3 tập trung vào việc thiết kế và cài đặt mã nguồn song song hóa cho ba thuật toán Dijkstra, Ford-Bellman và Floyd bằng CUDA C. Tác giả tiến hành phân rã cấu trúc lặp tuần tự của từng thuật toán thành các kernel xử lý song song trên GPU:

  • Song song hóa Dijkstra thông qua việc phân chia các luồng kiểm tra và cập nhật nhãn khoảng cách của tập đỉnh.
  • Song song hóa Ford-Bellman theo hai phương án cấu hình luồng: cấu hình 1 chiều (CUDA 1D) và cấu hình 2 chiều (CUDA 2D) để tối ưu hóa việc duyệt qua các cạnh của đồ thị.
  • Song song hóa Floyd bằng cách chuyển đổi hai vòng lặp duyệt ma trận thành lưới luồng 2D trên GPU, mỗi luồng tính toán độc lập một ô của ma trận khoảng cách tại mỗi bước lặp của đỉnh trung gian $k$.

Toàn bộ các chương trình được chạy thử nghiệm thực tế để so sánh thời gian thực thi giữa mã tuần tự trên CPU và mã song song trên GPU. Các bảng số liệu thực nghiệm được tổng hợp chi tiết tại các bảng:

  • Bảng 3.1: Kết quả thực hiện thuật toán Dijkstra tuần tự và CUDA trên đồ thị lên đến 15.000 đỉnh.
  • Bảng 3.2: Kết quả thực hiện thuật toán Ford-Bellman tuần tự, CUDA 1D và CUDA 2D trên đồ thị lên đến 11.000 đỉnh.
  • Bảng 3.3: Kết quả thực hiện thuật toán Floyd tuần tự, CUDA 1D và CUDA 2D trên đồ thị lên đến 3.500 đỉnh.

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

Kết quả thực nghiệm

Khóa luận đã triển khai cài đặt hoàn chỉnh và thu thập số liệu thử nghiệm trên các bộ dữ liệu đồ thị có quy mô lớn:

  • Thuật toán Dijkstra: Thử nghiệm thành công trên đồ thị có quy mô lên tới 15.000 đỉnh (Hình 3.1, 3.2, 3.3). Phiên bản CUDA cho thấy sự vượt trội về thời gian xử lý so với phiên bản tuần tự khi số lượng đỉnh tăng cao.
  • Thuật toán Ford-Bellman: Đánh giá trên đồ thị lên tới 11.000 đỉnh (Hình 3.4, 3.5, 3.6, 3.7). Phiên bản CUDA 2D cho thấy hiệu quả phân chia dữ liệu tốt hơn mô hình CUDA 1D, giúp giảm thiểu đáng kể thời gian chạy so với thuật toán tuần tự trên CPU.
  • Thuật toán Floyd: Đánh giá trên đồ thị ma trận lên tới 3.500 đỉnh (Hình 3.8, 3.9, 3.10, 3.11). Nhờ loại bỏ được hai vòng lặp lồng nhau và xử lý đồng thời trên lưới luồng 2D của GPU, phiên bản CUDA giảm thời gian tính toán của giải thuật từ bậc $O(N^3)$ xuống mức thực thi nhanh hơn nhiều lần trên thực tế.

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

  1. Hệ thống hóa kiến thức: Cung cấp tài liệu tổng quan, có hệ thống về kiến trúc tính toán song song, phần cứng GPU và công nghệ lập trình NVIDIA CUDA tại thời điểm nghiên cứu (năm 2012).
  2. Thiết kế giải thuật: Đề xuất và hiện thực hóa thành công các mô hình phân chia luồng 1D và 2D cho các bài toán đồ thị kinh điển, chứng minh khả năng ứng dụng của GPGPU vào các bài toán phi đồ họa có cấu trúc dữ liệu ma trận.
  3. Thực nghiệm đối sánh: Xây dựng bộ dữ liệu kiểm thử và đo lường khách quan, cung cấp các biểu đồ và bảng dữ liệu thực nghiệm minh chứng rõ ràng sự khác biệt về hiệu năng giữa xử lý tuần tự trên CPU và xử lý song song trên GPU.

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

Hạn chế

  • Các thuật toán song song trong đề tài được triển khai trên một thiết bị GPU đơn lẻ (Single-GPU), chưa mở rộng trên các hệ thống phân tán kết hợp nhiều GPU (Multi-GPU).
  • Đối với các đồ thị có số lượng đỉnh nhỏ, chi phí thời gian sao chép dữ liệu giữa bộ nhớ Host và Device qua bus PCIe chiếm tỷ trọng lớn, làm giảm ưu thế của việc xử lý song song.
  • Một số bước tính toán vẫn mang tính tuần tự bắt buộc (như việc lựa chọn đỉnh cố định trong Dijkstra hoặc vòng lặp đỉnh trung gian $k$ trong Floyd), đòi hỏi phải có các rào đồng bộ luồng (synchronization), gây ảnh hưởng nhất định đến hiệu suất tối đa của GPU.

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

  • Nghiên cứu tối ưu hóa việc sử dụng các vùng nhớ tốc độ cao như Shared Memory và Texture Memory để giảm tần suất truy xuất vào Global Memory của GPU.
  • Mở rộng phạm vi nghiên cứu để song song hóa các thuật toán tìm đường đi ngắn nhất khác hoặc các bài toán luồng cực đại trên mạng.
  • Nghiên cứu kết hợp mô hình truyền thông điệp MPI với CUDA để xử lý bài toán trên các cụm máy tính hiệu năng cao (Cluster) tích hợp nhiều GPU.

Giá trị tham khảo

Đồ án là tài liệu tham khảo giá trị cho:

  • Sinh viên ngành Công nghệ Thông tin và Khoa học Máy tính: Tài liệu học tập hữu ích cho các môn học về Tính toán song song, Lập trình hiệu năng cao (HPC), Lý thuyết đồ thị và Cấu trúc dữ liệu và giải thuật.
  • Lập trình viên và nhà nghiên cứu công nghệ: Cung cấp kiến thức nền tảng và các ví dụ mã nguồn chi tiết về cách thiết lập cấu hình lưới luồng, cấp phát bộ nhớ và gọi hàm kernel trong CUDA C.
  • Phần đáng tham khảo nhất:
    • Mục 2.3 và 2.4 (Chương 2): Hướng dẫn chi tiết cú pháp mở rộng của CUDA C và các bài toán mẫu từ cấp độ 1D (cộng mảng) đến 2D (cộng ma trận).
    • Toàn bộ Chương 3: Phương pháp luận chuyển đổi giải thuật từ tuần tự sang song song và kỹ thuật tổ chức ánh xạ luồng 1D/2D cho bài toán ma trận đồ thị.

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

1. Đề tài tập trung song song hóa những thuật toán tìm đường đi ngắn nhất nào?

Khóa luận tập trung nghiên cứu, chuyển đổi và song song hóa ba thuật toán kinh điển trong lý thuyết đồ thị:

  • Thuật toán Dijkstra (tìm đường đi ngắn nhất từ một đỉnh trên đồ thị có trọng số không âm).
  • Thuật toán Ford-Bellman (tìm đường đi ngắn nhất từ một đỉnh, hỗ trợ trọng số âm).
  • Thuật toán Floyd (tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trên đồ thị).

2. Vì sao tác giả chọn công nghệ CUDA thay vì tính toán truyền thống trên CPU?

Tác giả chọn CUDA vì công nghệ này cho phép khai thác kiến trúc đa nhân của GPU với hàng ngàn đơn vị tính toán số học (ALU). Trong khi CPU truyền thống bị giới hạn tốc độ xung nhịp do vấn đề nhiệt độ và xử lý tuần tự chậm chạp trên các tập dữ liệu lớn, GPU với mô hình SIMD giúp phân chia dữ liệu ma trận đồ thị thành nhiều khối nhỏ để tính toán đồng thời, giúp rút ngắn đáng kể thời gian thực thi.

3. Khái niệm Host và Device trong lập trình CUDA được phân định như thế nào?

Trong kiến trúc CUDA:

  • Host đại diện cho CPU và bộ nhớ RAM của hệ thống, thực hiện nhiệm vụ điều khiển chung, chuẩn bị dữ liệu và phân phối tác vụ.
  • Device đại diện cho GPU và bộ nhớ card đồ họa (VRAM), thực hiện các tác vụ tính toán song song quy mô lớn thông qua các hàm kernel. Dữ liệu bắt buộc phải được sao chép từ Host sang Device trước khi tính toán và chuyển ngược lại sau khi hoàn thành.

4. Các biến nội hợp (built-in variables) nào được dùng để định vị luồng trong CUDA?

CUDA cung cấp 4 biến nội hợp chính để xác định vị trí của luồng trong không gian thực thi:

  • gridDim: Chứa kích thước (số lượng khối) của lưới.
  • blockDim: Chứa kích thước (số lượng luồng) của một khối.
  • blockIdx: Chứa chỉ số tọa độ của khối hiện tại trong lưới.
  • threadIdx: Chứa chỉ số tọa độ của luồng hiện tại trong khối.

5. Quy mô số đỉnh đồ thị lớn nhất được đưa vào thử nghiệm trong khóa luận là bao nhiêu?

Trong Chương 3, nhóm tác giả đã tiến hành thử nghiệm trên các tập dữ liệu đồ thị có quy mô lớn:

  • Thuật toán Dijkstra được thử nghiệm trên đồ thị lên đến 15.000 đỉnh (Bảng 3.1, Hình 3.2, 3.3).
  • Thuật toán Ford-Bellman được thử nghiệm trên đồ thị lên đến 11.000 đỉnh (Bảng 3.2, Hình 3.5, 3.6, 3.7).
  • Thuật toán Floyd được thử nghiệm trên ma trận đồ thị lên đến 3.500 đỉnh (Bảng 3.3, Hình 3.9, 3.10, 3.11).

Kết luận

Khóa luận tốt nghiệp "Xây dựng thuật toán song song tìm đường đi ngắn nhất với CUDA" của nhóm sinh viên Nguyễn Việt Đức và Nguyễn Nam Giang đã giải quyết thành công bài toán ứng dụng công nghệ tính toán đa mục đích trên GPU vào lĩnh vực lý thuyết đồ thị. Đề tài đã xây dựng cơ sở lý thuyết vững chắc về kiến trúc song song, phân tích chi tiết môi trường lập trình NVIDIA CUDA và triển khai cài đặt song song hóa thành công ba thuật toán Dijkstra, Ford-Bellman và Floyd theo các mô hình 1D và 2D. Kết quả thực nghiệm trên đồ thị quy mô lớn lên đến 15.000 đỉnh đã chứng minh tính đúng đắn của giải thuật và cho thấy ưu thế vượt trội về tốc độ xử lý của GPU so với phương pháp tính toán tuần tự trên CPU.