Main navigation | Main content

HOME » PROGRAMS/ACTIVITIES » Annual Thematic Program

PROGRAMS/ACTIVITIES

Annual Thematic Program »Postdoctoral Fellowships »Hot Topics and Special »Public Lectures »New Directions »PI Programs »Industrial Programs »Seminars »Be an Organizer »Annual »Hot Topics »PI Summer »PI Conference »Applying to Participate »

Talk Abstract

Bandwidth-efficient parallel computation

Bandwidth-efficient parallel computation

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.