LANS Research


CACHE Institute : Communication Avoidance and Communication Hiding at the Extreme Scale

Paul Hovland

MCS People Involved:
Lois Curfman McInnes, Boyana Norris, Stefan Wild

Additional People:
Erich Strohmaier (Project Lead, LBNL), James Demmel (UCB), Michelle Mills Strout (CSU)

Other Institutes:
Lawrence Berkeley National Laboratory, UC Berkeley, Colorado State University


Our goal is to have applied mathematicians and computer scientists collaborate to reduce the two major obstacles to productively using future extreme scale computer architectures: the cost of communication, and the programming effort required to write efficient programs on these increasingly large and complicated machines. Communication means moving data (either between levels of a memory hierarchy, or between processors on a network) and synchronization. Both bandwidth costs (proportional to the number of words moved) and latency costs (proportional to the number of messages, or packets of contiguous data) are important to minimize. Mathematical innovation is needed to develop new algorithms that do less communication than current algorithms, which were mostly designed to minimize arithmetic operations rather than communication (sometimes minimizing the two goes together, but not always, as we will see). Computer science innovation is needed to make programming these more complicated algorithms easier on these more complicated and possibly heterogeneous architectures, as well as more easily finding the fastest implementation out of the combinatorial explosion of possibilities.