1. |
A PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH FIRST SEARCH |
|
Parallel Algorithms and Applications,
Volume 5,
Issue 3-4,
1995,
Page 161-164
ALAKK. DATTA,
RANJANK. SEN,
Preview
|
PDF (83KB)
|
|
摘要:
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
|
2. |
A RELIABLE SORTING ALGORITHM ON HYPERCUBE MULTICOMPUTERS |
|
Parallel Algorithms and Applications,
Volume 5,
Issue 3-4,
1995,
Page 165-186
YUH-SHYAN CHEN,
JANG-PING SHEU,
Preview
|
PDF (416KB)
|
|
摘要:
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
|
3. |
A COST-OPTIMAL EREW BREADTH-FIRST ALGORITHM FOR ORDERED TREES, WITH APPLICATIONS* |
|
Parallel Algorithms and Applications,
Volume 5,
Issue 3-4,
1995,
Page 187-197
RONG LIN,
STEPHAN OLARIU,
Preview
|
PDF (191KB)
|
|
摘要:
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
|
4. |
MODELING AND SIMULATION OF DYNAMIC LOAD BALANCING USING QUEUEING THEORY |
|
Parallel Algorithms and Applications,
Volume 5,
Issue 3-4,
1995,
Page 199-218
HERVÉ GUYENNET,
FRANÇOIS SPIES,
MICHEL TRÉHEL,
Preview
|
PDF (316KB)
|
|
摘要:
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
|
5. |
AGE METHOD WITH VARIABLE COEFFICIENTS FOR PARALLEL COMPUTING |
|
Parallel Algorithms and Applications,
Volume 5,
Issue 3-4,
1995,
Page 219-228
ZHANG BAOLIN,
LI WENZHI,
Preview
|
PDF (115KB)
|
|
摘要:
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
|
6. |
NEW PARALLEL STRATEGIES FOR BLOCK UPDATING THE QR DECOMPOSITION* |
|
Parallel Algorithms and Applications,
Volume 5,
Issue 3-4,
1995,
Page 229-239
ERRICOSJ. KONTOGHIORGHES,
Preview
|
PDF (179KB)
|
|
摘要:
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
|
7. |
A RECURRENCE-FREE VARIANT OF STRASSEN'S ALGORITHM ON HYPERCUBE* |
|
Parallel Algorithms and Applications,
Volume 5,
Issue 3-4,
1995,
Page 241-249
E. FRANCOMANO,
A.TORTORICI MACALUSO,
C. LODATO,
Preview
|
PDF (162KB)
|
|
摘要:
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
|
8. |
BOUNDARY-CONFORMING NUMERICAL GRID GENERATION ON PROCESSOR NETWORKS |
|
Parallel Algorithms and Applications,
Volume 5,
Issue 3-4,
1995,
Page 251-268
JÖRG-UDO ADEN,
NORBERT KÖCKLER,
Preview
|
PDF (284KB)
|
|
摘要:
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
|
9. |
THE RANDOM SEARCH GLOBAL OPTIMIZATION METHOD FOR PARALLEL COMPUTERS |
|
Parallel Algorithms and Applications,
Volume 5,
Issue 3-4,
1995,
Page 269-282
K. DEEP,
D. J. EVANS,
Preview
|
PDF (202KB)
|
|
摘要:
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
|
10. |
AN EXPERIMENT IN IMAGE RESTORATION USING TRANSPUTER NETWORKS |
|
Parallel Algorithms and Applications,
Volume 5,
Issue 3-4,
1995,
Page 283-292
F. ZAMA,
E. LOLI PICCOLOMINI,
Preview
|
PDF (146KB)
|
|
摘要:
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
|