        |
 |
|
|||
|
|
Parallel Algorithms for Motion Planning
supported by NSF, Dept. of Education, Texas Higher Education Coordinating Board
Shawna Thomas, Gabriel Tanase, Nancy Amato, Laurence Rauchwerger
Project Alumni: Lucia K. Dale
In this project, we are developing parallel algorithms for motion planning applications. We are particularly interested in parallelizing probabilistic roadmap motion planning methods (PRMs), and have shown that significant, scalable speedups can be obtained with relatively little effort on the part of the developer. In our initial work, we demonstrated that PRMs are "embarrassingly parallel". In later work, we used STAPL, the Standard Template Adaptive Parallel Library, to produce a platform independent parallel implementation.
PRMs are Embarrassingly Parallel. PRMs consist of two phases, node generation and node connection, both of which can be easily parallelized. To generate n random nodes in parallel, we simply ask each of the p processors to generate n/p of them. Effective parallelization of the connection phase is essential to obtain scalable speedups since this typically accounts for 98% of the sequential computation time. A simple sequential connection algorithm attempts to connect every node to its k nearest neighbors. Suppose we group the n nodes into p sets, one for each processor. Then, a simple parallel solution is for each processor to compute the k nearest neighbors for its set of nodes and attempt the connections.
We tested the performance of our parallel motion planning implementation on an SGI Origin2000 with shared memory. Although this is a heavily utilized multi-user system, we consistently obtained measurable speedups.
| Speedups | |
 |
 |
| Node Generation | Node Connection |
Parallelization with STAPL. We use the Standard Template Adaptive Parallel Library (STAPL) to parallelize our existing motion planning and protein folding code. STAPL allows for easy transition from sequential code to parallel code by extending the ANSI C++ Standard Template Library, and it provides portable efficiency to different systems, both shared memory and distributed memory models, without requiring user code modification. We simply represent the roadmap in a pGraph, a parallel, distributed data structure provided by STAPL. The pGraph manages all communication for the user.
We obtained good speedups on multiple platforms, ranging from small linux clusters, to distributed shared memory machines, to massively parallel machines. We obtained similar preformance results for all three types of proteins.
 |
 |
| Total time | Each phase for Protein CTXIII |
 |
 |
| Total time | Each phase for Protein A |
 |
 |
| Total time | Each phase for Protein G |
 |
 |
| Total time | Each phase for Protein CTXIII |
Related Projects
Parallel Protein Folding with STAPL, Shawna Thomas, Gabriel Tanase, Lucia K. Dale, Jose M. Moreira, Lawrence Rauchwerger, Nancy M. Amato, Concurrency and Computation: Practice and Experience, 17(14):1643-1656, Dec 2005.
Journal(ps, pdf, abstract)
Parallel Protein Folding with STAPL, Shawna Thomas, Nancy M. Amato, In Proc. IEEE Int. Wkshp. on High Performance Computational Biology, Santa Fe, NM, Apr 2004.
Proceedings(ps, pdf, abstract)
Probabilistic Roadmap Methods are Embarrassingly Parallel, Nancy M. Amato, Lucia K. Dale, In Proc. IEEE Int. Conf. Robot.
Autom. (ICRA), pp. 688-694, Detroit, Michigan, USA, May 1999.
Proceedings(ps, pdf, abstract)
Parasol Home | Research | People | General info | Seminars | Resources Parasol Lab, 301 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112 Contact Webmaster Phone 979.458.0722 Fax 979.458.0718 
Department of Computer Science and Engineering | Dwight Look College of Engineering | Texas A&M University Privacy statement: Computer Science and Engineering Engineering TAMU |