This week's book giveaway is in the Spring forum.
We're giving away four copies of Spring in Action (5th edition) and have Craig Walls on-line!
See this thread for details.
Win a copy of Spring in Action (5th edition) this week in the Spring forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Knute Snortum
  • Junilu Lacar
  • paul wheaton
Saloon Keepers:
  • Ganesh Patekar
  • Frits Walraven
  • Tim Moores
  • Ron McLeod
  • Carey Brown
Bartenders:
  • Stephan van Hulst
  • salvin francis
  • Tim Holloway

Parallelizing Barnes-Hut algorithm with MPI: Is there any better method than the two methods listed?  RSS feed

 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I can think about two methods to code with C++ and MPI to simulate the N-Body problem using Barnes-Hut, but not sure which one is more efficient or if there is any other better methods.

1. First, one processor holds all the information of bodies for the entire system, builds a quadtree using that information, and then distributes subtrees to all other processors. Then each processor calculates the forces on bodies using the subtree it received. How would you distribute the quadtrees while keeping in mind load balancing issues? If the subtree that processor A receives is a subtree of processor B's subtree, what do you do so that forces between bodies aren't considered more than once? Is this an efficient method of parallelizing the algorithm?
2. Each processor receives a certain number of bodies, and builds its own quadtree using those bodies. Then, one after the other, each processor will send out its own bodies to all other processors, and have the processors calculate the forces on its own bodies. Afterwards, the information will be gathered back at the original processor that sent out the bodies. One main problem is that collisions are not detected if two bodies are on different processors. Is there any way to detect collisions without checking every body against every processor's bodies? Also, would this method yield correct results (forces/positions of the bodies)? This is my current implementation.
3. Any other better methods?


Thanks in advance!
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!