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 luanvanchat@agmail.com 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 luanvanchat@agmail.com 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 luanvanchat@agmail.com [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 luanvanchat@agmail.com 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 luanvanchat@agmail.com Để 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.