Emerging applications in multi-media and the Human Genome Project require storage and searching of large databases of strings - a task for which parallelism seems the only hope. In this paper, we consider the parallel...
详细信息
Emerging applications in multi-media and the Human Genome Project require storage and searching of large databases of strings - a task for which parallelism seems the only hope. In this paper, we consider the parallelism in some of the fundamental problems in compressing strings and in matching large dictionaries of patterns against texts. We present the first work-optimal algorithms for these well-studied problems including the classical dictionary matching problem, optimal compression with a static dictionary and the universal data compression with dynamic dictionary of Lempel and Ziv. All our algorithms are randomized and they are of the Las Vegas type. Furthermore, they are fast, working in time logarithmic in the input size. Additionally, our algorithms seem suitable for a distributed implementation.
We consider the problem of finding in parallel the connected components of an undirected graph when the computation is asynchronous. An algorithm is presented that uses a linear number of processes and time complexity...
详细信息
ISBN:
(纸本)089791483X
We consider the problem of finding in parallel the connected components of an undirected graph when the computation is asynchronous. An algorithm is presented that uses a linear number of processes and time complexity O(log n) in the APRAM [CZ89] model. In addition, the algorithm computes a spanning forest for the graph. Previously published algorithms, even those running on a concurrent CRCW PRAM, are more complicated than the one we present. Moreover, the proof techniques are sufficiently robust for application to other models of asynchronous parallel computation.
In this paper, we present a dynamic load-balancing algorithm for parallel digital logic simulation making use of reinforcement learning We first introduce two dynamic load-balancing algorithms oriented towards balanci...
详细信息
ISBN:
(纸本)9781450300797
In this paper, we present a dynamic load-balancing algorithm for parallel digital logic simulation making use of reinforcement learning We first introduce two dynamic load-balancing algorithms oriented towards balancing the computational and communication load respectively and then utilize reinforcement learning to create an algorithm which is a combination of the first two algorithms In addition, the algorithm determines the value of two important parameters the number of processors which participate in the algorithm and the load which is exchanged during its execution. We investigate the algorithms on gate level simulations of several open source VLSI circuits
We present parallelalgorithms for several graph and geometric problems, including transitive closure and topological sorting in planar st-graphs, preprocessing planar subdivisions for point location queries, and cons...
详细信息
An effective method in practice to compute quality Delaunay triangulations is to apply parallel refinements that insert Steiner points whose prestars in the triangulation do not overlap. We show that these algorithms ...
详细信息
ISBN:
(纸本)9781581138405
An effective method in practice to compute quality Delaunay triangulations is to apply parallel refinements that insert Steiner points whose prestars in the triangulation do not overlap. We show that these algorithms can be implemented in O(log m) time using m processors, where m is the output size. To our knowledge, this is the first such analysis.
The idea of dynamic programming (DP), proposed by Bellman in the 1950s, is one of the most important algorithmic techniques. However, in parallel, many fundamental and sequentially simple problems become more challeng...
详细信息
ISBN:
(纸本)9798400704161
The idea of dynamic programming (DP), proposed by Bellman in the 1950s, is one of the most important algorithmic techniques. However, in parallel, many fundamental and sequentially simple problems become more challenging, and open to a (nearly) work-efficient solution (i.e., the work is off by at most a polylogarithmic factor over the best sequential solution). In fact, sequential DP algorithms employ many advanced optimizations such as decision monotonicity or special data structures, and achieve better work than straightforward solutions. Many such optimizations are inherently sequential, which creates extra challenges for a parallel algorithm to achieve the same work bound. The goal of this paper is to achieve (nearly) work-efficient parallel DP algorithms by parallelizing classic, highly-optimized and practical sequential algorithms. We show a general framework called the Cordon Algorithm for parallel DP algorithms, and use it to solve several classic problems. Our selection of problems includes Longest Increasing Subsequence (LIS), sparse Longest Common Subsequence (LCS), convex/concave generalized Least Weight Subsequence (LWS), Optimal Alphabetic Tree (OAT), and more. We show how the Cordon Algorithm can be used to achieve the same level of optimization as the sequential algorithms, and achieve good parallelism. Many of our algorithms are conceptually simple, and we show some experimental results as proofs-of-concept.
Hydra PPS is a collection of annotations, classes, a run-time, and a compiler designed to provide Java programmers with a fairly simple method of producing programs for Symmetric Multiprocessing (SMP) architectures. T...
详细信息
ISBN:
(纸本)1595934529
Hydra PPS is a collection of annotations, classes, a run-time, and a compiler designed to provide Java programmers with a fairly simple method of producing programs for Symmetric Multiprocessing (SMP) architectures. This paper introduces the basics of this new system including the basic constructs for this new programming language and the relationship between the Java VM, the compiler, the runtime, and the parallel program. Hydra will exploit parallelism when the underlying architecture supports it and will run as normal sequential Java program when the architecture does not have support for parallelism. parallelism is expressed through events in Hydra, it is easy to use, and programs run efficiently on parallelarchitectures.
In this paper, we study parallelalgorithms for private-cache chip multiprocessors (CMPs), focusing on methods for foundational problems that are scalable with the number of cores. By focusing on private-cache CMPs, w...
详细信息
ISBN:
(纸本)9781595939739
In this paper, we study parallelalgorithms for private-cache chip multiprocessors (CMPs), focusing on methods for foundational problems that are scalable with the number of cores. By focusing on private-cache CMPs, we show that we can design efficient algorithms that need no additional assumptions about the way cores are interconnected, for we assume that all inter-processor communication occurs through the memory hierarchy. We study several fundamental problems, including prefix sums, selection, and sorting, which often form the building blocks of other parallelalgorithms. Indeed, we present two sorting algorithms, a distribution sort and a mergesort. Our algorithms are asymptotically optimal in terms of parallel cache accesses and space complexity under reasonable assumptions about the relationships between the number of processors, the size of memory, and the size of cache blocks. In addition, we study sorting lower bounds in a computational model, which we call the parallel external-memory (PEM) model, that formalizes the essential properties of our algorithms for private-cache CMPs.
We present an algorithm that computers a minimum spanning tree (MST) of an undirected weighted graph G = (V, E) of n = |V| vertices and m = |E| edges on an EREW PRAM in O(log3/2 n) time using n + m processors. This re...
详细信息
ISBN:
(纸本)089791483X
We present an algorithm that computers a minimum spanning tree (MST) of an undirected weighted graph G = (V, E) of n = |V| vertices and m = |E| edges on an EREW PRAM in O(log3/2 n) time using n + m processors. This represents a substantial improvement in the running time over the previous results for this problem using at the same time the weakest of the PRAM models. It also implies the existence of algorithms having the same complexity bounds for the EREW PRAM, for connectivity, ear decomposition, biconnectivity, strong orientation, st-numbering and Euler tours problems.
暂无评论