Path planning on a ring of processors ^∗∗

This work has been supported by the Research Project C3 of CNRS.

Abstract

In this paper, we discuss the implementation of Bitz and Kung's path planning algorithm on a ring of general-purpose processors. We show that Bitz and Kung's algorithm, originally designed for the Warp machine, is not efficient in this context, due to the intensive inter-processor communications that it requires. We design a modified version that is much more performing. The new version updates a segment of k positions within a step and allocates blocks of r consecutive rows of the map to the processors in a wraparound fashion. Bitz and Kung's algorithm corresponds to the situation (k, r) = (l, 1). We analytically determine the optimal values of the parameters (k, r) which minimize the parallel execution time as a function of the problem size n and of the number of processors p. The theoretical results are nicely corroborated by numerical experiments on a ring of 32 transputers.

Keywords:

• Path planning
• image sweep
• ring of processors
• data allocation strategies
• parallel algorithms
• dynamic programming

This work has been supported by the Research Project C3 of CNRS.

This work has been supported by the Research Project C3 of CNRS.

Notes

This work has been supported by the Research Project C3 of CNRS.