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.

Speedups for Linux Cluster A It consists of four boards, each of which has two processors and 2 GB RAM. Two boards have 1 GHz processors with 256 KB caches, and two boards have 1.1 GHz processors with 512 KB caches. They are connected with a Gbit dedicated Ethernet switch.
Total time	Each phase for Protein CTXIII
Speedups for SGI Altix 3700 A distributed shared-memory machine in the Texas A&M University Supercomputing facility. It contains 32 nodes, each with two pairs of 1.3 GHz 64-bit processors, and 256 GB RAM.
Total time	Each phase for Protein A
Speedups for MCR A large, dedicated Linux cluster at the Lawrence Livermore National Laboratory. It has 1152 nodes with two 2.4 GHz processors and 4 GB RAM each. They are connected with a Gbit Ethernet switch.
Total time	Each phase for Protein G
Speedups for BlueGene/L A scalable massively parallel 180 Teraflop machine which will have up to 65,536 compute nodes, each with 256 MB of memory, configured as a 64x32x32 three-dimensional torus. Each node has a single ASIC and 256 MB of memory.
Total time	Each phase for Protein CTXIII

Related Projects

STAPL
Protein Folding

Papers

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 | Dwight Look College of Engineering | Texas A&M University     Privacy statement: Computer Science Engineering TAMU