Computer Science Speakers Calendar

Back to Listing

Vijaya Ramachandran (Efficient Resource-Oblivious Multithreaded Algorithms)

Event Type
The Department of Computer Science, University of Illinois, Scientific Computing & Theory and Algorithms
4403 Siebel
Aug 22, 2017   2:00 pm  
Vijaya Ramachandran, Blakemore Regents Professor of Computer Science, The University of Texas @ Austin
Joe Jeffries

Abstract:  We introduce the notion of a resource-oblivious parallel algorithm, which is an algorithm designed without any reference to the machine parameters such as number of cores,  cache size and block size, or to the run-time scheduler. We present 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 efficient algorithms with high levels of parallelism for matrix multiplication, FFT, sorting, list ranking, graph connectivity, sequence alignment and other basic problems.


Bio:  Vijaya Ramachandran is Professor of Computer Science at University of Texas at Austin.  She received a Ph.D. in EECS from Princeton University.  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. She currently serves on the Editorial Board of ACM Transactions on Parallel Computing.

link for robots only