• 1

• 35.2k
• 13
• 134
• 238

Java 1.7: Optimization of Barnes-Hut Multithread Insertion algorithm

• 41
• 2

I'm currently working on optimizing a barnes-hut implementation ( connected to a previous post I did ) and I need help to optimize it further.

After some testing, the main problem appears to be in the Insertion algorithm, which takes roughly 3-10 times as long as the second longest part of the program.

The basis of the program are a number of threads that each act as a worker that does the following when building the tree:

//particle[] is a list that is set in the constructor
public void run(){
 boolean run = true;
 
 while(run){
 i = barnesHut.getIndex();
 
 if(i < particle.length){ tree.insertThreaded(particle[i], thread); }
 else{ run = false; }
 }
}

the getIndex function can be found in the BarnesHut class which handles the start of the program and the insertion algorithm. It's synchronized to work as a

public synchronized int getIndex(){
 return index++;
}

Now, the insertion algorithm looks like this:

//entryLock and quadLock are two atomic mutex locks
//childs[][] are the leaves to the tree structur that makes up a Barnes-Hut
public void insertThreaded(BHBody body, int threadID){
 entryLock.lock();
 numberOfParticles++;
 if(numberOfParticles == 1){
 existingParticle = body;
 entryLock.unlock();
 }
 else if(numberOfParticles == 2){
 quadLock.lock();
 
 entryLock.unlock();
 int[] position = getQuadForBody(existingParticle);
 if(childs[position[0]][position[1]] == null){
 startQuad(position[0],position[1]);
 }
 quadLock.unlock();
 
 childs[ position[0] ][ position[1] ].insertThreaded(existingParticle, threadID);
 
 quadLock.lock();
 position = getQuadForBody(body);
 if(childs[position[0]][position[1]] == null){
 startQuad(position[0],position[1]);
 }
 quadLock.unlock();
 
 childs[ position[0] ][ position[1] ].insertThreaded(body, threadID);
 }
 else if(numberOfParticles > 2){
 entryLock.unlock();
 
 quadLock.lock();
 int[] position = getQuadForBody(body);
 if(childs[position[0]][position[1]] == null){
 startQuad(position[0],position[1]);
 }
 quadLock.unlock();
 childs[position[0]][position[1]].insertThreaded(body, threadID); 
 }
}

The locks are to make sure that no other thread gets into the way of the thread when its creating something vital, such as a new leaf or even trying to update the number of particles.

The startQuad function which creates a new leaf for the current node:

public void startQuad(int x, int y){
 if(x == 0 && y == 0)
 childs[0][0] = new BHnode(xStart,xMid,yMid,yEnd, debug, range,correction);
 if(x == 0 && y == 1)
 childs[0][1] = new BHnode(xStart,xMid,yStart,yMid, debug, range,correction);
 if(x == 1 && y == 0)
 childs[1][0] = new BHnode(xMid,xEnd, yMid,yEnd, debug, range,correction);
 if(x == 1 && y == 1)
 childs[1][1] = new BHnode(xMid,xEnd,yStart,yMid, debug, range,correction);
}

The getQuad function which returns the quad for the body to be inserted into:

public int[] getQuadForBody(BHBody body){
 int x = 0, y = 0;
 if( body.getX() > xMid ){
 x++;
 }
 if( body.getY() < yMid ){
 y++;
 }
 int[] a = {x,y};
 if(debug){
 System.out.println("setting ("+body.getX()+","+body.getY()+") at ("+x+","+y+") with mid " +xMid+","+yMid);
 helper.sleepSeconds(2);
 }
 return a;
}

If anyone has any suggestions on how to improve this code I would be grateful. I've tried a lot of different things, from completly rewriting parts of the code to making things in a different order.