Luận văn thạc sĩ về tối ưu hóa thuật toán n-body sử dụng cây bát phân trên PC Cluster

Luận văn thạc sĩ toán học phân tích 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, đánh giá thực trạng, chỉ ra hạn chế, đề

• 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ệ
• Đề tài: Tối ưu hóa thuật toán n-body với cây bát phân 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ề thuật toán n body

Bài toán mô phỏng N-body là một trong những thách thức lớn trong lĩnh vực tính toán khoa học. Thuật toán n-body được sử dụng để mô phỏng sự tương tác giữa nhiều hạt trong không gian, thường gặp trong vật lý thiên văn và động lực học. Độ phức tạp tính toán của bài toán này là O(N²), trong đó N là số lượng hạt. Điều này dẫn đến việc cần thiết phải tối ưu hóa thuật toán để giảm thời gian tính toán. Các phương pháp như cây bát phân và thuật toán nhanh đã được phát triển để cải thiện hiệu suất tính toán. Việc áp dụng các phương pháp này không chỉ giúp giảm thời gian tính toán mà còn mở rộng khả năng mô phỏng các hệ thống lớn hơn.

1.1. Các bước trong quy trình giải bài toán mô phỏng N body

Quy trình giải bài toán mô phỏng N-body bao gồm ba bước chính: biểu diễn hệ thống, tính toán năng lượng và lực tương tác giữa các hạt, và cập nhật trạng thái của các hạt. Việc tính toán 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 đó, việc tối ưu hóa thuật toán tính lực là rất quan trọng. Các phương pháp như thuật toán Barnes-Hut và thuật toán khai triển đa cực nhanh (FMM) đã được đề xuất để giảm độ phức tạp tính toán từ O(N²) xuống O(N log N) hoặc O(N).

II. Tối ưu hóa thuật toán n body với cây bát phân

Tối ưu hóa thuật toán n-body thông qua việc sử dụng cây bát phân là một trong những phương pháp hiệu quả nhất. Cây bát phân cho phép nhóm các hạt thành các cụm, từ đó giảm số lượng phép tính cần thiết để xác định lực tương tác. Việc xây dựng cây bát phân được thực hiện theo cách chia nhỏ không gian thành các ô nhỏ hơn, giúp dễ dàng quản lý và tính toán. Hiệu suất tính toán được cải thiện đáng kể khi áp dụng phương pháp này, đặc biệt là trong các hệ thống lớn với hàng triệu hạt. Kết quả thử nghiệm cho thấy thời gian tính toán giảm rõ rệt khi sử dụng cây bát phân so với phương pháp tính lực trực tiếp.

2.1. Phân chia dữ liệu và xây dựng cây bát phân

Phân chia dữ liệu là bước quan trọng trong quá trình tối ưu hóa thuật toán. Dữ liệu về các hạt được chia đều cho các bộ xử lý trong hệ thống PC Cluster. Mỗi bộ xử lý sẽ tính toán lực tương tác giữa các hạt mà nó quản lý. Việc xây dựng cây bát phân diễn ra song song, giúp tăng tốc độ tính toán. Các giải pháp phân chia dữ liệu như ORB và SFC được áp dụng để tối ưu hóa quá trình này. Kết quả cho thấy việc sử dụng cây bát phân không chỉ giúp giảm thời gian tính toán mà còn cải thiện độ chính xác của mô phỏng.

III. Kết quả và đánh giá

Kết quả thử nghiệm cho thấy việc áp dụng thuật toán song song và cây bát phân trong mô phỏng N-body mang lại hiệu quả rõ rệt. Thời gian tính toán giảm đáng kể khi so sánh giữa chương trình tuần tự và chương trình song song. Việc sử dụng hệ thống phân tán như PC Cluster cho phép xử lý đồng thời nhiều tác vụ, từ đó nâng cao hiệu suất tính toán. Đánh giá tổng thể cho thấy rằng việc tối ưu hóa thuật toán không chỉ giúp tiết kiệm thời gian mà còn mở rộng khả năng mô phỏng các hệ thống phức tạp hơn trong tương lai.

3.1. So sánh hiệu suất giữa các phương pháp

So sánh giữa các phương pháp tính toán cho thấy rằng thuật toán n-body sử dụng cây bát phân và song song hóa mang lại hiệu suất tốt nhất. Thời gian tính toán giảm từ hàng giờ xuống chỉ còn vài phút khi áp dụng các phương pháp tối ưu hóa. Điều này chứng tỏ rằng việc áp dụng công nghệ mới và cải tiến thuật toán là cần thiết để đáp ứng nhu cầu ngày càng cao trong nghiên cứu và ứng dụng thực tiễn.

Nội dung chính

## Tổng quan nghiên cứu

Bài toán mô phỏng N-body là một trong những thách thức lớn trong lĩnh vực tính toán khoa học, đặc biệt trong các ngành vật lý thiên văn, hóa học, và vật lý plasma. Với số lượng các hạt (body) trong hệ có thể lên đến hàng triệu, việc tính toán lực tương tác giữa các hạt chiếm đến khoảng 90-95% tổng thời gian tính toán, với độ phức tạp O(N²). Ví dụ điển hình là mô phỏng va chạm giữa hai thiên hà với tổng số thiên thể lên đến 2048, yêu cầu thực hiện khoảng 10.000 bước lặp để thu được kết quả chính xác. Mục tiêu nghiên cứu của luận văn là phát triển và 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, nhằm giảm đáng kể thời gian tính toán trên hệ thống PC-Cluster sử dụng giao diện truyền thông điệp MPI. Phạm vi nghiên cứu tập trung vào không gian ba chiều, áp dụng thuật toán khai triển đa cực nhanh (FMM) và các phương pháp phân chia dữ liệu hiệu quả như ORB và SFC. Ý nghĩa của nghiên cứu được thể hiện qua việc tăng tốc độ tính lực, giảm thời gian mô phỏng, từ đó mở rộng khả năng ứng dụng trong các mô hình vật lý phức tạp và các hệ thống lớn.

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

### Khung lý thuyết áp dụng

- **Thuật toán khai triển đa cực nhanh (FMM)**: Giảm độ phức tạp tính toán từ O(N²) xuống O(N) bằng cách nhóm các hạt thành các cụm và sử dụng khai triển đa cực để tính lực tương tác giữa các cụm.
- **Cây bát phân (Oct-tree)**: Cấu trúc dữ liệu dạng cây phân chia không gian ba chiều thành các ô con, giúp tổ chức và truy xuất dữ liệu hiệu quả.
- **Phương pháp phân chia dữ liệu song song (ORB, SFC)**: Giúp cân bằng tải giữa các bộ xử lý bằng cách phân chia dữ liệu theo các đường cong phủ không gian như Morton hoặc Peano-Hilbert.
- **Mô hình lập trình song song SPMD với MPI**: Cho phép thực hiện các tiến trình song song trên hệ thống PC-Cluster, tối ưu hóa truyền thông và đồng bộ hóa giữa các node.

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

Luận văn sử dụng dữ liệu mô phỏng N-body với số lượng body từ 8.000 đến 2.048.000, thực hiện trên hệ thống Linux PC-Cluster gồm 8 máy tính. Phương pháp phân tích bao gồm:

- Xây dựng cây bát phân tuần tự và song song dựa trên khóa Morton và bảng băm để biểu diễn cấu trúc cây.
- Phân chia dữ liệu cho các bộ xử lý theo phương pháp Space-Filling Curve (SFC) nhằm cân bằng tải.
- Cài đặt và thử nghiệm thuật toán FMM song song sử dụng thư viện MPI để truyền thông điệp giữa các node.
- Đánh giá hiệu năng qua các chỉ số thời gian tính lực trực tiếp và thời gian tạo cây bát phân, so sánh giữa chương trình tuần tự và song song.
- Timeline nghiên cứu kéo dài trong khoảng thời gian thực hiện luận văn, với các giai đoạn thiết kế, cài đặt, thử nghiệm và đánh giá.

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

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

- **Tăng tốc độ tính lực**: Thuật toán song song giảm thời gian tính lực trực tiếp từ 19,63 giây xuống còn 3,38 giây với 8.000 body trên hệ thống 8 máy, tương đương giảm khoảng 82,8%.
- **Thời gian tạo cây bát phân**: Với 8.000 body, thời gian tạo cây tuần tự là khoảng 0,62 giây, tăng lên theo cấp số nhân khi số lượng body tăng, cho thấy nhu cầu song song hóa để giảm thời gian xử lý.
- **Hiệu quả phân chia dữ liệu**: Phương pháp phân chia theo đường cong phủ Peano-Hilbert cho kết quả cân bằng tải tốt hơn so với khóa Morton, giảm thiểu sự gián đoạn trong việc tính toán lực giữa các ô gần nhau.
- **Khả năng mở rộng**: Thuật toán song song hóa cây bát phân và tính lực trên PC-Cluster cho thấy khả năng mở rộng tốt khi tăng số lượng node, giảm đáng kể thời gian tính toán so với phương pháp tuần tự.

### Thảo luận kết quả

Nguyên nhân chính của sự cải thiện hiệu năng là do việc phân chia dữ liệu hợp lý và sử dụng cấu trúc cây bát phân biểu diễn hệ thống giúp giảm độ phức tạp truy xuất dữ liệu xuống O(1) cho mỗi node. So với các nghiên cứu trước đây chỉ tập trung vào thuật toán tuần tự hoặc phần cứng đặc biệt, việc áp dụng song song hóa trên hệ thống PC-Cluster với MPI mang lại giải pháp chi phí thấp và linh hoạt hơn. Dữ liệu có thể được trình bày qua biểu đồ so sánh thời gian tính lực trực tiếp giữa chương trình tuần tự và song song, cũng như biểu đồ thời gian tạo cây bát phân theo số lượng body, minh họa rõ ràng hiệu quả của phương pháp. Kết quả này có ý nghĩa quan trọng trong việc ứng dụng mô phỏng N-body cho các hệ lớn trong vật lý thiên văn và hóa học, giúp rút ngắn thời gian tính toán và nâng cao độ chính xác mô phỏng.

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

- **Triển khai rộng rãi hệ thống PC-Cluster**: Khuyến nghị các viện nghiên cứu và trường đại học đầu tư xây dựng hệ thống PC-Cluster để tận dụng khả năng tính toán song song, nâng cao hiệu quả mô phỏng N-body.
- **Áp dụng phương pháp phân chia dữ liệu Peano-Hilbert**: Động viên sử dụng phương pháp này để cân bằng tải tốt hơn, giảm thiểu thời gian chờ đợi giữa các bộ xử lý, đặc biệt trong các hệ lớn.
- **Phát triển phần mềm song song hóa thuật toán FMM**: Khuyến khích phát triển và tối ưu hóa phần mềm sử dụng MPI, hỗ trợ đa nền tảng và đa ngôn ngữ lập trình, nhằm tăng tính linh hoạt và khả năng mở rộng.
- **Tích hợp phần cứng chuyên dụng khi cần thiết**: Đề xuất kết hợp phần cứng tính toán nhanh như GRAPE trong các dự án lớn để tăng tốc độ tính toán lực, đặc biệt trong các mô phỏng yêu cầu độ chính xác cao.
- **Đào tạo và nâng cao năng lực lập trình song song**: Tổ chức các khóa đào tạo về lập trình song song và sử dụng MPI cho các nhà nghiên cứu và sinh viên nhằm nâng cao năng lực phát triển các giải pháp tính toán hiệu quả.

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

- **Nhà nghiên cứu và giảng viên ngành khoa học máy tính và công nghệ thông tin**: Học hỏi phương pháp song song hóa thuật toán và ứng dụng trong mô phỏng khoa học.
- **Chuyên gia vật lý thiên văn và hóa học tính toán**: Áp dụng các giải pháp mô phỏng N-body hiệu quả cho nghiên cứu thiên văn và hóa học phân tử.
- **Kỹ sư phát triển phần mềm tính toán hiệu năng cao (HPC)**: Tham khảo kỹ thuật xây dựng cây bát phân song song và tối ưu hóa truyền thông MPI.
- **Sinh viên cao học và nghiên cứu sinh**: Nắm bắt kiến thức về thuật toán FMM, cấu trúc dữ liệu cây bát phân, và kỹ thuật lập trình song song để phục vụ nghiên cứu và luận văn.

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

1. **Thuật toán FMM là gì và tại sao nó quan trọng?**  
   Thuật toán FMM là phương pháp khai triển đa cực nhanh giúp giảm độ phức tạp tính toán lực từ O(N²) xuống O(N), rất quan trọng trong mô phỏng các hệ N-body lớn để tiết kiệm thời gian và tài nguyên tính toán.

2. **Tại sao cần song song hóa thuật toán mô phỏng N-body?**  
   Vì số lượng body rất lớn và thời gian tính lực chiếm phần lớn tổng thời gian, song song hóa giúp phân chia công việc cho nhiều bộ xử lý, giảm thời gian thực thi đáng kể.

3. **Phương pháp phân chia dữ liệu nào hiệu quả nhất?**  
   Phương pháp phân chia theo đường cong phủ Peano-Hilbert được đánh giá cao hơn khóa Morton vì nó giữ được tính liên tục không gian, giúp cân bằng tải và giảm chi phí truyền thông.

4. **Hệ thống PC-Cluster có ưu điểm gì so với phần cứng chuyên dụng?**  
   PC-Cluster có chi phí thấp, dễ mở rộng và linh hoạt trong sử dụng, trong khi phần cứng chuyên dụng như GRAPE có chi phí cao và ít phổ biến.

5. **MPI hỗ trợ gì trong việc lập trình song song?**  
   MPI cung cấp chuẩn giao tiếp truyền thông điệp hiệu quả, hỗ trợ đa nền tảng và đa ngôn ngữ, giúp đồng bộ và truyền dữ liệu giữa các tiến trình trong hệ thống song song.

## Kết luận

- Thuật toán khai triển đa cực nhanh (FMM) kết hợp với cây bát phân giúp giảm đáng kể độ phức tạp tính toán trong mô phỏng N-body.  
- Song song hóa bước biểu diễn cây bát phân trên hệ thống PC-Cluster sử dụng MPI đã chứng minh hiệu quả vượt trội, giảm thời gian tính lực đến hơn 80%.  
- Phương pháp phân chia dữ liệu theo đường cong phủ Peano-Hilbert giúp cân bằng tải và tối ưu hóa hiệu năng tính toán.  
- Nghiên cứu mở ra hướng phát triển các giải pháp mô phỏng khoa học hiệu quả, phù hợp với các hệ thống tính toán hiện đại.  
- Đề xuất tiếp tục phát triển phần mềm và hạ tầng tính toán song song, đồng thời đào tạo nguồn nhân lực để ứng dụng rộng rãi trong nghiên cứu và công nghiệp.

Khuyến khích các tổ chức nghiên cứu triển khai thử nghiệm trên quy mô lớn hơn, đồng thời phát triển các công cụ hỗ trợ lập trình song song để nâng cao hiệu quả mô phỏng N-body.

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

Chương 1 giới thiệu bài toán mô phỏng N-body, các khó khăn gặp phải và cách khắc phục các khó khăn này. Một số mô hình song song áp dụng cho tính toán song song cũng được trình bày. Luận văn cũng giới thiệu một số vấn đề cơ bản nhất về mô hình MPI trên Linux PC Cluster được dùng để cài đặt thử nghiệm thuật toán trong luận văn. Chương 2 trình bày thuật toán FMM cơ sở cho thuật toán chính trong luận văn, phương pháp biểu diễn cây bát phân, giới thiệu chương trình cài đặt cây bát phân tuần tự.

Một số nhận xét, đánh giá bước đầu được trình bày nhằm chỉ ra tính ưu việt khi thực hiện song song hóa cây bát phân. Chương 3 trình bày thực hiện song song hóa cây bát phân. Các giải pháp phân chia dữ liệu, tạo và duyệt cây bát phân đã được phân tích. Luận văn cũng giới thiệu những nội dung cơ bản liên quan đến việc cài đặt chương trình thử nghiệm song song hóa thuật toán.

Một số nhận xét, đánh giá bước đầu dựa trên các kết quả thử nghiệm đã được đưa ra. 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 z 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).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 z 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 z [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 z 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 z Để 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.