Abstract

With the advent of multicore architectures, or chip multi-processors (CMPs), and the realization that processors are not increasing in speed the way they used to, there is an increased realization that parallelism is the primary remaining method for achieving orders of magnitude improvements in performance. Unfortunately, the existing parallel models are not very well suited for modern CMPs. In particular, the communication among individual cores in the CMP architectures is conducted via shared memory (just as in PRAM ), but each processor takes advantage of private faster cache for local computations and transfers data to shared memory in blocks (just as in the External Memory (EM) model of Aggarwal and Vitter).

In this talk, I will present the Parallel External Memory (PEM) model, which extends the EM model to the parallel setting. In the new model, I will show how to solve the fundamental problems of sorting items in an array and rank a linked list. The solutions to these two problems lead to various efficient algorithms on trees and graphs, such as computing lowest common ancestors, tree contraction and expression tree evaluation, finding connected and bi-connected components and minimum spanning forest on graphs, and ear decomposition of a bi-connected graph. All algorithms presented provide asymptotically optimal linear speedup in cache utilization compared to the single-processor EM counterparts.