Parallel External Memory Model for Multicore Architectures

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

• Nodari Sitchinava, University of California, Irvine
• Friday 17 April 2009, 16:15-17:15
• SS03, Computer Laboratory, William Gates Building.

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.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory Computer Architecture Group Meeting
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• SS03, Computer Laboratory, William Gates Building
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.