[Colloq] PhD Thesis Defense: Xiaoqin Ma

[Chantal Cardona]

College of Computer and Information Science PhD Thesis Defense: Xiaoqin Ma

Title: Designing and Analyzing Cache-Conscious Algorithms for Applications
with Irregular Memory Access Patterns

Date: Thursday, December 8, 2005, 1:30pm -3:30pm
Location: 366 WVH (CCIS Conference room)

Abstract:
This research is motivated by the increasing performance disparity between
CPU and memory.  This performance disparity between CPU and memory will
continue in the foreseeable future with the new technologies, such as
dual/quad core CPUs. Many classic computer science algorithms and
commercial applications have shown that memory is the performance
bottleneck on modern hardware.

Focusing on making efficient use of CPU cache and reducing the memory
access cost, this dissertations describes the research that aims at
understanding, modeling, and improving some classic computer science
algorithms' performance on modern hardware. We study the memory
performance both in a single processor environment and in a distributed
environment.

We begin with constructing a model, the MBRAM model, to analyze a
program's memory performance in a single processor environment. The MBRAM
model can statically predict a program's running time by identifying
different memory access patterns and counting the number of memory
accesses. The MBRAM model can be implemented in a compiler to
automatically optimize memory access patterns in a program at
compile-time. With the MBRAM model as guidance, different optimizations'
benefits can be easily computed at compile-time and the best optimization
can be easily selected.

Then we design a series of cache conscious solutions for some classic
algorithms in computer science whose traditional solutions are affected
significantly by memory performance: faster permutation multiplication;
faster object rearrangement; cache conscious sorting and join in database
system; distributed in-cache data structure for index structure lookup and
tree traversal algorithms. These classic algorithms are common subroutines
of many applications. The performance improvement for these algorithms
will have a great performance impact  both on commercial applications and
scientific computations.


Committee:
Prof. Gene Cooperman, NU (advisor)
Prof. Betty Salzberg, NU
Prof. David Kaeli, NU
Prof. Donghui Zhang, NU
Dr. Jiri Schindler, EMC