PARALLEL COMPUTING OF PHYSICAL MAPS - A COMPARATIVE-STUDY IN SIMD ANDMIMD PARALLELISM

Ordering clones from a genomic Library into physical maps of whole chr omosomes presents a central computational problem in genetics. Chromos ome reconstruction via clone ordering is usually isomorphic to the NP- complete Optimal Linear Arrangement problem, Parallel SPMD and MIMD al gorithms for simulated annealing based on Markov chain distribution ar e proposed and applied to the problem of chromosome reconstruction via clone ordering, Perturbation methods and problem-specific annealing h euristics are proposed and described, The SIMD algorithms are implemen ted on a 2048 processor MasPar MP-2 system which is an SIMD 2-D toroid al mesh architecture whereas the MIMD algorithms are implemented on an 8 processor Intel iPSC/860 which is an MIMD hypercube architecture A comparative analysis of the various SIMD and MIMD algorithms is presen ted in which the convergence, speedup, and scalability characteristics of the various algorithms are analyzed and discussed, On a fine-grain ed, massively parallel SIMD architecture with a low synchronization ov erhead such as the MasPar MP-2, a parallel simulated annealing algorit hm based on multiple periodically interacting searches performs the be st, For a coarse-grained MIMD architecture with high synchronization o verhead such as the Intel iPSC/860, a parallel simulated annealing alg orithm based on multiple independent searches yields the best results, In either case, distribution of clonal data across multiple processor s is shown to exacerbate the tendency of the parallel simulated anneal ing algorithm to get trapped in a local optimum.