Lopata Hall 101
Dr. Vijaya Ramachandran
University of Texas at Austin
Efficient Resource-Oblivious Algorithms for Multicores
The multicore revolution represents a paradigm shift in computing, as parallelism becomes ubiquitous. Barring a few exceptions, the theory of parallel algorithms has remained focused on the decades-old approaches of designing algorithms for the PRAM model and for bulk-synchronous computing.
In this talk we consider cost measures and algorithmic strategies that are geared to current parallel multicore environments. We view the multicore as consisting of multiple cores, each having a private cache, which communicate through shared memory, with data organized in blocks of words. It has a run-time scheduler that schedules parallel tasks that are generated by the parallel algorithm being executed.
We introduce the notion of a resource-oblivious parallel algorithm, that is designed without any reference to the machine parameters such as number of cores, and cache and block sizes, or to the run-time scheduler. We characterize a class of multithreaded resource-oblivious algorithms for which we establish low cache miss and false sharing overhead on multicores with a wide range of machine parameters, as long as the run-time scheduler is efficient in terms of the number of parallel tasks it schedules across the caches. This class includes algorithms with high levels of parallelism for matrix computations, FFT, sorting, list ranking and other basic problems.
This is joint work with Richard Cole, NYU.
Vijaya Ramachandran received a Ph.D. in EECS from Princeton University. She served on the faculty of the University of Illinois at Urbana-Champaign, and then at the University of Texas at Austin, where she has been a Professor of Computer Science since 1995. Her research interests are in algorithm design and analysis, and in parallel computation. She has served on the Editorial Boards of several journals in theoretical computer science, including Journal of the ACM, SIAM Journal on Computing, SIAM Journal on Discrete Mathematics, and ACM Transactions on Algorithms.
Computer Science & Engineering
Computer Science and Engineering (314) 935-6160
Back to Calendar