Neighborhood algorithm optimization and parallelization for shared memory computing

Key Words and Key Phrases: Neighborhood algorithm, overlapping detection, serial, parallel, shared memory computer, computer architecture

Introduction/Background:

1. Presently, the neighborhood algorithm can optimize results in various fields, such as
1) Simulating the collision of characters in neighborhood environment of real time games
2) Calculating the optimal path in the searching algorithm of robots
3) Doing simulation between physical particles.
2. The multi-processor-computer comes more and more common in both the daily life and scientific areas.
3. Neighborhood algorithm optimization and parallelization will improve the efficiency of above areas.

Objectives:

Optimize and parallelize the code from one-dimensional to three-dimensional in order to take the better use of the multi-core host.
Short-term goal: Optimize and parallelize the one-dimensional code
Long-term goal: Optimize and parallelize the three-dimensional code

Methodology:

1. Understand mathematic module.
2. Rewrite the code from one-dimensional to three-dimensional. In every dimension:
1) Analyze the present code.
2) Optimize serial code structure in preparation for parallelization.
3) Parallelize the serial code to take better use the multi-core host.
4) Debugging to avoid errors and decrease of the accuracy.
3. Find the change in run time.
4. Analyze the result, find how much time it will save.
Serial to parallel
1. MATLAB can't start the parallel function automatically. So before the code executed , ‘matlabpool local’ command must be inputted to tell the multi-processors to work at the same time. During the computation, the task will be divided into multi-threads for computing.
2. The most common part which should be changed from serial to parallel is ‘for loop’. In the parallel code, it will be used as ‘parfor loop’. There are some rules to follow in the ‘parfor loop’ as the following shows:
1) Calculations in ‘parfor loop’ are independent every time, no relative parameters are allowed. Hence, the form such as ‘a(i+1)=a(i)+1’ must be replaced by a new way. In this research, the array “koordinate” is this kind of parameter, the serial code updates the coordinate on basis of the previous coordinate. To avoid this situation, random generation method will be used.
2) Global parameters can’t be used in some parallel functions. So all the global parameters have been replaced by creating new parameters and deliver them to relative functions.
3) Some parallel functions don’t allow loop nest such as “for” and “while”. Otherwise, some errors will happen.

Evaluation Policies:

1. Run time: After optimization and parallelization, the run time will decrease in theory.
2. Utilization ratio of the multi-processors: In serial code, only one processor will be used, when changed into parallel one, the other processors will be used at the same time.

Results:

Conclusions:

(1)The number of the particals has tiny influence on the run time, but the sweep times have great influence.
(2)Changing the serial code into parallel one will save the run time. The larger the sweep times change, the more time will be saved in parallel code.

Future works:

(1)Understand how to program in FORTRAN
(2)Accomplish the optimization and parallelization from one-dimensional code to three-dimensional code