Cache Efficient Simple Dynamic Programming
by
Cary Cherng
Simple dynamic programming solves the problem of computing the product
of elements under all possible groupings. This is done by solving all
contiguous subproblems. For large problem sizes the standard algorithm
suffers from many cache misses. New cache-oblivious and cache-aware
algorithms based Valiant's context-free language recognition algorithm
are implemented, analyzed, and empirically evaluated with timing
studies and cache simulations. The studies show that for large inputs
they perform significantly faster than the standard algorithm.
Advised by Richard Ladner
CSE 403
Wednesday
February 2, 2005
3:30 - 4:20 pm