To take advantage of the various high performance computer (HPC) architectures for multithreaded and distributed computing, this paper parallelizes the dynamic programming algorithm for multiple sequence alignment (MSA). A novel definition of a hyper-diagonal through a tensor space is used to reduce the search space. Experiments demonstrate that scoring less than 1% of the search space produces the same optimal results as scoring the full search space. The alignment scores are often better than other heuristic methods and are capable of aligning more divergent sequences.

Optimal multiple sequence alignment by dynamic programming, like many highly dimensional scientific computing problems, has failed to benefit from the improvements in computing performance brought about by multi-processor systems, due to the lack of suitable scheme to manage partitioning and dependencies. A scheme for parallel implementation of the dynamic programming multiple sequence alignment is presented, based on a peer to peer design and a multidimensional array indexing method. This design results in up to 5-fold improvement compared to a previously described master/slave design, and scales favourably with the number of processors used. This study demonstrates an approach for parallelising multi-dimensional dynamic programming and similar algorithms utilizing multi-processor architectures.

We consider the analysis and optimization of code utilizing operations and functions operating on entire arrays. Models are developed for studying the minimization of the number of materializations of array-valued temporaries in basic blocks, each consisting of a sequence of assignment statements involving array-valued variables. We derive lower bounds on the number of materializations required, and develop several algorithms minimizing the number of materializations, subject to a simple constraint on allowable statement rearrangement. In contrast, we also show that when statement rearrangement is unconstrained, minimizing the number of materializations becomes NP-complete, even for very simple basic blocks.

Large scale scientific computing necessitates finding a way to match the high level understanding of how a problem can be solved with the details of its computation in a processing environment organized as networks of processors. Effective utilization of parallel architectures can then be achieved by using formal methods to describe both computations and computational organizations within these networks. By returning to the mathematical treatment of a problem as a high level numerical algorithm we can express it as an algorithmic formalism that captures the inherent parallelism of the computation. We then give a meta description of an architecture followed by the use of transformational techniques to convert the high level description into a program that utilizes the architecture effectively. The hope is that one formalism can be used to describe both computations as well as architectures and that a methodology for automatically transforming computations can be developed. The formalism and methodology presented in the paper is a first step toward the ambitious goals described above. It uses a theory of arrays, the Psi calculus, as the formalism, and two levels of conversions—one for simplification and another for data mapping.

The PRAM model has been shown to be an optimal design for emulating both loose and tightly coupled multiprocessors for unit time operations. When virtual processors are required, multiplexing work to available processors is employed. This introduces a form of latency incurred by operating system overhead. Further complications arise when bandwidth creates bottlenecking of work units. G.E. Blelloch (1989) showed how to add parallel prefix operations (scans) to an extended PRAM model which uses unit step, not time operations. This paper shows how the Psi( psi ) calculus can be used to group work units, i.e. pipelining the work units, so that multiplexing is not required. The authors instead pipeline work units to processors and show how the number of processors need not be equivalent to the number of data components. Partitioning array data structures and pipelining groups of partitions to processors can minimize latency and bottlenecking on distributed message passing multiprocessing architectures.>

International audience