摘要:

The serial model for self-stabilizing distributed algorithms assumes that the reading of the states of the neighbors and the updating of its own state are grouped together into one atomic operation (indivisible execution step) the model also assumes that each node can simultaneously see the current states of all its neighbors and that only one node executes an atomic step at a time. Because of the popularity of the serial model and the relative ease of its use in designing and proving correctness for new self-stabilizing algorithms, a large number of such algorithms have appeared in the literature. This serial model makes stronger assumptions about the run time environment than those normally provided by a real time message passing distributed system. On the other hand designing and proving correctness for self-stabilizing algorithms in a distributed model are relatively difficult. Thus, in order to make use of the self-stabilizing algorithms designed for a serial model, it is necessary to design lower level self-stabilizing protocols such that an algorithm developed for a serial model can be run in a distributed environment. Our purpose in this paper is to propose a new protocol that can be used to run a serial model self-stabilizing algorithm in a distributed environment that accepts as atomic operations only send a message, receive a message an update a state. Unlike the scheme in M. Mizuno and H. Kakugawa. A timestamp based transformation or self-stabilizing programs for distributed computing environments. In Proceedings of the lOih International Workshop on Distributed Algorithms (WDAG'S), Vol. 304-321, 1996, our protocol does not use lime-stamps (which are unbounded integers) our algorithm uses only bounded integers (actually, the integers can assume values only 0, 1, 2 and 3)and can be easily implemented.

ISSN:1063-7192    

DOI:10.1080/10637199808947375

出版商:Taylor & Francis Group    

年代:1999

数据来源: Taylor

摘要:

In this paper we give a convergence result for parallel chaotic synchronous algorithms associated with nonexpansive linear systems which are not necessarily contractive. This result allows us to apply these algorithms to flnite homogenous Markov chains and to consistent singular linear systems solved by parallel two-stage methods.

ISSN:1063-7192    

DOI:10.1080/10637199808947376

出版商:Taylor & Francis Group    

年代:1999

数据来源: Taylor

摘要:

This paper deals with a parallelization of the two-sided Jacobi algorithm for computation of Singular Value Decomposition (SVD) on a computer withpprocessors, which are organized into a two-dimensional √p× √pmesh configuration. This work represents a continuation of our paper (Part I, to appear inJ. Parallel Algorithms and Applications), which described a parallelization approach by columns and efficient ordering strategies for the hypercube and ring topologies.

ISSN:1063-7192    

DOI:10.1080/10637199808947377

出版商:Taylor & Francis Group    

年代:1999

数据来源: Taylor

摘要:

The Lanczos algorithm is one of the principal algorithms for the computation of a few of the extreme eigenvalues and their corresponding eigenvectors of very large, sparse, symmetric matrices and is currently the subject of intense research. In this paper two explicit restart techniques for the algorithm are proposed and their suitability for implementation in two different parallel environments is explored. Both techniques adopt a deflation approach in which exactly one eigenpair at a time is computed. Thus,peigenpairs are computed using exactly p applications of the chosen Lanczos method. Newly generated Lanczos vectors are orthogona-lized with respect to all previously converged eigenvectors. Each of the techniques has been embedded in a version of the Lanczos algorithm which incorporates full reorthogonalization of the Lanczos vectors as well as a new convergence monitoring routine. Both of the modified Lanczos algorithms have been implemented in a distributed memory SIMD environment and in a shared memory MIMD environment. The execution time efficiency of the two algorithms in each environment for the solution of a variety of matrices selected from the Harwell-Boeing collection of sparse matrices is presented and their performances are compared with those of Sorensen's implicit state-of-the-art routine taken from the ARPACK library. The experiments show that, in an environment in which matrix-vector products may be executedveryefficiently, the explicit methods often significantly outperform the implicit method. This result points to the desirability of selecting implementations of algorithms built (as far as possible) from operations which may be efficiently performed in the given parallel environment.

ISSN:1063-7192    

DOI:10.1080/10637199808947378

出版商:Taylor & Francis Group    

年代:1999

数据来源: Taylor

摘要:

In this paper we present more evidence to the viability of the hyperslar (Journal of Parallel and Distributed Computing, 48(2), 1998, 175-199) as a potential interconnection network for large-scale multiprocessor systems. An efficient framework for developing parallel algorithms on the hyperslar is presented and evaluated. This unified flamework can be used to implement a wide class of parallel algorithms in the hyperslar in parlicular and in the class of product networks in general. The proposed algorithms outperform their mesh and hypercube counterparts in terms of communication overhead.

ISSN:1063-7192    

DOI:10.1080/10637199808947379

出版商:Taylor & Francis Group    

年代:1999

数据来源: Taylor