"Parallel computing on uniform-memory-access shared-memory architectures: linear speed-ups for complex combinatorial problems"
Bernard Moret (moret@cs.unm.edu)
Up to now, parallel computing has been almost entirely restricted to "embarrassingly parallel problems" (such as Monte Carlo simulations) and highly regular problems (such as grid-based computations) and as such has not seen much use in complex combinatorial optimization tasks of the type often encountered in computational biology (phylogeny reconstruction, multiple sequence alignment, etc.). A new class of machines has been introduced recently by Sun Microsystems, machines that offer true shared memory and uniform memory access. Our preliminary experiments on these machines suggest that they will enable us to use 20 years of research in parallel algorithms developed for the PRAM model and thus to obtain linear speed-ups for complex combinatorial optimization problems. In turn, these speed-ups will enable the scientific community to revisit problems given up as too hard 20 years ago and, in particular, will make an enormous difference in computational biology.