URSI 2003 - WEB Dynamics
In the summer of 2003, I participated in the Undergraduate Research Summer Institute at Vassar College. I worked with Dr. Brad Richards of the Computer Science Department at Vassar. For our research, Dr. Richards and I were investigating the Weighted-Ensemble Brownian (WEB) dynamics algorithm, which is an algorithm for simulating Brownian motion.
Brownian motion and the WEB Dynamics algorithm
Brownian motion is the random movement of particles, caused by their bombardment on all sides by bigger molecules. This motion can be seen in the behavior of pollen grains placed in a glass of water, or in a speck of dust in a light beam. Because this motion often drives the interaction of molecules within a system, simulations of Brownian motion are important in several fields, such as biochemistry and drug design. However, simulating Brownian motion by brute force is often slow and inefficient, because the interactions of interest occur only infrequently.
The WEB dynamics algorithm is important because it provides a faster way to accurately simulate Brownian motion. This algorithm was developed in 1996 by Sangtae Kim of the Department of Chemical Engineering at the University of Wisconsin - Madison. The algorithm works by using weighted particles instead of simple particles, and by partitioning the total space being dealt with, such that all the parts have approximately equal numbers of particles at the end of each iteration. The particle weights maintain statistical accuracy during the particle readjustments that keep the parts balanced. Because the algorithm focuses resources in the areas of interest, fewer particles are required, and results are seen in fewer iterations of the simulation.
The objective of our research was to develop a simple sequential WEB-based simulator, and ultimately, to parallelize the algorithm on both a distributed memeiry system and a shared memory system. These models would be implemented using MPI and threads respectively.
Summary of Work
Our research process was split up into several steps:
- Given the simple (brute-force) Brownian motion simulator and a sequential WEB dynamics-based simulator written by Dr. Richards, I validated the two versions and ensured that they achieved the same results.
- The next step involved learning about parallel programming, as I did not know anything about it at that point. To this end, I completed a few small projects assigned to me by Dr. Richards in order to familiarize myself with the basic concept.
- After learning the basics of parallel programming, I applied what I had learned to the project at hand. I parallelized the sequential WEB dynamics version of the algorithm by using MPI on a distributed memory system. This parallel version was validated against the two previous versions of the simulator, and although the correct results were achieved, the speed-up observed was not as good as we had hoped. We therefore decided to direct our energies towards a shared memory model, in the hope that we would see better speed-up.
This was as far as we got over the summer. However, we continued the research project during the Spring semester of 2004.
- Our next objective was to parallelize the algorithm using threads on a shared memory system. Unlike the previous versions, which were all written in C++, we decided to write this version of the simulator in Java. This is because Java has a native threads model, and this project provided a chance to learn more about it.
- The next step was therefore to "translate" the sequential WEB dynamics version of the simulator in C++ into Java, and then to validate it against existing versions. This version was observed to run a little slower than its C++ equivalent.
- Now that we have a Java version of the sequential WEB dynamics simulator, the next step would be to parallelize it. This has not yet been completed, and the project is still in progress.
Presentations
- In September 2003, I presented a poster of my work at the Vassar College URSI Symposium.
- In April 2004, I attended the Consortium for Computing Sciences in Colleges - Northeastern Conference at Union College, Schenectady, NY, where I presented a poster.
- In May 2004, I participated in the Mid-Hudson Technology Council's Scintilla Forum where I presented a talk on my work, for which I earned first prize. A copy of my talk can be found here.
