Cartesian computations and the high cost of moving data
Larry Carter (University of California, San Diego)
COMPUTER SYSTEMS SEMINARDATE: 2013-11-29
TIME: 15:00:00 - 16:00:00
LOCATION: Physics and Phsychology G6 lecture theatre, building 38, ANU campus
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
In this talk, we identify and analyze a class of algorithms that includes many familiar scientific computations, such as sparse matrix-vector products, and more generally many map-reduce algorithms . A "2-D Cartesian computation" is characterized by having two very large data structures, A and B (perhaps A is the input and B is the output), and for each suitably chosen chunk of A and chunk of B, there is a chunk of computation that must be performed.
When neither A nor B fits in the fast memory of a computer, the time (or energy) needed to move bits between cores, chips, nodes and levels of the memory hierarchy can dominate the computation cost.
Static Partitioning, Tiling, Inspector/Executor strategies, and Bucketizing are some well-known programming techniques that reduce data movement. We present a methodology that, for many Cartesian computations, allows one to decide which is the best of these techniques.
Our results elegantly relate three orthogonal aspects of a computer -- computation speed, memory capacity, and communication or memory bandwidth -- and show that different techniques are needed at different levels of architectural granularity.
BIO:
Larry Carter received the A.B. degree from Dartmouth College in 1969 and the Ph.D. in mathematics from the University of California at Berkeley in 1974. He worked at as a Research Staff Member and manager at IBM's T.J. Watson Research Center for nearly 20 years in the areas of probabilistic algorithms, compilers, VLSI testing, and high-performance computation.
From 1994 to 2004, Dr. Carter was a Professor in the Computer Science and Engineering Department of the University of California at San Diego and a Senior Fellow at the San Diego Supercomputer Center. His current research interests include scientific computation, performance programming, parallel computation, and computer architecture. Prof. Carter is a Fellow of the IEEE, and a Professor Emeritus at UCSD.
