BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Parallel External Memory Model for Multicore Architectures - Nodar
 i Sitchinava\, University of California\, Irvine
DTSTART:20090417T151500Z
DTEND:20090417T161500Z
UID:TALK18005@talks.cam.ac.uk
CONTACT:Prof Simon Moore
DESCRIPTION:With the advent of multicore architectures\, or chip multi-pro
 cessors (CMPs)\, and the realization that processors are not increasing in
  speed the way they used to\, there is an increased realization that paral
 lelism is the primary remaining method for achieving orders of magnitude i
 mprovements in performance. Unfortunately\, the existing parallel models a
 re not very well suited for modern CMPs. In particular\, the communication
  among individual cores in the CMP architectures is conducted via shared m
 emory (just as in PRAM)\, but each processor takes advantage of private fa
 ster cache for local computations and transfers data to shared memory in b
 locks (just as in the External Memory (EM) model of Aggarwal and Vitter).\
 n\nIn 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 ar
 ray and rank a linked list. The solutions to these two problems lead to va
 rious efficient algorithms on trees and graphs\, such as computing lowest 
 common ancestors\, tree contraction and expression tree evaluation\, findi
 ng connected and bi-connected components and minimum spanning forest on gr
 aphs\, and ear decomposition of a bi-connected graph. All algorithms prese
 nted provide asymptotically optimal linear speedup in cache utilization co
 mpared to the single-processor EM counterparts.\n
LOCATION:SS03\, Computer Laboratory\, William Gates Building
END:VEVENT
END:VCALENDAR