[Colloq] PhD Thesis Proposal, Xiaoqin Ma, March 28

[Gene Cooperman]

College of Computer and Information Science
PhD Thesis Proposal:  New Cache-Conscious Algorithms for
                      Applications with Irregular Memory Access Patterns


SPEAKER:  Xiaoqin Ma
TIME:   Monday, Mar. 28, 9:00 a.m.
PLACE:  366 West Village H
Advisor:  Gene Cooperman

The research is motivated by the increasing gap between CPU
performance and memory performance. As demonstrated in the past two
decades, the CPU speed has been increasing at 50\% per year, but memory
latency has not improved over the last decade.  This performance
disparity between CPU and memory will continue in the foreseeable
future.  

We develop the MBRAM model (Memory-Bound Realistic Analytical Model),
which is able to make accurate predictions of running times based on
a static analysis of pseudo-code.  This allows us to first design
an algorithm and to estimate its running time with good accuracy.

With this insight, we then develop faster cache-aware solutions for:

1.  Object rearrangement (includes permutation multiplication as
			  a special case)
2.  In-memory sorting
3.  Index structure lookup and tree traversal

The last solution is a distributed solution over the nodes of a cluster,
which we call cooperative CPU caching.




_______________________________________________
Colloq mailing list
Colloq at lists.ccs.neu.edu
https://lists.ccs.neu.edu/bin/listinfo/colloq