摘要:

We present a new parallel algorithm for finding a maximal matching of a graph. The time required by our algorithm isO(TD(n) logn) and the number of processors used isPD(n), whereTD(n) andPD(n) are the time and number of processors needed for a Depth First Search (DFS) of the graph.

ISSN:1063-7192    

DOI:10.1080/10637199508915482

出版商:Taylor & Francis Group    

年代:1995

数据来源: Taylor

摘要:

In this paper, we present an algorithm-based fault-tolerant technique, namely the median-splitting strategy, for designing a reliable sorting algorithm. Combining the median-splitting strategy with bitonic sorting algorithm, a reliable sorting algorithm is proposed on the hypercube multicomputers. By the strategies of duplicating data and rollback, the proposed algorithm can detect transient faults and automatically correct errors without any hardware modification. We also implement our algorithm on nCUBE/1 hypercube machines with 64 processors. The simulation results show that our sorting algorithm is reliable and cost-effective.

ISSN:1063-7192    

DOI:10.1080/10637199508915483

出版商:Taylor & Francis Group    

年代:1995

数据来源: Taylor

摘要:

Encoding the shape of a tree is a basic step in a number of algorithms in integrated circuit design, automated theorem proving, and game playing. We propose a simple cost-optimal encoding algorithm for ordered trees and show that our encoding can be used to obtain an optimal Breadth-First traversal of ordered trees. Specifically, with an n-node ordered tree as input our algorithms run in O(logn) time using O(n/logn) processors in the EREW-PRAM model of computation. We then show that the Breadth-First algorithm can be used to produce new encodings of binary and ordered trees.

ISSN:1063-7192    

DOI:10.1080/10637199508915484

出版商:Taylor & Francis Group    

年代:1995

数据来源: Taylor

摘要:

The aim of this article is to present an original modeling of dynamic load balancing, using qucueing theory, then to present a simulation method, using QNAP software and finally to show that results of the model and results of the simulation are identical. First we present six load balancing strategies we simulate using the QNAP software, and we study the basic parameters: the load, the number of nodes, the communication speed, and the overload rate. Then we realise a complete and original modeling of the “optimal” strategy. The values given by this method are reference values for other strategies. By comparing the results, we demonstrate the accuracy of our mathematical model and the precision of our simulation.

ISSN:1063-7192    

DOI:10.1080/10637199508915485

出版商:Taylor & Francis Group    

年代:1995

数据来源: Taylor

摘要:

The well-known AGE (Alternating Group Explicit) method is extended for solving the diffusion equation with variable coefficients and the unconditional stability of the AGE method is proved by the energy method in the discreteL2-norm.

ISSN:1063-7192    

DOI:10.1080/10637199508915486

出版商:Taylor & Francis Group    

年代:1995

数据来源: Taylor

摘要:

Parallel strategies are proposed for updating the QR decomposition of anmxnmatrix after addingkrows (k≫n). These strategies are based on Givens rotations and are found to complete the updating in fewer steps by comparison to a recently published algorithm. An efficient adaptation of the first parallel strategy to compute the QR decomposition of structured banded matrices is also discussed in detail.

ISSN:1063-7192    

DOI:10.1080/10637199508915487

出版商:Taylor & Francis Group    

年代:1995

数据来源: Taylor

摘要:

In this paper a non-recursive Strassen's matrix multiplication algorithm is presented. This new algorithm is suitable to run on parallel environments. Two computational schemes have been worked out exploiting different parallel approaches on hypercube architecture. A comparative analysis is reported.

ISSN:1063-7192    

DOI:10.1080/10637199508915488

出版商:Taylor & Francis Group    

年代:1995

数据来源: Taylor

摘要:

We show that numerical grid generation for arbitrary regions involving transformation methods can be efficiently implemented on appropriate processor networks.

ISSN:1063-7192    

DOI:10.1080/10637199508915489

出版商:Taylor & Francis Group    

年代:1995

数据来源: Taylor

摘要:

In this paper we present a strategy for random search global optimization for parallel computers. The implementation on a shared memory parallel computer is coded in FORTRAN and the implementation on a distributed memory multiprocessor system is coded inCusing the processor farming technique. Results on known test examples confirm the conclusions.

ISSN:1063-7192    

DOI:10.1080/10637199508915490

出版商:Taylor & Francis Group    

年代:1995

数据来源: Taylor

摘要:

The problem of image restoration, with a blurring function linear, space-variant and nonseparable, has been solved on a transputer network, using primitives of Parasoft express environment and A.CS.Arnia Library. A domain decomposition strategy has been introduced to split the problem among the processors. Some interesting computational results are reported.

ISSN:1063-7192    

DOI:10.1080/10637199508915491

出版商:Taylor & Francis Group    

年代:1995

数据来源: Taylor