This parallel code (a SIMPLE/SMP module) evaluates arithmetic expression trees using the algorithmic techniques of list ranking and tree contraction; this problem is not only of interest in its own right, but is representative of a large class of irregular combinatorial problems that have simple and efficient sequential implementations and fast PRAM algorithms, but have no known efficient parallel implementations.

References:

D.A. Bader, S. Sreshta, and N.R. Weisse-Bernstein, "Evaluating Arithmetic Expressions using Tree Contraction: A Fast and Scalable Parallel Implementation for Symmetric Multiprocessors (SMPs)," 9th International Conference on High Performance Computing (HiPC 2002), Bangalore, India, Lecture Notes in Computer Science, 2552:63-75, December 2002.