| In this dissertation we propose the parallel external memory (PEM) model -- a parallel model for private-cache chip multiprocessors (CMPs). By focusing on private-cache CMPs, we show that we can design efficient algorithms that need no additional assumptions about the way that processors are interconnected. In particular we assume that all inter-processor communication occurs through the memory hierarchy.;We study several parallel algorithms fundamental for any parallel model: all-prefix-sums, gather and scatter, selection, partitioning and sorting. We also study problems on graphs. We present efficient solution to the list ranking problem -- a key result to solving other problems on graphs in parallel. We address the problems of finding Euler tour and lowest common ancestors on trees, connected and bi-connected components on graphs, minimum spanning tree on connected graphs and ear decomposition on bi-connected graphs. Finally, we address the computational geometry problem of computing the convex hull on a set of points in the plane. |
