Summary: We believe that for the next few years, the most pressing research question in parallel computation will concern communication bandwidth: Can we design fast algorithms for parallel computers that only support low bandwidth communication (such as most existing parallel computers). An alternative formulation of the question is, can we design parallel algorithms that have communication locality? While good locality preserving techniques are known for application problems with regular, predictable dataflow, few theoretical results have been developed for irregular problems e.g. problems involving sparse graphs, or problems that adapt to data distribution dynamically. And yet, since most existing parallel computers only offer low communication bandwidth, it is necessary to either develop techniques to live with low bandwidth, or provide arguments in favor of building parallel computers with high bandwidth communication systems.
This paper provides a rough sketch of a research plan for rigorously answering some of these questions. First, we propose a formal definition of what it means to exploit locality, e.g. to be able to decide whether it is possible to exploit locality for a given problem, and if so, to what extent a given implementation is successful in it. Using our formal notion of locality, we describe some preliminary work regarding the development of strategies to exploit locality. Finally, our formal definition opens up the possibility of formally proving that a given problem does not have locality though it may have parallelism), i.e. it is impossible to design fast algorithms for the problem without having high communication bandwidth. We give examples of some such problems.
For the entire collection see [Zbl 0851.00043].