摘要:

In this short note a new recursive stride (RS) procedure is outlined for the parallel LU decomposition of a positive definite tridiagonal matrix of order n. The new strategy is shown to involve log2(n/2) steps using the fan-in procedure and is superior to recursive doubling [1].

ISSN:1063-7192    

DOI:10.1080/10637199708915614

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

We present a cost-optimal parallel algorithm for the maximum matching problem on bipartite permutation graphs on an EREW PRAM. Previously, Chen and Yesha have dealt with this problem. Their solution relies on Dekel and Sahni's matching algorithm for convex bipartite graphs, which runs in O(log2n) time usingO(n) processors. Given a permutation diagram, our algorithm runs in O(logn) time by using O(n/logn) processors. Our method starts with an easily understood greedy algorithm. We define a nontrivial binary operation which is associative and equivalent to the greedy algorithm. Thus parallel prefix can be applied to the problem.

ISSN:1063-7192    

DOI:10.1080/10637199708915615

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

One of the most promising areas of research is the area of automatic parallelization of sequential algorithms, where the primary objective is the execution of the algorithm in optimal parallel lime. For this purpose, methods of detecting and exploiting all inherent parallelism must be devised. Once optimal execution time is ensured, other prerequisites, e.g., the minimization of the number of processing elements (in the case of systolic arrays) or the minimization of the communication overhead (in the case of distributed memory architectures), should be accomplished too. In this paper we study the automatic parallelization of DO(FOR)-loops; we propose an algorithm that partitions the index space into distinct dependence chains and assigns them to different processing elements. We estimate that our method is always optimal in time and, for a specific subclass of nested DO(FOR)-loops, is also optimal in the number of systolic cells.

ISSN:1063-7192    

DOI:10.1080/10637199708915616

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

This paper actually shows the magic of applying the interlocking property to 3D algorithms and 2D systolic arrays. The interlocking property along with the determinant presenting the characteristics of the linear transformations are results introduced by the authors in [1,2].

ISSN:1063-7192    

DOI:10.1080/10637199708915617

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

Computer vision tasks are traditionally partitioned into three distinct categories, depending on the types of objects they operate on. It is fairly standard to refer to the computational tasks involving two-dimensional arrays of pixels as low-level tasks. An important low-level task is that of texture discrimination. Our main contribution is to present a parallel implementation of a texture discrimination technique called the Covering-Blanket method on a mesh-based platform, the DAP. The crux of the method is to map estimates of the local fractal dimension of an image lo a feature space that is useful in separating textures. Our results show that the DAP is particularly well suited to handle texture discrimination via the Covering-Blanket method. Our results compare favorably with the best running times of many commercially-available architectures.

ISSN:1063-7192    

DOI:10.1080/10637199708915618

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

Flame sheet problems are on the natural route to the numerical solution of detailed chemistry, laminar diffusion flames, which, in turn, are important in many engineering applications. In order to model the flame structure more accurately, we use the vorticity-velocity formulation of the fluid flow equations instead of the more traditional stream function-vorticity approach. The numerical solution of the resulting nonlinear coupled elliptic partial differential equations involves damped Newton iterations, adaptive grid procedures, and multigrid methods. We focus on nonlinear damped Newton multigrid, using either one way or correction schemes. Results on serial and parallel processors are presented.

ISSN:1063-7192    

DOI:10.1080/10637199708915619

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

We propose a simple and elegant distributed self-stabilizing algorithm to find the center of an arbitrary tree graph. The algorithm is uniform over all nodes of the tree. We prove the self-stabilization of the distributed algorithm using mathematical induction; we did not need to design a bounded function on the global state (which is customary for proving correctness of self-stabilizing algorithms).

ISSN:1063-7192    

DOI:10.1080/10637199708915620

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

In this paper, we investigate the problems of sorting integers by bucket sort and of computing minimal interval and circular are overlap representations, and give several optimal algorithms. We show that, givennlinearly ranged integers, sorting can be done

ISSN:1063-7192    

DOI:10.1080/10637199708915621

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

In this paper, we combine the techniques of approximation, parallelism, and randomization to solve the traveling salesman problem, one of the most celebrated problems in computer science. We show that there is an EREW PRAM algorithmA1such thatA1(l) ≤ 2 OPT(l) for all TSP instancesl, whereA1(l) is the length of the tour produced byA1, and OPT(l) is the length of an optimum tour. The algorithm has time complexityO(log2 n), and usesO(n2) processors. There is a similar CREW PRAM algorithmA2that usesO(n2/log2 n) processors. Furthermore, there is a Monte Carlo CREW PRAM algorithmA3which, for all TSP instancesl, finds a traveling salesman lour such thatA3(l) ≤ 1.5OPT(l) with probability at least 1 − (1/2k), wherekis any large integer. The randomized algorithm has time complexityO(log2 n), and usesO(n5.5L) processors, whereLis the length of the interval which contains all distances inl. We also show that there is a Las Vegas CREW PRAM algorithmA4which, for all TSP instancesl, produces a traveling salesman tour such thatA4(l) ≤ 1.5 OPT(l), with expected time complexityO(log2 n), and usingO(n5.5L) processors. Therefore, it is possible to accurately solve the TSP very fast with high probability by using a reasonable amount of resources.

ISSN:1063-7192    

DOI:10.1080/10637199708915622

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor

摘要:

This paper describes transputer implementation of systolic array designs of parallel algorithms for low-level digital image processing, in particular we consider the gradient operator. To achieve high performance, a new systolic array in which all the cells in a double pipeline are interconnected to a system bus. The transputer implementation of the design, is discussed. Comments and conclusions related to the implementation of the systolic array on transputer networks are provided in the performance section. It is then shown that the systolic array design can be extended to handle the Prewitt and Sobel operators and inverse gradient filter.

ISSN:1063-7192    

DOI:10.1080/10637199708915623

出版商:Taylor & Francis Group    

年代:1997

数据来源: Taylor