Over the last 20 years there has been much theoretical work in parallel pointer-based algorithm design. Often these algorithms are asymptotically very fast but are so complex and have such large constant factors that they are useful only for extremely large data sets. In addition, most of this theoretical work is based on the Parallel Random Access Memory (PRAM) machine model. Critics complain that the model is not realistic because it assumes that the time for memory access is comparable to the time for other operations and there is no cost for synchronization. On most multiprocessor machines memory access can be 100 times slower than a floating point operation. If the PRAM is unrealistic, then do PRAM algorithms have any value? What is the performance of PRAM pointer-based algorithms in practice? Do they necessarily have poor performance?
I have been studying two fundamental pointer-based problems, list ranking and maintaining dynamic balanced trees. They pose the same challenges common to most fine-grain pointer-based parallel algorithms: The parallel algorithms can be quite different from their serial counterparts and often having much higher overheads, memory accesses that are hard to optimize and cannot be scheduled at compile time, and huge communication bandwidth requirements. My goal is to show that, by designing PRAM algorithms that are work efficient and have small constants and by using new implementations techniques, parallel pointer-based algorithms can indeed have substantial speedup over fast workstations.
I am also interested in pursuing research in computational biology.