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.
