University of Cambridge > Talks.cam > Computer Laboratory Computer Architecture Group Meeting > Parallel External Memory Model for Multicore Architectures

Parallel External Memory Model for Multicore Architectures

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Prof Simon Moore.

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.

This talk is part of the Computer Laboratory Computer Architecture Group Meeting series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2020 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity