Luận văn thạc sĩ vnu uet song song hoá bước biểu diễn cây bát phân trong thuật toán nhanh giải bài toán n body và tính toán thử nghiệm trên pc cluster

Luận văn thạc sĩ nghiên cứu vnu uet song song hoá bước biểu diễn cây bát phân trong thuật toán nhanh giải bài toán n body và, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện

• Tác giả: Tào Thị Thu Phượng
• Người hướng dẫn: TS. Nguyễn Hải Châu
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Song song hoá bước biểu diễn cây bát phân trong thuật toán nhanh giải bài toán N-body và tính toán thử nghiệm trên PC-Cluster
• Loại tài liệu: Luận văn thạc sỹ
• Năm xuất bản: 2004
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• DANH MỤC CÁC TỪ VIẾT TẮT
• DANH MỤC BẢNG BIỂU HÌNH VẼ
• MỞ ĐẦU
• 1. CHƯƠNG 1: BÀI TOÁN MÔ PHỎNG N-BODY VÀ MÔ HÌNH SONG SONG
• 1.1. Bài toán mô phỏng N-body
• 1.1.1. Giới thiệu
• 1.2. Các bước trong quy trình giải bài toán mô phỏng N-body
• 1.3. Các giải pháp tăng tốc độ tính lực cho bài toán mô phỏng N-body
• 1.3.1. Phần cứng đặc biệt
• 1.3.2. Thuật toán nhanh
• 1.3.3. Thuật toán song song

Tóm tắt

I. Giới thiệu về luận văn thạc sĩ VNU UET và cây bát phân

Luận văn thạc sĩ VNU UET tập trung vào việc song song hóa bước biểu diễn cây bát phân trong thuật toán nhanh giải bài toán N-body. Bài toán N-body là một trong những thách thức lớn trong lĩnh vực mô phỏng vật lý, đặc biệt là trong các nghiên cứu về thiên văn học và vật lý hạt. Việc áp dụng cây bát phân giúp giảm độ phức tạp tính toán, từ đó tăng tốc độ xử lý. Luận văn này không chỉ trình bày lý thuyết mà còn thực hiện các thử nghiệm trên hệ thống PC Cluster.

1.1. Tổng quan về bài toán N body và ứng dụng

Bài toán N-body mô phỏng sự tương tác giữa nhiều hạt trong không gian. Ứng dụng của nó rất đa dạng, từ mô phỏng thiên hà đến nghiên cứu động lực học nguyên tử. Việc hiểu rõ về bài toán này là cần thiết để phát triển các thuật toán hiệu quả hơn.

1.2. Cây bát phân và vai trò trong thuật toán N body

Cây bát phân là một cấu trúc dữ liệu quan trọng giúp tổ chức và tính toán lực tương tác giữa các hạt. Nó cho phép giảm độ phức tạp tính toán từ O(N^2) xuống O(N log N), giúp tăng tốc độ xử lý trong các bài toán lớn.

II. Thách thức trong việc giải bài toán N body

Giải bài toán N-body gặp nhiều thách thức, đặc biệt là khi số lượng hạt tăng lên. Độ phức tạp tính toán cao dẫn đến thời gian xử lý lâu, ảnh hưởng đến khả năng mô phỏng. Việc tính lực tương tác giữa các hạt là giai đoạn tốn thời gian nhất, chiếm khoảng 90% tổng thời gian mô phỏng. Do đó, cần có các giải pháp tối ưu hóa để cải thiện hiệu suất.

2.1. Độ phức tạp tính toán và ảnh hưởng đến hiệu suất

Độ phức tạp tính toán của bài toán N-body là O(N^2), điều này có nghĩa là thời gian xử lý tăng theo bình phương số lượng hạt. Khi số lượng hạt lớn, thời gian tính toán trở thành một vấn đề nghiêm trọng.

2.2. Các phương pháp tối ưu hóa hiện có

Một số phương pháp tối ưu hóa đã được đề xuất như thuật toán Barnes-Hut và Fast Multipole Method (FMM). Những phương pháp này giúp giảm thời gian tính toán và cải thiện hiệu suất mô phỏng.

III. Phương pháp song song hóa cây bát phân trong N body

Phương pháp song song hóa cây bát phân là một trong những giải pháp hiệu quả để tăng tốc độ tính toán trong bài toán N-body. Bằng cách chia nhỏ dữ liệu và phân phối cho nhiều bộ xử lý, thời gian tính toán có thể giảm đáng kể. Luận văn này sẽ trình bày chi tiết về cách thức thực hiện song song hóa và các kết quả đạt được.

3.1. Nguyên tắc phân chia dữ liệu trong song song hóa

Phân chia dữ liệu là bước quan trọng trong quá trình song song hóa. Dữ liệu về các hạt sẽ được chia đều cho các bộ xử lý, giúp tối ưu hóa thời gian tính toán và sử dụng tài nguyên hiệu quả.

3.2. Cài đặt và thử nghiệm trên PC Cluster

Việc cài đặt chương trình thử nghiệm trên hệ thống PC Cluster cho phép kiểm tra hiệu suất của thuật toán song song hóa. Kết quả thử nghiệm sẽ được phân tích để đánh giá tính hiệu quả của phương pháp.

IV. Kết quả nghiên cứu và ứng dụng thực tiễn

Kết quả nghiên cứu cho thấy việc song song hóa cây bát phân đã cải thiện đáng kể tốc độ tính toán trong bài toán N-body. Các thử nghiệm trên PC Cluster cho thấy thời gian xử lý giảm đi nhiều lần so với phương pháp truyền thống. Điều này mở ra nhiều cơ hội ứng dụng trong các lĩnh vực nghiên cứu khác nhau.

4.1. Đánh giá hiệu suất của thuật toán song song

Kết quả thử nghiệm cho thấy thuật toán song song hóa cây bát phân có thể giảm thời gian tính toán từ hàng giờ xuống chỉ còn vài phút. Điều này chứng tỏ tính hiệu quả của phương pháp.

4.2. Ứng dụng trong các lĩnh vực nghiên cứu

Phương pháp này không chỉ áp dụng trong mô phỏng N-body mà còn có thể được mở rộng ra nhiều lĩnh vực khác như mô phỏng động lực học, vật lý thiên văn và đồ họa máy tính.

V. Kết luận và hướng phát triển tương lai

Luận văn đã trình bày một cách chi tiết về việc song song hóa bước biểu diễn cây bát phân trong thuật toán nhanh giải bài toán N-body. Kết quả đạt được cho thấy tiềm năng lớn trong việc cải thiện hiệu suất tính toán. Hướng phát triển tương lai có thể bao gồm việc áp dụng các công nghệ mới và tối ưu hóa hơn nữa các thuật toán hiện có.

5.1. Tóm tắt những đóng góp chính của luận văn

Luận văn đã đóng góp vào việc phát triển các phương pháp tính toán hiệu quả hơn cho bài toán N-body, đồng thời mở ra hướng nghiên cứu mới trong lĩnh vực này.

5.2. Định hướng nghiên cứu trong tương lai

Nghiên cứu có thể tiếp tục mở rộng sang các lĩnh vực khác, áp dụng các công nghệ mới như trí tuệ nhân tạo để tối ưu hóa hơn nữa các thuật toán tính toán.

Nội dung chính

Tổng quan nghiên cứu

Trong lĩnh vực mô phỏng số và tính toán khoa học, bài toán tương tác $N$ vật thể ($N$-body) đóng vai trò nền tảng để mô hình hóa các hiện tượng tự nhiên từ quy mô vi mô như động lực học phân tử đến quy mô vĩ mô như chuyển động của các thiên hà. Thách thức lớn nhất của bài toán nằm ở việc tính toán lực tương tác trực tiếp giữa từng cặp hạt với độ phức tạp tính toán lên tới $O(N^2)$, trong đó giai đoạn tính lực thường chiếm tới 90% đến 95% tổng thời gian thực thi của toàn bộ chương trình mô phỏng. Khi số lượng hạt mở rộng lên đến hàng triệu phần tử và quá trình mô phỏng đòi hỏi hơn 10.000 bước thời gian, các hệ thống máy tính tuần tự đơn lẻ hoàn toàn không đủ khả năng đáp ứng yêu cầu về thời gian và tài nguyên.

Nhằm giải quyết nút thắt cổ chai này, công trình tập trung nghiên cứu, thiết kế và song song hóa bước biểu diễn cây bát phân (oct-tree) kết hợp với thuật toán khai triển đa cực nhanh (Fast Multipole Method - FMM) để giải bài toán $N$-body trên hệ thống cụm máy tính cá nhân (PC-Cluster). Nghiên cứu được tiến hành trong khuôn khổ thực nghiệm tại Khoa Công nghệ thuộc Đại học Quốc gia Hà Nội vào năm 2004, ứng dụng môi trường tính toán cụm gồm 8 bộ vi xử lý chạy hệ điều hành Linux và thư viện truyền thông điệp MPI.

Ý nghĩa cốt lõi của nghiên cứu thể hiện qua việc giảm độ phức tạp thuật toán từ $O(N^2)$ xuống mức tuyến tính $O(N)$, đồng thời tăng tốc độ xử lý tính toán lực lên hơn 5,6 lần trên cấu hình 8 nút mạng so với xử lý tuần tự. Công trình mở ra giải pháp xây dựng hệ thống tính toán hiệu năng cao với chi phí đầu tư thấp, thay thế hiệu quả cho các hệ thống phần cứng chuyên dụng đắt đỏ có giá thành vượt mức 10.000 USD tại thời điểm nghiên cứu.

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 được xây dựng dựa trên sự kết hợp chặt chẽ giữa các lý thuyết vật lý toán học và các nguyên lý tính toán song song hiện đại:

• Lý thuyết trường thế và Thuật toán khai triển đa cực nhanh (FMM): Dựa trên định luật tĩnh điện Coulomb, phương trình Laplace và các bổ đề giải tích phức Cauchy-Riemann. Thuật toán phân tách không gian thành các cụm hạt tách biệt, chuyển đổi tương tác xa giữa các nhóm hạt thành các khai triển đa cực (Multipole Expansion - ME) và khai triển địa phương (Local Expansion - LE) qua chuỗi Taylor, giúp giảm thiểu tối đa số phép tính cặp đôi.
• Lý thuyết cấu trúc dữ liệu cây không gian và Đường cong lấp đầy không gian (Space-Filling Curves - SFC): Không gian ba chiều chứa $N$ hạt được biểu diễn phân cấp dưới dạng cây bát phân với độ sâu $h \approx \log_8 N$. Để khắc phục nhược điểm của cấu trúc con trỏ truyền thống trong môi trường phân tán, nghiên cứu ứng dụng phương pháp mã hóa tọa độ thành chuỗi bit khóa nhị phân Morton và Peano-Hilbert kết hợp bảng băm không gian (Spatial Hash Table).
• Khái niệm cốt lõi: Các khái niệm mấu chốt bao gồm Khai triển đa cực, Danh sách tương tác (Interaction List), Bảng băm không gian truy xuất tức thời với độ phức tạp $O(1)$, Cân bằng tải song song (Load Balancing), và Mô hình tính toán Đơn chương trình - Đa dữ liệu (SPMD).

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

Nghiên cứu sử dụng phương pháp thực nghiệm kết hợp phân tích thuật toán định lượng với quy trình chặt chẽ:

• Nguồn dữ liệu và cỡ mẫu thử nghiệm: Tập dữ liệu nghiên cứu bao gồm các tập dữ liệu tổng hợp với quy mô hạt biến thiên từ 8.000 hạt (8k) đến 2.048.000 hạt (2048k) trong không gian 3 chiều. Case study cụ thể áp dụng mô phỏng quá trình va chạm và hợp nhất giữa hai thiên hà với quy mô 2.048 thiên thể qua 180 bước thời gian mô phỏng (tương ứng từ thời điểm ban đầu $t = 0$ đến khi va chạm hoàn tất tại $t = 7,087$).
• Phương pháp chọn mẫu: Lựa chọn mẫu phân bố hạt theo cả hai dạng: phân bố cụm mật độ không đồng nhất (đặc trưng cho cấu trúc thiên hà) và phân bố ngẫu nhiên đồng đều trong không gian hộp lập phương ba chiều, đảm bảo đánh giá toàn diện khả năng cân bằng tải của thuật toán.
• Lý do lựa chọn phương pháp phân tích: Ngôn ngữ lập trình C kết hợp chuẩn giao diện truyền thông điệp MPI (Message Passing Interface) trên nền tảng Linux PC-Cluster được chọn vì khả năng quản lý bộ nhớ trực tiếp, tính tương thích cao và độ trễ thấp trong giao tiếp mạng. Timeline thực nghiệm được tiến hành qua các chu kỳ lặp từ kiểm thử tuần tự đơn bước đến mô phỏng song song đa bước thời gian dài hạn.

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

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

Quá trình thực nghiệm đối sánh giữa các thuật toán và mô hình tính toán đã mang lại 4 phát hiện quan trọng:

• Tối ưu hóa thời gian tính lực trực tiếp: Khi thử nghiệm với tập dữ liệu quy mô 8.000 hạt ở 1 bước thời gian mô phỏng, chương trình tính lực tuần tự mất 19,63 giây. Trong khi đó, chương trình song song hóa trên cụm PC-Cluster gồm 8 bộ vi xử lý chỉ mất 3,46 giây, giúp rút ngắn thời gian xử lý tới 82,37% và đạt tốc độ tăng tốc (speedup) xấp xỉ 5,67 lần.
• Hiệu năng vượt trội của cây bát phân dùng bảng băm: Việc thay thế con trỏ móc nối bằng mảng khóa nhị phân và bảng băm giúp thời gian tạo cây bát phân đạt hiệu quả cao. Với quy mô 8.192 hạt ở độ cao cây bằng 4, thời gian tạo cây tuần tự chỉ mất 0,62 giây, đồng thời cho phép truy xuất trực tiếp các nút con và nút láng giềng với thời gian $O(1)$.
• Độ co giãn khi tăng kích thước bài toán: Khi số lượng hạt tăng từ 8k lên 2.048k, độ cao cây tăng tương ứng từ mức 4 lên mức 7. Cấu trúc cây bát phân băm thể hiện tính ổn định cao, không xảy ra hiện tượng tràn bộ nhớ cục bộ trên từng nút xử lý.
• Hiệu quả phân chia dữ liệu bằng đường cong Peano-Hilbert: Phương pháp phân chia miền dữ liệu dựa trên đường cong SFC theo thứ tự Peano-Hilbert duy trì tính liên tục cục bộ không gian tốt hơn đáng kể so với mã Morton, giúp giảm xung đột truyền thông giữa các bộ vi xử lý khoảng 15% đến 20%.

Thảo luận kết quả

Nguyên nhân chính dẫn đến sự cải thiện hiệu năng vượt bậc là việc giải phóng hoàn toàn sự phụ thuộc vào cấu trúc con trỏ phân tán. Trong môi trường tính toán cụm không chia sẻ bộ nhớ, việc gửi dữ liệu cây dạng con trỏ đòi hỏi chi phí đóng gói rất lớn. Bằng cách mã hóa vị trí hạt thành các khóa bit nguyên và lưu trong mảng phẳng kết hợp bảng băm, các tiến trình MPI có thể đóng gói và truyền tải thông tin biên qua hàm phát sóng MPI_Bcast một cách tối ưu.

Khi so sánh với các giải pháp phần cứng chuyên dụng như hệ thống GRAPE-4 hay MDGRAPE-2 (với chi phí khoảng 10.000 USD cho một bo mạch đơn lẻ vào những năm 1999–2004), giải pháp PC-Cluster kết hợp cây bát phân song song chứng minh tính khả thi kinh tế vượt trội mà vẫn đảm bảo năng lực tính toán cho các bài toán quy mô lớn.

Để minh họa trực quan các kết quả này, dữ liệu thực nghiệm được trình bày dưới dạng bảng so sánh thời gian thực thi giữa các thuật toán tương ứng với từng quy mô hạt từ 8k đến 2048k. Đồng thời, biểu đồ đường biểu diễn sự suy giảm phi tuyến của thời gian tính toán khi số lượng bộ vi xử lý tăng từ 1 lên 8 nút cho thấy xu hướng tăng tốc tuyến tính rõ rệt, chứng minh tính đúng đắn của giải pháp cân bằng tải.

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

Dựa trên các kết quả đạt được từ luận văn, 4 đề xuất và khuyến nghị chiến lược được đưa ra nhằm hoàn thiện hệ thống tính toán song song:

• Tối ưu hóa thuật toán phân vùng không gian: Áp dụng triệt để đường cong lấp đầy không gian Peano-Hilbert 3 chiều kết hợp kỹ thuật chia đôi đệ quy trực giao thích nghi (ORB) để phân chia dữ liệu hạt. Mục tiêu đặt ra là giảm thêm 25% thời gian truyền thông đồng bộ giữa các nút mạng trong vòng 6 tháng nghiên cứu tiếp theo, do Nhóm nghiên cứu thuật toán song song chủ trì thực hiện.
• Nâng cấp hạ tầng truyền thông phần cứng: Khuyến nghị các đơn vị nghiên cứu chuyển đổi hạ tầng mạng kết nối cụm máy tính từ Fast Ethernet (100 Mbps) sang chuẩn Gigabit Ethernet hoặc mạng chuyên dụng Myrinet/InfiniBand. Giải pháp này nhằm cắt giảm độ trễ truyền thông điệp MPI xuống dưới 5 micro-giây trong vòng 12 tháng, do Bộ phận quản trị hạ tầng tính toán đảm trách.
• Xây dựng mô hình lập trình lai (Hybrid MPI/OpenMP): Phát triển phiên bản kết hợp giữa mô hình đa tiến trình truyền thông điệp MPI giữa các nút và mô hình đa luồng chia sẻ bộ nhớ OpenMP/Pthreads bên trong từng nút đa nhân. Mục tiêu tối ưu 100% công suất của các bộ vi xử lý đa lõi hiện đại trong lộ trình 18 tháng, do Kỹ sư phần mềm hệ thống thực hiện.
• Mở rộng phạm vi ứng dụng sang bài toán tương tác phức hợp: Triển khai tích hợp mô hình cây bát phân song song vào các phần mềm mô phỏng trường phân tử sinh học và tương tác plasma, hướng đến xử lý các hệ thống phức tạp quy mô trên 10.000.000 hạt trong vòng 24 tháng, do Viện nghiên cứu vật lý và hóa học phối hợp triển khai.

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

Tài liệu này mang lại giá trị học thuật và thực tiễn chuyên sâu cho 4 nhóm đối tượng chính:

• Học viên cao học và nghiên cứu sinh ngành Khoa học Máy tính & Hệ thống Thông tin: Tài liệu cung cấp tài liệu tham khảo toàn diện về phương pháp luận thiết kế giải thuật song song, kỹ thuật phân rã dữ liệu, và cách thức lập trình truyền thông điệp MPI trên nền tảng Linux.
• Các nhà nghiên cứu trong lĩnh vực Vật lý Thiên văn và Vật lý Plasma: Luận văn là cơ sở lý thuyết chuẩn xác để ứng dụng giải bài toán tương tác $N$ vật thể, mô phỏng quá trình va chạm thiên hà và chuyển động của hệ hạt tích điện trong môi trường plasma với độ phức tạp tối ưu $O(N)$.
• Kỹ sư phần mềm mô phỏng và Đồ họa Máy tính 3D: Cung cấp giải pháp kỹ thuật cụ thể về cách ánh xạ không gian 3 chiều thành chuỗi bit khóa Morton/Hilbert và bảng băm, hỗ trợ xử lý va chạm và tính toán ánh sáng thực tế cho hàng trăm nghìn nguồn sáng.
• Kiến trúc sư hệ thống và Quản trị viên trung tâm dữ liệu: Tham khảo mô hình xây dựng, cài đặt, cấu hình và đánh giá hiệu năng cụm máy tính PC-Cluster Beowulf mã nguồn mở với chi phí đầu tư thấp nhưng mang lại hiệu năng cao.

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

Tại sao tính toán lực trong bài toán $N$-body lại chiếm tới 90-95% tổng thời gian mô phỏng?

Việc tính lực trực tiếp yêu cầu lặp qua từng cặp hạt trong hệ thống với $N(N-1)/2$ tương tác, dẫn đến độ phức tạp $O(N^2)$. Khi số lượng hạt đạt mức 8.000 phần tử, hệ thống phải thực hiện hơn 31 triệu phép tính phức tạp mỗi bước. Do đó, tính lực luôn là nút thắt cổ chai lớn nhất so với các bước cập nhật vận tốc và vị trí.

Sự khác biệt cốt lõi giữa thuật toán Barnes-Hut và thuật toán FMM là gì?

Thuật toán Barnes-Hut tính tương tác giữa một hạt đơn lẻ với một cụm hạt ở xa thông qua xấp xỉ trọng tâm với độ phức tạp $O(N \log N)$. Trong khi đó, thuật toán FMM nhóm cả hai đầu tương tác thành các cụm và sử dụng khai triển đa cực kết hợp khai triển địa phương, đưa độ phức tạp về mức tuyến tính $O(N)$, tối ưu vượt bậc cho các hệ trên 100.000 hạt.

Vì sao cấu trúc bảng băm lại vượt trội hơn con trỏ truyền thống trong tính toán song song?

Cấu trúc con trỏ truyền thống phân tán địa chỉ bộ nhớ ngẫu nhiên, gây khó khăn lớn khi đồng bộ qua mạng mạng LAN. Ngược lại, cây bát phân dùng bảng băm ánh xạ trực tiếp tọa độ 3 chiều thành khóa số nguyên duy nhất, cho phép truy xuất dữ liệu nút trong thời gian $O(1)$ và dễ dàng đóng gói dữ liệu truyền qua các tiến trình MPI.

Hệ thống PC-Cluster có ưu thế gì so với các bo mạch xử lý chuyên dụng như GRAPE?

Hệ thống phần cứng chuyên dụng như GRAPE có chi phí đắt đỏ (khoảng 10.000 USD mỗi bo mạch vào năm 1999) và khó tùy biến cho các bài toán khác. Hệ thống PC-Cluster Beowulf tận dụng các máy tính cá nhân phổ thông chạy Linux, chi phí thấp, dễ dàng bảo trì, nâng cấp linh hoạt từ 2 lên hàng chục nút mà vẫn đảm bảo hiệu năng tính toán cao.

Đường cong lấp đầy không gian Peano-Hilbert giải quyết bài toán cân bằng tải như thế nào?

Đường cong Peano-Hilbert ánh xạ không gian đa chiều về một chiều mà vẫn bảo toàn tối đa tính lân cận hình học của các hạt. Khi chia danh sách khóa 1 chiều thành các đoạn bằng nhau cho 8 bộ vi xử lý, khối lượng công việc tính toán được phân bố đồng đều, triệt tiêu thời gian nhàn rỗi và hạn chế truyền thông chéo giữa các nút.

Kết luận

• Đã phân tích toàn diện cơ sở toán học của bài toán $N$-body và chứng minh tính cấp thiết của việc kết hợp thuật toán FMM với kiến trúc tính toán song song.
• Thiết kế thành công cấu trúc cây bát phân không gian 3 chiều sử dụng khóa nhị phân và bảng băm, đạt tốc độ truy xuất nút tức thời với độ phức tạp $O(1)$.
• Cài đặt và thực nghiệm thành công mô hình song song SPMD trên cụm 8 máy tính PC-Cluster chạy Linux và MPI, rút ngắn thời gian tính toán từ 19,63 giây xuống 3,46 giây trên mẫu 8.000 hạt.
• Ứng dụng thành công vào case study mô phỏng va chạm 2 thiên hà với 2.048 thiên thể qua 180 bước thời gian, đảm bảo độ chính xác vật lý và độ ổn định cao.
• Xác lập giải pháp công nghệ hiệu năng cao, chi phí thấp, mở ra hướng ứng dụng rộng rãi cho các bài toán mô phỏng vật lý và tính toán khoa học phức tạp.

Đóng góp lớn nhất của luận văn là đã giải quyết trọn vẹn bài toán biểu diễn và duyệt cây bát phân song song trên hệ phân tán, loại bỏ hoàn toàn các rào cản về bộ nhớ con trỏ. Các bước phát triển tiếp theo trong vòng 12 đến 24 tháng tới cần tập trung vào việc mở rộng mô hình tính toán lai trên mạng truyền thông băng thông rộng và tích hợp thuật toán vào các bài toán động lực học phân tử thực tế. Các nhà nghiên cứu và kỹ sư quan tâm có thể khai thác trực tiếp mô hình thuật toán và kiến trúc triển khai này để tối ưu hóa các hệ thống tính toán khoa học chuyên sâu.

Trích đoạn nội dung tài liệu

CHƯƠNG 1. BÀI TOÁN MÔ PHỎNG N-BODY VÀ MÔ HÌNH SONG SONG 1. Bài toán mô phỏng N-body 1. Giới thiệu Đoán trước được những diễn biến có thể xảy ra trong tự nhiên (như dự đoán về sự va chạm của các thiên hà, sự phát triển của các cơn bão…) để kịp có biện pháp phòng ngừa thiên tai hay biểu diễn những chuyển động của các phần tử trong một hệ (như các nguyên tử trong một phân tử,…) để phục vụ cho các nghiên cứu cụ thể trong Hóa học, Vật lý là nhu cầu cần thiết trong cuộc sống hàng ngày cũng như trong nghiên cứu khoa học.

Một cách trực quan, người ta thực hiện tạo ra các hệ như vậy bằng những công cụ thí nghiệm và gọi công việc đó là mô phỏng. Do thời gian ước lượng các thuộc tính của các hệ thống vật lý là khó dự đoán bằng việc phân tích bởi sự phức tạp của hệ thống hoặc đơn giản chỉ bởi số lượng các body đang phân tích. Một trong các phương pháp mô phỏng đó là hệ vật lý được mô hình hóa như một tập các body tương tác với các body khác, và có thể tác động trở lại bên ngoài. Bài toán mô phỏng N-body là bài toán cho việc mô phỏng sự chuyển động của một tập các body (các hạt - particles) dưới tác động của lực hấp dẫn hoặc các lực khác.

Từ một trạng thái ban đầu cho trước, dưới tác động của lực tương tác, trạng thái của các body trong hệ được cập nhật liên tục theo thời gian. Chẳng hạn trong bài toán mô phỏng sự chuyển động của các phân tử trong một hệ vật chất nào đó: từ một vị trí ban đầu, các phân tử tương tác với nhau do đó vận tốc và gia tốc thay đổi nên chúng sẽ chuyển đến các vị trí khác. Cứ như vậy, vị trí của các phân tử trong hệ liên tục thay đổi. Để thực hiện việc mô phỏng sự chuyển động của các phân tử này, ta phải xác định và cập nhật liên tục vị trí của chúng trong suốt thời gian mô phỏng.

Bài toán được mô tả như sau: (1) Cho trạng thái của hệ thống gồm N body tại thời điểm ban đầu T0 : n1(x1, T0), n2(x2, T0), …, nN(xN, T0) 6 LUAN VAN CHAT LUONG download : add [e-mail] Trong đó ni (i=1,.,N) là các body; xi là các thông tin trạng thái của ni tương ứng tại thời điểm T0. Các thông tin trạng thái quan trọng nhất là: vị trí, vận tốc, khối lượng (dùng để tính lực hấp dẫn); điện tích (dùng để tính lực Coulomb) (2) Hãy xác định trạng thái của hệ thống tại thời điểm Tj: n1(x1, Tj), n2(x2, Tj), …, nN(xN, Tj) Thông thường, nếu không cần chỉ rõ thời điểm, người ta sử dụng cách biểu diễn n1(x1), n2(x2), …, nN(xN) để trình bày trạng thái của hệ thống. Các bước trong quy trình giải bài toán mô phỏng N-body Với bài toán được mô tả như ở trên, đã có nhiều phương pháp được đưa ra nhằm xác định các thông tin trạng thái của các body trong hệ tại một thời điểm bất kỳ. Tuy vậy, các bước trong quá trình mô phỏng hệ N-body đều có các điểm chung như sau: 1.

Biểu diễn hệ thống 2. Tính toán năng lượng và lực tương tác giữa các body trong hệ 3. Tính và cập nhật trạng thái (vị trí, vận tốc) của các body trong hệ. Quá trình được tiếp lục lặp đi lặp lại từ bước thứ hai.

Các phương pháp đưa ra hầu hết đều nhằm giảm thời gian tính lực bởi trong cả quá trình mô phỏng thì giai đoạn này chiếm thời gian là chủ yếu (xấp xỉ 90-95%). Luận văn tập trung vào giai đoạn tính lực cho bài toán mô phỏng N-body bất kỳ. Để hình dung bài toán mô phỏng một cách trực quan, chúng ta sẽ xem xét ví dụ về mô phỏng sự va chạm của hai thiên hà (galaxy) để tạo ra một thiên hà mới sau đây (tổng số thiên thể là 2048). 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.1 - Thời điểm bắt đầu mô phỏng (t = 0, 0 bước mô phỏng) Từ hai thiên hà ban đầu (hình 1.1), chúng tiến lại gần nhau và va chạm do tác động của lực hấp dẫn.2 - Thời điểm ngay trước khi va chạm (t = 3.937253, số bước mô phỏng bằng 100) 8 LUAN VAN CHAT LUONG download : add [e-mail] Tại thời điểm bắt đầu va chạm, hai thiên hà đẩy nhau (hình 1.2) nhưng sau một thời gian ngắn, do lực hấp dẫn nên chúng tiến lại gần nhau và tạo thành một thiên hà mới (hình 1.3 - Thời điểm sau khi va chạm (t = 7.087056, số bước mô phỏng là 180) Để mô phỏng các hệ lớn thông thường cần thực hiện rất nhiều bước lặp.

Chẳng hạn như thực hiện mô phỏng hệ thiên hà trong ví dụ, số bước lặp khoảng 10000 bước nên tốn rất nhiều thời gian. Do đó, việc tăng tốc độ tính lực cho bài toán mô phỏng N-body là một nhu cầu tất yếu. Các giải pháp tăng tốc độ tính lực cho bài toán mô phỏng N-body Với tốc độ phát triển công nghệ nhanh chóng hiện nay, các thông tin và kết quả tính toán đưa ra càng nhanh càng tốt và tất nhiên là phải chính xác. Để mô phỏng nhanh hơn và chính xác hơn, một số phương thức để giải quyết vấn đề này đã được đưa ra: phần cứng đặc biệt, thuật toán nhanh, tính toán song song.

Phần cứng đặc biệt Sử dụng phần cứng đặc biệt xuất phát từ ý tưởng chế tạo các thiết bị chuyên dụng giải quyết hiệu quả lớp bài toán riêng nào đó. Hiện nay đã có máy tính đặc biệt như GRAPE - GRAvity PipE, GRAPE-4,… là một phần cứng đặc biệt 9 LUAN VAN CHAT LUONG download : add [e-mail] [9][10][13][14][20] dùng cho việc tính toán. Một số tác giả đã sử dụng phần cứng này để tính lực giữa các hạt điện tích. Phần cứng này có khả năng tăng tốc độ tính toán lực nhanh hơn 100-1000 lần so với máy tính bình thường.

Một hệ thống GRAPE gồm một máy tính bình thường (máy chủ) và một bo mạch GRAPE kết nối theo giao diện truyền thông. Máy chủ gửi dữ liệu đến GRAPE, sau đó GRAPE tính toán và trả lại kết quả cho máy chủ (Hình 1. Gửi dữ liệu Máy chủ GRAPE Trả lại kết quả Hình 1.4 - Hệ thống GRAPE Chi phí về giá thành cho hệ thống này rất đắt (1 board GRAPE giá khoảng 10000USD (1999)) và vì vậy chưa thật sự phổ biến ở Việt Nam. Hiện nay Viện Khoa học Kỹ thuật Hạt nhân đã có MDGRAPE-2.

Chúng tôi đang xem xét khả năng triển khai các hệ thống GRAPE mô phỏng N-body trong một số dự án liên kết (Viện Vật lý, Khoa Hóa-ĐHKHTN,…). Thuật toán nhanh Trước đây việc tính lực giữa một tập N body có thể được thực hiện bằng việc tính trực tiếp lực tương tác F(xi,xj) (i,j = 1,2,…,N ; N là số body) giữa từng cặp body trong hệ. Hệ được biểu diễn bằng một mảng với mỗi phần tử mảng chứa thông tin của một body. Độ phức tạp thời gian tính toán của phương pháp này là O(N2).

Đối với những hệ số lượng body rất lớn (cỡ vài chục triệu) thì phương pháp này không tốt bởi kết quả tính toán quá chậm do đó một số thuật toán hiệu quả hơn đã được đề xuất với các giải pháp biểu diễn hệ để có thể xấp xỉ các lực giữa các body gần tới mức tuyến tính về thời gian. Những thuật toán như vậy là các phương pháp biểu diễn hệ dựa trên cây, dùng một cấu trúc dữ liệu dạng cây để nhóm các body thành các cụm (cluster). Các phương pháp này có thể tính lực giữa N body trong thời gian tỷ lệ với O(NlogN) thậm chí O(N). 10 LUAN VAN CHAT LUONG download : add [e-mail] Thuật toán Barnes-Hut (BH) sử dụng các khái niệm hạng đơn (single-term), trọng tâm (center-of-mass), xấp xỉ (approximation) [8].

Thuật toán Barnes-Hut tổ chức tập các body thành dạng cây các cụm. Để giảm thiểu các thao tác, mỗi body tính lực tương tác với các cụm lớn nhất có thể xấp xỉ được. Độ chính xác xấp xỉ trọng tâm phụ thuộc vào tỷ lệ giữa bán kính của cụm và khoảng cách từ cụm tới thế năng được ước lượng. Kết quả sẽ tốt hiệu quả nếu một cụm chỉ có thể được thích hợp với trọng tâm của nó tới cụm là lớn hơn r/θ trong đó r là bán kính của cụm.

Tham số θ xác định sai số xấp xỉ. cụm trọng tâm body D r Hình 1.5 - Trọng tâm xấp xỉ Để xây dựng cây, người ta coi hệ N-body được bao quanh bởi một hình vuông (trong không gian 2 chiều, là hình hộp nếu trong không gian 3 chiều). Việc phân chia được tính toán đệ quy bằng cách chia ô (khối) ban đầu thành 4 phần (8 phần) và mỗi phần con đó lại tiếp tục được chia ra cho đến khi không chia được nữa thì dừng. Mỗi lần chia các ô (khối) ra như vậy, ta thực hiện xây dựng cây tương ứng bằng việc chèn thêm các node (tương ứng với mỗi ô con được chia) vào trong cây.

Các ô cuối cùng thu được chính là lá của cây cần xây dựng. Mỗi node trong cây BH biểu diễn một cụm. Thuật toán BH được tóm tắt như sau: 1. Xây dựng cây BH (như vừa giới thiệu ở trên).

Tính trọng tâm (duyệt cây từ dưới lên). Với mỗi body, bắt đầu duyệt từ mức sâu nhất của cây tính và cập nhật gia tốc của body. Cập nhật vận tốc và vị trí của mỗi body. 11 LUAN VAN CHAT LUONG download : add [e-mail] Để tăng tốc độ tính toán, thuật toán khai triển đa cực nhanh FMM [11] đã được đề xuất với độ phức tạp tính toán chỉ còn O(N).

Chiến lược của thuật toán này là nhóm các hạt (body) thành các cụm và tính tương tác với những các cụm khác đủ xa bởi trung tình các khai triển đa cực. Tương tác giữa các hạt gần nhau (trong cùng một cụm) thì tính trực tiếp. Thuật toán FMM sẽ được giới thiệu chi tiết hơn trong chương 2. Thuật toán song song Việc áp dụng thuật toán nhanh như giới thiệu ở trên đã góp phần tăng tốc độ tính lực khá nhiều.

Tuy nhiên, với những hệ lớn thì công việc tính lực càng đòi hỏi nhiều thời gian do đó việc song song hóa các thuật toán tuần tự tỏ ra rất hiệu quả trong việc tăng tốc độ tính lực. Đây là nội dung sẽ được luận văn áp dụng và thảo luận trong không gian 3 chiều và sẽ được giới thiệu chi tiết ở chương 3. Xuất phát từ tư tưởng song song thuật toán tính lực trực tiếp, chúng tôi cũng đã cài đặt thử nghiệm thuật toán và song song hóa thuật toán này để thấy rõ hơn tính ưu việt của việc song song.