Parallel algorithms that solve problems by communication
D. Sharp, Martin Cripps · IEEE Symposium on Parallel and Distributed Processing (SPDP) · 2002
Most current parallel computers are made from tens of processors that may communicate with each other (fairly slowly) by means of static intercommunication paths. However, in the future the use of optical communication media and wafer scale integration will facilitate construction of computers with thousands of simple processors each of which may communicate simultaneously with any other. What will these computers run? The authors present three novel algorithms that solve problems by communication (quicksort, tessellation and fractals). One, fractal image generation, works purely by iterative communication which is interesting because studies of the human brain indicate that the connections between neurons are mainly responsible for our powers of thought. These algorithms combine features of both imperative and connectionist programming styles and arose from a systematic study of goal-directed program transformation, including the target architecture with the program specification. They are examples of a whole class of such algorithms which the authors expect will be developed similarly.>
Cited by 10 works. doi:10.1109/spdp.1991.218293
Authors
References
- The Art of Computer Programming: Volume 3: Sorting and Searching
- The Art of Computer Programming, Vol. 3: Sorting and Searching
- Geometric complexity
- Fractals Everywhere
- Computing Dirichlet Tessellations in the Plane
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- Data parallel algorithms
- New Parallel-Sorting Schemes
- Fast parallel sorting algorithms
- A better way to compress images