Changes between Version 13 and Version 14 of UGT2008
- Timestamp:
- Feb 12, 2012 2:53:35 PM (12 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
UGT2008
v13 v14 4 4 == Speedup of the Tree-Method Solution to the N-body Problem == 5 5 The purpose of the computer simulations is to reproduce natural phenomena and analyze it, and it is to make simulations useful for the real world. If the simulations is considerably slow, it will not be used. In a natural phenomenon, in particular, this research optimize the three dimensional N-body problem. We perform speedup (optimization) with Graphics Processing Unit (GPU) and tree method algorithm that reduce calculation time of the forces to O(NlogN) from O(N^2^). In recent years, the performance of GPU improves greatly and shows performance (FLOPS) that is higher than the CPU. Therefore, this research uses the GPU for speedup. We compared execution time of CPU and GPU in the N-body problem with tree method, and we try to speedup of this solution. As a result, the execution time of GPU became about 20 times faster than CPU in the number of particles 32000. 6 7 file:///home/committee/aac/Thesis2008/s1130100 6 8 7 9 [[Image(SM_fig1.jpg)]] … … 12 14 These days, the Monte Carlo Method is noticed in the field of the programs of board games. In this thesis, the method adopted by Japanese chess. Moreover, the program which I made is parallelized on Playstation 3 (PS3). As the number of trial increases, I tried to improve the program. It is important for the evaluated functions to distinguish the situations of the board. My program is used three functions properly. the parallelization was successful. However, the program did not become strong as the number of processor increases. In the program of board games, the parallelization was not effective without a appropriate way to select the next move. 13 15 16 file:///home/committee/aac/Thesis2008/s1130154 17 14 18 [[Image(TH_fig1.png)]] 15 19 [[Image(TH_fig2.png)]] … … 19 23 The gravitational N-body problem is a problem concerning the planet movement, when interacting between the fixed star and planet by universal gravitation such as the solar system. However, solving the gravitational N-body problem with a CPU takes a lot of time. In this paper, I show how to speed-up solving the gravitational N-body problem by using GPU, which is high performance graphic processing unit. In addition, to achieve higher performance, I optimized my program on GPU by loop unrolling. As a result, the peak performance to solve 100000-body problem was about 500 GFLOPS in my optimized program on GPU. 20 24 25 file:///home/committee/aac/Thesis2008/s1130195 26 21 27 [[Image(FK_fig2.png)]] 22 28 … … 24 30 == Shogi System using the Monte Carlo Method on the Multi-core CPU == 25 31 The Monte Carlo Method for table games becoming increasingly popular. We use the Monte Carlo Method for Shogi. The Monte Carlo Method needs a lot of computational complexity. However, each Monte Carlo tree search for Shogi is independence and implemented easily for parallel processing. Then, our Shogi system is implemented on the Multi-core CPU. As a result, the number of playout lenearly-increase when the number of thread increase. And the number of winning percentage increases slightly when the number of playout increases. 32 33 file:///home/committee/aac/Thesis2008/s1130197 26 34 27 35 [[Image(HJ_fig1.png)]] … … 32 40 The particle simulation is to compute various movements of the particle virtually in the program. However, because it takes time to calculate when number of particles increases, it is not possible to simulate it in real time with only CPU. Then, I attempts to speed-up the particle simulations by using Graphics Processing Unit(GPU) whose arithmetic capacity is higher than that of CPU. As a result, it is possible to simulate with GPU particle simulations in realtime with GPU up to the number of particles of 8000. 33 41 42 file:///home/committee/aac/Thesis2008/s1130199 43 34 44 [[Image(HK_fig1.png)]] 35 45 [[Image(HK_fig2.png)]]
