摘要:

Ordering clones from a genomic library into physical maps of whole chromosomes presents a pivotal computational problem in genetics. Previous research has shown the physical mapping problem to be isomorphic to the NP-completeOptimal Linear Arrangement(OLA) problem for which no polynomial-time algorithm for determining the optimal solution is known. Serial implementations of stochastic global optimization techniques such as simulated annealing yielded very good results but proved computationally intensive. The design, analysis and implementation of coarse-grained parallel MIMD algorithms for simulated annealing on the Intel iPSC/860 hypercube is presented. Data decomposition and control decomposition strategies based on Markov chain decomposition, perturbation methods and problem-specific annealing heuristics are proposed and applied to the physical mapping problem. A suite of parallel algorithms are implemented on an 8-node Intel iPSC/860 hypercube, exploiting the nearest-neighbor communication pattern on the Boolean hypercube topology. Convergence, speedup and scalability characteristics of the various parallel algorithms are analyzed and discussed. Results indicate a deterioration of performance when a single Markov chain of solution states is distributed across multiple processing elements in the Intel iPSC/860 hypercube.

ISSN:1063-7192    

DOI:10.1080/01495739708941423

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

In this paper we investigate the problem of constructing iterative methods for solving non-linear algebraic equations and systems of equations, corresponding to a parallel implementation on a multiprocessor system with no synchronization between co-operating processes.

ISSN:1063-7192    

DOI:10.1080/01495739708941424

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

This paper presents count-sort, a parallel algorithm for mesh-connected computers to sort integers where the range of inputs is known. A straightforward counting technique that has not been implemented previously in parallel sorting algorithms is presented. On a mesh-connected computer with N×N processors we are able to sort N integers in the range 1 sN in timewhere cN is very small. For practical values of N, the algorithm is extremely fast. Further, it is possible to expand the range by a factor k to 1 N so that the slowdown is less than k.

ISSN:1063-7192    

DOI:10.1080/01495739708941425

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

We experimentally analyze some properties of simulated annealing algorithms (SA) and genetic algorithms (GA) for mapping data to multicomputers. These properties include sensitiviiy to user parameters, fault tolerance capability, and applicability to different multicomputer topologies. Some user parameters are included in the objective function and are architecture- or problem-dependent parameters. The others are used in the GA and SA algorithms. The fault tolerance capability is demonstrated by mapping data to a multicomputer with some faulty processors. We assume a hypercube multicomputer architecture in most experiments. However, mapping to mesh, array, ring, tree, and star graph topologies is also demonstrated. The experimental results show that the GA and SA are insensitive to user parameters in wide ranges, completely fault tolerant, and unbiased towards particular multicomputer topologies. These properties of flexibility and general applicability, which are lacking in other heuristic algorithms, make the GA and SA attractive for automatic parallelization systems.

ISSN:1063-7192    

DOI:10.1080/01495739708941426

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

Initially, parallel algorithms were designed by parallelising the existing sequential algorithms for frequently occurring problems on available parallel architectures.

ISSN:1063-7192    

DOI:10.1080/01495739708941427

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

Given a set S ofnproper circular arcs, it is required to identify a largest cardinality subset K[S] of S each two of whose members intersect. This paper describes an optimal parallel algorithm to compute K[S]. The algorithm is not based on any previously known sequential solution, and is designed for the CREW PRAM model of computation. It uses 0(n/logn) processors and runs in O(logn) time. An interesting feature of the algorithm is that it transforms the computational geometric problem at hand, to a problem involving computations on 0-1 matrices, and then transforms the latter back into a ray shooting problem in computational geometry.

ISSN:1063-7192    

DOI:10.1080/01495739708941428

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

In this paper a factorisation of certain symmetric circulant banded linear systems proposed by Evans [Evans 1981] is described. It can be shown that a banded Toeplitz matrix can be factorised into the product of easily inverted cyclic matrices. By using this factorisation, a solution can be derived for such matrices.

ISSN:1063-7192    

DOI:10.1080/01495739708941429

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

In this paper, according to the asynchronous iteration model presented by G. M. Baudet [4] and D.P. Bertsekas [5], we propose an asynchronous monotone Newton iterative method for solving the nonlinear system of equations F(x) = 0 on a distributed computer, and prove its convergence.

ISSN:1063-7192    

DOI:10.1080/01495739708941430

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor