## February 11, Winter Quarter 2010: Theory Seminar

### 1:00pm in 4011 Bren Hall

#
Resource Oblivious Multicore Sorting

## Richard Cole, NYU

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.