Gravitational N Body Simulation

18Sep08

n body simulation visualization

n body simulation visualization

Tugas berikutnya dari mata kuliah sistem berkinerja tinggi adalah tentang data partitioning dan divide and conquer. Dari tiga studi kasus yang ada di Bab 4 Buku Parallel Programmingnya Barry Wilkinson, saya kebagian tugas mengimplementasi kasus N Body Simulation.

Deskripsi dari persoalan ini adalah jika diberikan sejumlah n astronomical body (posisi, dan massa) maka ditanyakan posisi berikutnya setelah selang waktu t berikutnya dengan asumsi tiap objek akan terpengaruh oleh gaya gravitasi objek-objek lainnya sesuai dengan hukum gravitasi newton.

Berhubung ngerjainnya pun baru beberapa jam sebelumnya di kampus, yang baru terimplementasi baru versi algoritma sekuensial antar-partikel dan antarmuka untuk visualisasinya. Kompleksitas algoritma sekuensial antar partikel adalah O(N2). Algoritma ini dapat diparalelkan dengan sudut pandang partisi data dengan catatan seluruh objek dihitung posisi barunya setelah dt satuan waktu tetapi belum mengubah posisi objek tersebut. Dengan demikian perhitungan gaya yang berlaku pada setiap objek dapat diparalelisasikan dalam proses/thread tersendiri.

Adapun variasi dari algoritma antar objek sebagai partikel ini (particle-to-particle) adalah dengan melakukan partisi dan agregasi terhadap objek. partisi yang dilakukan dengan menggunakan struktur data spasial (octtree atau k-d tree, bounding volume hierarchies, dll) dengan catatan setiap node dalam hierarki tersebut merepresentasikan satu objek semu sebagai rata-rata terhadap objek-objek yang di cakup dalam node objek semu tersebut. Sebagai contoh untuk algoritma Barnes-hut yang menggunakan octtree sebagai partisi data kompleksitas yang didapat dalam menghitung resultan gaya untuk setiap objek adalah O(N log N) (tentu dengan overhead komputasi pembuatan octtree dalam setiap tahapannya).

berikut ini potongan kode utama (yang diparalelkan):

/*
 * calculate total force working on body_idx
 */
void calculate_force(int body_idx)
{
	int i;
	svec3f dpos;
	float r2, r, tmpf;
	
	bodies[body_idx].f = vec3(0.0f, 0.0f, 0.0f);
	for (i=0; i<NBODY; ++i)
		if (i!=body_idx){
			//dpos = vec3sub(bodies[i].pos, bodies[body_idx].pos);
			dpos = vec3sub(bodies[body_idx].pos, bodies[i].pos);
			r2 = vec3dot(dpos, dpos);//r^2
			r = sqrt(r2);//distance
			tmpf = (G * bodies[i].mass * bodies[body_idx].mass) / (r2 * r);
			bodies[body_idx].f = vec3add(bodies[body_idx].f, vec3(dpos.x * tmpf, dpos.y * tmpf, dpos.z * tmpf));
		}
}

/*
 * update the simulation
 */
void do_sim()
{
	int b;
	float cur_time = gettime();
	float dt = (cur_time-last_time) * 2;
	delta_time += (cur_time-last_time);
	
	#pragma omp parallel
	{
		#pragma omp for
		for (b=0; b<NBODY; ++b){
			calculate_force(b);
			
			bodies[b].acc = vec3scale(bodies[b].f, 1.0f / bodies[b].mass);
			bodies[b].vel = vec3add(bodies[b].vel, vec3scale(bodies[b].acc, dt));
			newpos[b] = vec3add(bodies[b].pos, vec3scale(bodies[b].vel, dt));
			
		}
		#pragma omp barrier
		for (b=0; b<NBODY; ++b) bodies[b].pos = newpos[b];
	}
	
	if(delta_time > 0.05){
		render_scene();
		delta_time = 0.0f;
	}
	last_time = cur_time;
}

kode ditulis dalam bahasa C dengan library tambahan OpenGL, GLU, dan GLUT dan dikompilasi menggunakan GCC 4.2 dengan ekstensi untuk OpenMP. Masih perlu diperbaiki (belum implementasi divide and conquer) dan octtree. kode sementara dapat diunduh di sini (seperti biasa, rename odt jadi zip).

About these ads


One Response to “Gravitational N Body Simulation”

  1. waduh, nggak ngerti deh……sok ajah……dilanjut, saya do’akan biar jadi orang sukses di dunia ini….., Amin….. :)


Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Logout / Ubah )

Twitter picture

You are commenting using your Twitter account. Logout / Ubah )

Facebook photo

You are commenting using your Facebook account. Logout / Ubah )

Google+ photo

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s


Ikuti

Get every new post delivered to your Inbox.

Bergabunglah dengan 2.078 pengikut lainnya.

%d bloggers like this: