ICS Theory Group

CompSci 269S, Winter 2007: Theory Seminar

Mar 16, 2007, 1:00pm, in CS 243

Parallel External Memory Model

Nodari Sitchinava, UCI


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.