Presenting his paper with Vijaya Ramachandran
Abstract: Multicore chips, already the predominant desktop technology, are projected to have increasing numbers of cores, perhaps as many as 50--100 five years hence. Effectively exploiting this parallelism appears to call for parallel algorithms with data locality. Over the last decade, data locality in a sequential setting has been addressed in part via cache oblivious algorithms. (A cache oblivious algorithm does not know or use memory parameters such as block or page size, the time needed for a cache miss, etc. It's virtue is simplicity. The algorithmic challenge is to match the performance of parameter aware algorithms, at least up to modest constant factors. This has been achieved for many problems.) The current work explores to what extent obliviousness may be possible in the multicore setting. We seek algorithms that are oblivious to both memory parameters and to the number of cores. We show this is possible by developing oblivious algorithms for this setting, including a new sorting algorithm which achieves (asymptotically) optimal operation and cache-miss count, and a critical path length of O(log n log log n) for sorting n items.