Optimization of Barnes-Hut Multithread Insertion algorithm
You should know, what's the bottleneck. Do you have two locks altogether? This doesn't sound good, as each part of the tree can be worked independently on. This means you could run on hundreds of CPUs efficiently.

The operations you do under lock are rather simple, which means that the overhead of locking can be significant. Can't you separate the three into a few parts and assign one CPU to each part?



Now some boring general comments:

boolean run = true;
while(run){
    i = barnesHut.getIndex();
    if(i &lt; particle.length){ tree.insertThreaded(particle[i], thread); }
    else{ run = false; }
}


Where is i defined? Anyway, unobfuscate to

while (true) {
    int i = barnesHut.getIndex();
    if (i &gt;= particle.length) break;
    tree.insertThreaded(particle[i], thread);
}




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


That's what AtomicInt#incrementAndGet() is for.



Use better spacing, if (i &lt; particle.length) { instead of if(i &lt; particle.length){.