Abstract:
I will talk about a new model of parallel computation which is designed with multicore architectures in mind. The model takes into explicit consideration the cache-oriented nature of inputs and outputs in modern CPUs. I will present a parallel sorting algorithm which is provably optimal in both running time and cache-miss rate.
This is joint work with Michael Goodrich and Michael Nelson.