Tổng quan nghiên cứu

Trong kỷ nguyên phát triển mạnh mẽ của khoa học máy tính và tính toán hiệu năng cao (HPC), các bài toán mô phỏng vật lý, động lực học phân tử và giải hệ phương trình tuyến tính quy mô lớn thường xuyên phải xử lý những ma trận có kích thước từ hàng chục nghìn đến hàng triệu phần tử. Trong thực tế, các ma trận này thường có cấu trúc thưa với mật độ phần tử khác không chiếm tỷ lệ cực kỳ nhỏ, thông thường dưới 1% tổng thể tích ma trận. Phép nhân ma trận thưa với véctơ (SpMV) đóng vai trò là hạt nhân tính toán lặp đi lặp lại trong các thuật toán đại số tuyến tính như phương pháp Gradient liên hợp hay thuật toán Lanczos. Tuy nhiên, việc thực thi phép toán này trên các kiến trúc máy tính tuần tự truyền thống gặp phải rào cản nghiêm trọng về giới hạn dung lượng bộ nhớ và thời gian xử lý kéo dài.

Luận văn tập trung nghiên cứu và thiết kế các thuật toán song song hóa phép nhân ma trận thưa với véctơ nhằm khai thác tối đa sức mạnh của hệ thống đa bộ xử lý, tối ưu hóa thời gian tính toán và giảm thiểu chi phí truyền thông liên nút. Mục tiêu cụ thể của đề tài là xây dựng các cấu trúc dữ liệu lưu trữ nén tối ưu, thiết kế thuật toán phân hoạch ma trận hai chiều kết hợp phân phối véctơ biên địa phương và triển khai thực nghiệm kiểm chứng trên môi trường cụm máy tính. Nghiên cứu được thực hiện tại Hà Nội trong giai đoạn năm 2011, khảo sát trên các bộ dữ liệu ma trận chuẩn quốc tế có quy mô từ 1.000 đến hơn 20.000 chiều. Ý nghĩa thực tiễn của công trình thể hiện qua việc nâng cao hệ số tăng tốc tính toán từ 3,2 đến 3,8 lần trên cấu hình 4 bộ xử lý và giảm hơn 35% chi phí truyền thông so với các phương pháp phân hoạch một chiều truyền thống.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu vận dụng khung lý thuyết phân loại kiến trúc máy tính của Flynn, tập trung khai thác mô hình đa luồng lệnh - đa luồng dữ liệu (MIMD) kết hợp kiến trúc bộ nhớ phân tán và truy cập bộ nhớ không đồng nhất (NUMA). Nền tảng phân tích hiệu năng dựa trên Định luật Amdahl xác định giới hạn tăng tốc lý thuyết và mô hình chi phí thời gian song song toàn phần: thời gian thực thi bằng tổng thời gian tính toán nội bộ và thời gian truyền thông dữ liệu. Trong đó, thời gian truyền thông được mô hình hóa chặt chẽ qua độ trễ khởi tạo gói tin (startup time) và thời gian truyền dẫn thực tế trên mỗi đơn vị từ dữ liệu.

Về mặt cấu trúc dữ liệu, luận văn phân tích chuyên sâu 5 kỹ thuật lưu trữ ma trận thưa điển hình: Lược đồ tọa độ (COO), Lưu trữ nén hàng (CRS), Lưu trữ nén cột (CCS), Lưu trữ nén hàng có gia số (ICRS) và Lưu trữ đường chéo răng cưa (JDS). Cấu trúc ICRS nổi bật với khả năng tối ưu hóa việc truy cập bộ nhớ trực tiếp thay vì định chỉ số gián tiếp, giúp loại bỏ mảng con trỏ phụ và tiết kiệm tới 33% chi phí quản lý bộ nhớ. Về mặt giao tiếp liên tiến trình, giao diện truyền thông điệp chuẩn MPI-2 cùng gói hỗ trợ tính toán cụm Microsoft Compute Cluster Pack (MSMPI SDK) được sử dụng để thiết lập các kênh truyền thông điểm - điểm và truyền thông tập thể hiệu năng cao.

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

Phương pháp nghiên cứu kết hợp chặt chẽ giữa mô hình hóa toán học, thiết kế thuật toán song song và thực nghiệm đối chuẩn. Cỡ mẫu nghiên cứu bao gồm 6 bộ dữ liệu ma trận thưa chuẩn quốc tế được trích xuất từ các thư viện Matrix Market, Harwell-Boeing và Rutherford-Boeing, tiêu biểu như: bcsstk13, lp_cycle, onetone2, epb2, nasa2910 và random20k. Phương pháp chọn mẫu có chủ đích được áp dụng nhằm bao phủ đa dạng các đặc tính cấu trúc: ma trận đối xứng, ma trận phi đối xứng, ma trận khối đường chéo và ma trận phân tán ngẫu nhiên với kích thước từ 1.000 đến 20.000 hàng.

Lý do lựa chọn phương pháp phân tích phân hoạch hai chiều (2D Cartesian Partitioning) kết hợp thuật toán Mondrian và giải thuật biên địa phương (LA/LAvu) là vì phương pháp này cho phép tách biệt độc lập giai đoạn phân bổ ma trận với giai đoạn phân bổ véctơ đầu vào và đầu ra. Quy trình thực hiện gồm 4 bước mạch lạc: Phân hoạch miền dữ liệu, Xác định sơ đồ truyền thông, Tích hợp tác vụ và Ánh xạ lên các bộ xử lý. Timeline thực nghiệm được tiến hành liên tục trong 6 tháng, đối chuẩn trực tiếp giữa thuật toán tuần tự trên 1 CPU và thuật toán song song trên các cấu hình 2, 4 và 8 bộ xử lý.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Thứ nhất, việc áp dụng cấu trúc dữ liệu lưu trữ nén dòng có gia số (ICRS) đã giảm thiểu đáng kể hiện tượng trượt bộ nhớ đệm (cache miss). So với cấu trúc CRS truyền thống, ICRS giúp giảm từ 12% đến 15% thời gian tính toán nội bộ tại mỗi nút nhờ loại bỏ việc tra cứu gián tiếp mảng chỉ số cột.

Thứ hai, thuật toán phân hoạch ma trận hai chiều kết hợp giải thuật biên địa phương (LA) đã tạo ra bước đột phá về kiểm soát số lượng thông điệp truyền thông. Trên bộ dữ liệu thử nghiệm random20k với kích thước 20.000 x 20.000 phần tử, thuật toán đã khống chế số lượng thông điệp cực đại gửi đi trên mỗi bộ xử lý ở mức 2 nhân căn bậc hai của số bộ xử lý trừ 1, thay vì mức P trừ 1 thông điệp như mô hình phân hoạch một chiều. Khi thử nghiệm trên 4 bộ xử lý, số liên kết trao đổi giữa các nút giảm từ 3 xuống còn 2 kênh chính, giúp giảm 35% dung lượng dữ liệu cần luân chuyển qua mạng.

Thứ ba, hệ số tăng tốc đạt mức tối ưu rõ rệt đối với các ma trận có số lượng phần tử khác không lớn và phân bố đều. Đối với các ma trận bcsstk13 và lp_cycle, hệ số tăng tốc đạt xấp xỉ 3,65 lần trên 4 bộ xử lý, tương đương hiệu suất tính toán đạt trên 91,2%. Khi mở rộng thử nghiệm trên hệ thống mô phỏng cụm 8 nút tính toán, tổng thời gian thực thi giảm mạnh từ 14,8 giây xuống còn 2,1 giây, đạt mức tăng tốc hơn 7,0 lần.

Thảo luận kết quả

Sự vượt trội của thuật toán phân phối véctơ đồng thời (LAvu) bắt nguồn từ cơ chế tách rời việc tối ưu hóa cân bằng tải truyền thông sau khi đã hoàn tất cân bằng tải tính toán của các khối ma trận. Trong các mô hình phân hoạch đồ thị một chiều truyền thống, việc áp đặt phân phối véctơ trùng với phân phối hàng ma trận thường dẫn đến tình trạng mất cân bằng nghiêm trọng khi một số nút mạng phải nhận quá nhiều thành phần véctơ đầu vào.

Dữ liệu thực nghiệm được trình bày trực quan thông qua bảng thống kê thời gian thực thi và biểu đồ phân bố mật độ thưa của các ma trận epb2 hay nasa2910. Biểu đồ hình học thưa mô tả rõ nét cách các phần tử khác không được gom cụm tối ưu vào các miền cục bộ, trong khi bảng so sánh phản ánh chi tiết độ trễ khởi tạo chỉ chiếm khoảng 4% đến 6% tổng thời gian thực thi nhờ khả năng gộp gói tin truyền thông trong MPI. Kết quả này chứng minh rằng việc kết hợp giữa phân hoạch ma trận 2D và phân phối véctơ LA giúp các cụm máy trạm (WSC) đạt được hiệu năng tiệm cận các siêu máy tính đắt tiền với chi phí đầu tư phần cứng tiết kiệm hơn nhiều lần.

Đề xuất và khuyến nghị

Thứ nhất, chuẩn hóa và tích hợp cấu trúc dữ liệu lai ICRS vào các thư viện tính toán đại số tuyến tính trong nước. Các trung tâm tính toán hiệu năng cao cần triển khai cập nhật các module xử lý ma trận thưa, đặt mục tiêu nâng cao thông lượng tính toán lên ít nhất 25% trong lộ trình 12 tháng tới, do các kỹ sư phần mềm hệ thống chủ trì thực hiện.

Thứ hai, ứng dụng giải thuật phân hoạch hai chiều Mondrian và phân phối véctơ biên địa phương vào các phần mềm mô phỏng công nghiệp và dự báo thời tiết. Mục tiêu cụ thể là rút ngắn thời gian xử lý các mô hình lưới không gian 3D quy mô trên 50.000 nút lưới xuống dưới 30 phút, hoàn thành tích hợp trong vòng 6 đến 9 tháng bởi các nhóm nghiên cứu khoa học tính toán.

Thứ ba, tối ưu hóa hạ tầng truyền thông nội bộ trên các cụm máy trạm bằng cách chuyển đổi sang các thiết bị chuyển mạch mạng hiệu năng cao với băng thông từ 2 Gbps trở lên. Đơn vị quản trị hệ thống tại các viện nghiên cứu và trường đại học cần thực hiện kiểm tra định kỳ 6 tháng một lần để duy trì độ trễ truyền thông dưới 10 micro-giây.

Thứ tư, xây dựng khung chương trình đào tạo chuyên sâu về kỹ nghệ lập trình song song trên nền tảng MPI và OpenMP cho bậc sau đại học. Các cơ sở giáo dục đại học trọng điểm cần đặt mục tiêu đào tạo trên 500 kỹ sư và chuyên gia tính toán song song chất lượng cao trong giai đoạn 2 năm tới.

Đối tượng nên tham khảo luận văn

Nhóm nghiên cứu và phát triển phần mềm hiệu năng cao (HPC): Khai thác các thuật toán phân hoạch ma trận hai chiều và cấu trúc nén ICRS để xây dựng các thư viện tính toán lõi cho hệ thống cụm máy chủ phân tán.

Học viên cao học và nghiên cứu sinh ngành Khoa học máy tính, Toán tin ứng dụng: Sử dụng luận văn như một tài liệu tham khảo chuẩn mực về phương pháp luận song song hóa, quy trình đánh giá độ phức tạp tính toán và kỹ thuật lập trình MPI trên môi trường Microsoft Visual Studio.

Kỹ sư mô phỏng động lực học, cơ học kết cấu và kỹ thuật công trình: Áp dụng trực tiếp thuật toán nhân ma trận thưa với véctơ để giải các hệ phương trình vi phân đạo hàm riêng rời rạc, tính toán mạng lưới điện và mô phỏng tương tác vật lý với thời gian thực thi giảm trên 60%.

Chuyên gia phân tích dữ liệu lớn và Trí tuệ nhân tạo (AI): Vận dụng kỹ thuật lưu trữ nén và xử lý song song ma trận thưa vào việc tối ưu hóa mạng nơ-ron quy mô lớn, thuật toán lan truyền đồ thị và các hệ thống gợi ý chứa dữ liệu thưa với hàng triệu người dùng.

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

  1. Phép nhân ma trận thưa với véctơ (SpMV) có gì khác biệt so với nhân ma trận dày thông thường? Trong ma trận thưa, tỷ lệ phần tử khác không thường chiếm dưới 5% tổng thể tích ma trận. Thuật toán SpMV bỏ qua toàn bộ các phép tính với giá trị 0 và chỉ lưu trữ các phần tử thực tế bằng cấu trúc nén như CRS hay ICRS, giúp tiết kiệm hơn 90% bộ nhớ RAM và giảm đáng kể thời gian xử lý của CPU.

  2. Tại sao cấu trúc dữ liệu ICRS lại mang lại hiệu năng cao hơn cấu trúc CRS? Cấu trúc ICRS mã hóa tọa độ phần tử bằng chuỗi gia số một chiều đơn điệu tăng, giúp chương trình truy cập trực tiếp vào các phần tử của véctơ mà không cần thông qua mảng chỉ số cột phụ. Cơ chế này giúp giảm thiểu hiện tượng truy cập bộ nhớ gián tiếp, hạn chế lỗi bộ nhớ đệm và tăng tốc độ xử lý khoảng 15%.

  3. Phân hoạch ma trận hai chiều (2D) vượt trội hơn phân hoạch một chiều (1D) ở điểm nào? Phân hoạch 1D tạo ra số lượng liên kết truyền thông lớn tỷ lệ thuận với số bộ xử lý, dễ gây nghẽn mạng khi mở rộng hệ thống. Phân hoạch 2D phân chia đồng thời cả hàng và cột, giúp giảm số thông điệp cực đại trên mỗi nút xuống mức 2 nhân căn bậc hai của số bộ xử lý trừ 1, đảm bảo cân bằng tối ưu cả tải tính toán lẫn tải truyền thông.

  4. Luận văn đã sử dụng môi trường và công cụ lập trình song song nào để kiểm thử? Nghiên cứu sử dụng giao diện truyền thông điệp MPI chuẩn với gói Microsoft Compute Cluster Pack (MSMPI SDK), kết hợp môi trường phát triển Microsoft Visual Studio C/C++. Các chương trình thực thi được điều phối thông qua trình quản lý tiến trình mpiexec trên cấu hình từ 2 đến 8 bộ xử lý kết nối mạng tốc độ cao.

  5. Làm thế nào để áp dụng kết quả nghiên cứu vào các bài toán thực tế quy mô lớn? Các nhóm nghiên cứu có thể nhập ma trận từ định dạng chuẩn Matrix Market vào module phân hoạch LA và cấu trúc ICRS được đề xuất trong luận văn, sau đó ánh xạ lên hệ thống cụm máy chủ để giải quyết các hệ phương trình tuyến tính lớn chỉ trong vài giây.

Kết luận

  • Luận văn đã hệ thống hóa toàn diện cơ sở lý thuyết về tính toán song song, kiến trúc máy tính MIMD, mô hình truyền thông điệp MPI-2 và các chuẩn lưu trữ ma trận thưa tiên tiến.
  • Thiết kế thành công thuật toán song song nhân ma trận thưa với véctơ dựa trên cấu trúc dữ liệu nén ICRS và kỹ thuật phân hoạch hai chiều kết hợp thuật toán biên địa phương (LA/LAvu).
  • Chứng minh bằng thực nghiệm trên 6 bộ dữ liệu chuẩn quốc tế với hệ số tăng tốc đạt từ 3,2 đến 3,8 lần trên 4 bộ xử lý, giảm hơn 35% lưu lượng truyền thông so với các mô hình truyền thống.
  • Đóng góp giải pháp công nghệ có tính ứng dụng cao trong các lĩnh vực mô phỏng động lực học, dự báo thời tiết, cơ học tính toán và xử lý dữ liệu lớn trên nền tảng cụm máy tính chi phí thấp.
  • Trong giai đoạn 12 tháng tiếp theo, hướng phát triển tiềm năng là mở rộng thuật toán trên kiến trúc tính toán lai GPU-CPU đa luồng. Hãy tham khảo và ứng dụng ngay các giải pháp thuật toán từ luận văn để tối ưu hóa hiệu năng cho các hệ thống tính toán khoa học của bạn!