Design and Analysis of Parallel Cache-efficient Algorithms

芯片多处理器(即多核)正在迅速崛起，成为占主导地位的计算平台。该计算环境的特点是具有共享内存和缓存层次结构的并行计算。这项研究将为许多重要的问题开发并行和高速缓存高效的算法，以便有效地在多核上使用。这项研究的结果将是一套被证明是正确的有效利用多核的方法，这是至关重要的，因为每个桌面上都即将出现多核的现实。这些结果将广泛适用于所有依赖计算密集型任务的领域。

Chip multiprocessors (i.e., multicores) are rapidly emerging as the dominant platform for computing. This computing environment features parallel computing with shared-memory and a hierarchy of caches. This research will develop parallel and cache-efficient algorithms for many important problems that can be used effectively on multicores. The outcome of this research will be a set of provably correct methods for the efficient use of multicores, which is of critical importance given the imminent reality of multicores on every desktop. These results will have broad applicability to all fields that rely on compute-intensive tasks.