Main navigation | Main content
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
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.
Connect With Us: |