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 ofr parallel computers that only support low bandwidth communication. An alternative formultatin of the question is , can we design parallel algorithms that have communication locality? While good locality preserving tehcniques are knowen ofr applciation problems with regular, predicatable dataflwo, few theoretical results ahve been developed for irregualr problems e.g. problems involvign sparse graphs, or problems that adapt to data distribution dynamically. And yet, since most existing parallel ocmputers 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 ocmputers wiht high bandwidth communication systems. THis paper provides a rough sketch of a research plan for rigorously answering some of htese questions. First, we propsoe a formal defintion of what it means to exploit locality, e.g. to be able to decide whether it is posible 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 ofrmal definition opens up the possibility of formally proving that a given problem does not have localiy, i.e. it is impossible to design fast algorithms for the problem without having high ocmmunicaiton bandwidth. We give examples of such problems.
展开▼
