摘要:

This paper presents a new approach toParallel Computational Geometryby using networks ofanalogcomponents (referred to asanalog networksoranalog circuits). Massively parallel analog circuits with large numbers of processing elements exist in hardware and have proven to be efficient architectures for important problems (e.g. constructing an associative memory). In this paper it is demonstrated how Parallel Computational Geometry problems can be solved by exploiting the features of such analog parallel architectures. Using massively parallel analog circuits requires a radically different approach to geometric problem solving because (1) time is continuous instead of the standard discretized stepwise parallel processing, and (2) geometric data is represented by analog components (e.g. voltages at certain positions of the circuit) instead of the usual digital representation We presentanalogparallel algorithms for the following geometrical problems: minimum weight triangularization of planar point sets or of polygons with holes, minimum rectangular partitions of rectilinear polygons with holes, finding the smallest ϵ so that two given point sets are ϵ-congruent via translation, and determining for a given line segment set a subset of non-intersecting line segments of maximum total length. The paper also includes experimental results which demonstrate that, in practice, our analog parallel circuits produce high quality outputs.

ISSN:1063-7192    

DOI:10.1080/10637199508915472

出版商:Taylor & Francis Group    

年代:1995

数据来源: Taylor

摘要:

In this paper, we address the problem of finding a maximum matching for a convex bipartite graph on a mesh-connected computer (MCC). We shall show that this can be done in optimal time on MCC by designing the efficient merge and division schemes in bottom-up and top-down approach respectively.

ISSN:1063-7192    

DOI:10.1080/10637199508915473

出版商:Taylor & Francis Group    

年代:1995

数据来源: Taylor

摘要:

Genetic algorithms are highly parallel, adaptive search method based on the processes of Darwinian evolution. This paper combines genetic algorithms with simulated annealing algorithms to a new kind of random search algorithms which is called genetic evolution algorithms. We give some conditions which guarantee random search algorithms to converge to the global optima set with probability 1 for solving optimization problems and analyze the convergence of genetic evolution algorithms by using Markov chain theory.

ISSN:1063-7192    

DOI:10.1080/10637199508915474

出版商:Taylor & Francis Group    

年代:1995

数据来源: Taylor

摘要:

This paper considers the Jordan and Huard diagonalization methods for solving linear systems on an MIMD computer. We introduce two parallel algorithms for this class of methods and study their complexity taking into consideration the communication cost. Next, in an attempt to reduce the communication load we introduce their corresponding block versions. Finally, we derive new complexity results and compare their asymptotic performances.

ISSN:1063-7192    

DOI:10.1080/10637199508915475

出版商:Taylor & Francis Group    

年代:1995

数据来源: Taylor

摘要:

In this paper the parallel implementation of a Backpropagation-Cauchy Neural Network is described. The results confirm the suitability of the learning strategy to parallel machines.

ISSN:1063-7192    

DOI:10.1080/10637199508915476

出版商:Taylor & Francis Group    

年代:1995

数据来源: Taylor

摘要:

This paper describes the performance analysis of the local area network (LAN) of workstations for distributed computing applications. Several application programs represented in a task graph format are scheduled by the user workstation (master) for parallel execution in the idle or lightly loaded processors (slaves) in LAN. The partial results are collected by the master station to synchronize the operation of slave nodes. The system performance is characterized by the network speedup considering scheduling time, network load and size, communication time, TCP/IP communication overhead, task execution, and synchronization time. The sequential and parallel execution times and the performance degradation factors were measured during the implementation for various network loads. The measurement values and theoretical results have shown that the system performance is degraded mostly by the TCP/IP overhead (0.2 s), the network size, and the network load.

ISSN:1063-7192    

DOI:10.1080/10637199508915477

出版商:Taylor & Francis Group    

年代:1995

数据来源: Taylor

摘要:

The Hessenberg-Schur method is one of the most efficient and stable algorithms for solving linear matrix equations. When it is applied to the Sylvester equation,AX+X B=C, matrixAis reduced to the Hessenberg form and matrixBto the real Schur for using orthogonal similarity transformations. In this paper we present a parallel algorithm for solving the Sylvester matrix equation whenAandBare in the above-mentioned forms on a Distributed Memory Multiprocessor. Both a complexity analysis and an experimental study of the new algorithm are also presented.

ISSN:1063-7192    

DOI:10.1080/10637199508915478

出版商:Taylor & Francis Group    

年代:1995

数据来源: Taylor

摘要:

Parallel algorithms are developed for the numerical solution of second-order hyperbolic partial differential equations using (M,K) Padé approximants withM ≠ K. A linear one-dimensional wave equation is solved using the algorithms and comparisons are made with results from the literature confirming the accuracy of the algorithms.

ISSN:1063-7192    

DOI:10.1080/10637199508915479

出版商:Taylor & Francis Group    

年代:1995

数据来源: Taylor

摘要:

This paper deals with parallel checking of passive constraints in object-oriented databases. It presents a parallel algorithm for constraint checking based on a master-slave technique and discusses its implementation on a parallel object-oriented database system. The system is named PRACTIC and is based on class concurrency. Passive constraints, unlike active database rules, are independent and can be executed using AND-parallelism. Simulation shows that the proposed algorithm offers considerable speedup, which mainly depends on the number of constraints and the total constraint execution time, while it is only slightly affected from the distribution of constraints and the constraint scheduling policy. Finally, it is explained how the PRACTIC system enhances the algorithm's performance using features, like nested query parallelism and constraint overlapping.

ISSN:1063-7192    

DOI:10.1080/10637199508915480

出版商:Taylor & Francis Group    

年代:1995

数据来源: Taylor

摘要:

When distributing the object data for rendering in a MIMD network all erroneous data must be clipped against each of the subdivisions of the image space which have been allocated to the individual processors. This process of clipping entails an added computational cost to that of the actual rendering algorithm. This paper looks at the effect of clipping on rendering in a parallel environment and determines a way of minimising the computational cost of that clipping when using a Transputer network.

ISSN:1063-7192    

DOI:10.1080/10637199508915481

出版商:Taylor & Francis Group    

年代:1995

数据来源: Taylor