Portable parallel algorithms for geometric problems

The development of algorithms which can be ported among different fine-grain, massively parallel architectures and yield reasonably good implementations on each is discussed. The approach is to write algorithms in terms of general data movement operations and then implement the data movement operations on the target architecture. Efficient implementation of the data movement operations requires careful programming, but since the data movement operations form the foundation of many programs, the cost of implementing them can be amortized. The use of data movement operations also helps programmers think in terms of higher-level programming units, in the same way that the use of standard data structures helps programmers of serial computers. An approach is described for designing efficient, portable algorithms, and sample algorithms are given to solve some fundamental geometric problems. The difficulties of portability and efficiency for these geometric problems are redirected into similar difficulties for the standardized operations.