This paper investigates the design of parallel algorithmic strategies that address the efficient use of both, memory hierarchies within each processor and a multilevel clustered structure of the interconnection between processors. In the past, these phenomena have usually been addressed separately. This paper is a first step towards parallel algorithmic strategies which address both at the same time. As a case study, we investigate the distribution sweeping method which has been very effective for the design of external memory algorithms for computational geometry problems. We present a novel method for parallel distribution sweeping on a clustered parallel machine with hierarchical local memories, showing that it yields optimal computation, communication and memory access times for a number of geometry problems.

Additional Metadata
Persistent URL dx.doi.org/10.1109/IPDPS.2002.1015508
Conference 16th International Parallel and Distributed Processing Symposium, IPDPS 2002
Citation
Dehne, F, Mardegan, S., Pietracaprina, A., & Prencipe, G. (2002). Distribution sweeping on clustered machines with hierarchical memories. Presented at the 16th International Parallel and Distributed Processing Symposium, IPDPS 2002. doi:10.1109/IPDPS.2002.1015508