We present adaptive parallel algorithms for b — matchings in trees. The algorithms are designed using the exclusive-read exclusive-write parallel random-access machine (EREW PRAM) model of parallel computation. For a...
详细信息
We propose a new framework for designing efficient parallel algorithms on series parallel graphs. Recently, a new approach for recognizing series parallel graphs was presented by Eppstein. Eppstein explored characteri...
详细信息
Finding the all-pairs shortest-paths on a large graph is a fundamental problem in many practical applications such as bioinformatics, internet node traffic and network routing. In this paper, we present the designs of...
详细信息
parallel algorithm design is generally hard. parallel program verification is even harder. We take an ex-ample from the maximum subarray problem and and show those two problems of design and verification. The best kno...
详细信息
In this talk we present the intrinsic connection between modelling the suitable data type by algebraic specification and the correct and efficient implementation of high-speed parallel algorithms in hardware or softwa...
详细信息
In this talk we present the intrinsic connection between modelling the suitable data type by algebraic specification and the correct and efficient implementation of high-speed parallel algorithms in hardware or software. The design tool IDEAS developed at the author's institution representing the first such instrument for automatic parallel algorithm generation is described.
In this work we describe three sequential algorithms and their parallel counterparts for solving nonlinear systems, when the Jacobian matrix is symmetric and positive definite. This case appears frequently in unconstr...
详细信息
In this paper, we present efficient parallel algorithms for finding a minimum weighted connected dominating set, a minimum weighted Steiner tree for a distance-hereditary graph which take O(log n) time using O(n+m) pr...
详细信息
In this paper, we present efficient parallel algorithms for finding a minimum weighted connected dominating set, a minimum weighted Steiner tree for a distance-hereditary graph which take O(log n) time using O(n+m) processors on a CRCW PRAM, where n and m are the number of vertices and edges of a given graph, respectively. We also find a maximum weighted clique of a distance-hereditary graph in O(log2 n) time using O(n+m) processors on a CREW PRAM.
Lock-free shared data structures in the setting of distributed computing have received a fair amount of attention. Major motivations of lock-free data structures include increasing fault tolerance of a (possibly heter...
详细信息
ISBN:
(纸本)3540241299
Lock-free shared data structures in the setting of distributed computing have received a fair amount of attention. Major motivations of lock-free data structures include increasing fault tolerance of a (possibly heterogeneous) system and alleviating the problems associated with critical sections such as priority inversion and deadlock. For parallel computers with tightly-coupled processors and shared memory, these issues are no longer major concerns. While many of the results are applicable especially when the model used is shared memory multiprocessors, no prior studies have considered improving the performance of a parallel implementation by way of lock-free programming. As a matter of fact, often times in practice lock-free data structures in a distributed setting do not perform as well as those that use locks. As the data structures and algorithms for parallel computing are often drastically different from those in distributed computing, it is possible that lock-free programs perform better. In this paper we compare the similarity and difference of lock-free programming in both distributed and parallel computing environments and explore the possibility of adapting lock-free programming to parallel computing to improve performance. Lock-free programming also provides a new way of simulating PRAM and asynchronous PRAM algorithms on current parallel machines.
A two vehicle navigator on a discrete space is analyzed. The concept of linking time maps as source to optimal path planning is discussed. The rules for constructing these maps are given in a cellular automata mode. T...
详细信息
A two vehicle navigator on a discrete space is analyzed. The concept of linking time maps as source to optimal path planning is discussed. The rules for constructing these maps are given in a cellular automata mode. The implementation of these rules on a parallel computer is presented.< >
In this paper, the problem, of obtaining an optimal layout for the single row routing problem in narrow streets (maximum number of tracks in either street is at most 2) on parallel computers is studied. An O(log n) ti...
详细信息
In this paper, the problem, of obtaining an optimal layout for the single row routing problem in narrow streets (maximum number of tracks in either street is at most 2) on parallel computers is studied. An O(log n) time parallel algorithm with O(n/logn) processors on a CREW PRAM and an O(log/sup 2/n) time cost-optimal algorithm on a tree machine is obtained.
暂无评论