We present a new parallel algorithm for computing a maximum cardinality matching in a bipartite graph suitable for distributed memory computers. The presented algorithm is based on the PUSH-RELABEL. algorithm which is...
详细信息
We present a new parallel algorithm for computing a maximum cardinality matching in a bipartite graph suitable for distributed memory computers. The presented algorithm is based on the PUSH-RELABEL. algorithm which is known to be one of the fastest algorithms for the bipartite matching problem. Previous attempts at developing parallel implementations of it have focused on shared memory computers using only a limited number of processors. We first present a straightforward adaptation of these shared memory algorithms to distributed memory computers. However, this is not a viable approach as it requires too much communication. We then develop our new algorithm by modifying the previous approach through a sequence of steps with the main goal being to reduce the amount of communication and to increase load balance. The first goal is achieved by changing the algorithm so that many push and relabel operations can be performed locally between communication rounds and also by selecting augmenting paths that cross processor boundaries infrequently. To achieve good load balance, we limit the speed at which global relabelings traverse the graph. In several experiments on a large number of instances, we study weak and strong scalability of our algorithm using up to 128 processors. The algorithm can also be used to find epsilon-approximate matchings quickly. (C) 2011 Elsevier B.V. All rights reserved.
In this paper we design and analyse parallel algorithms with the goal to get exact bounds on their speed-ups on real machines. For this purpose we employ the BSP model [3] which is an extension of Valiant's BSP mo...
详细信息
ISBN:
(纸本)0818672552
In this paper we design and analyse parallel algorithms with the goal to get exact bounds on their speed-ups on real machines. For this purpose we employ the BSP model [3] which is an extension of Valiant's BSP model [13] and rewards blockwise communication. Further we use Valiant's notion of c-optimality. Intuitively a c-optimal parallel algorithm for p processors tends to speed-up p/c, where the communication time is asymptotically smaller than the computation time. We consider a basic problem in Image Processing, Connected Component Labeling for two and three dimensional images. Our algorithms are randomized and 2-optimal with high probability for a wide range of BSP parameters where the range becomes larger with growing input sizes. Our algorithms improve on previous results as they either need an asymptotically smaller amount of data to be communicated or fewer communication rounds. We further report on implementation work and experiments.
The Lovasz Local Lemma (LLL) is a cornerstone principle in the probabilistic method of combinatorics, and a seminal algorithm of Moser & Tardos (2010) provides an efficient randomized algorithm to implement it. Th...
详细信息
ISBN:
(纸本)9781611974782
The Lovasz Local Lemma (LLL) is a cornerstone principle in the probabilistic method of combinatorics, and a seminal algorithm of Moser & Tardos (2010) provides an efficient randomized algorithm to implement it. This algorithm can be parallelized to give an algorithm that uses polynomially many processors and runs in O(log(3) n) time, stemming from O(log n) adaptive computations of a maximal independent set (MIS). Chung et al. (2014) developed faster local and parallel algorithms, potentially running in time O(log(2) n), but these algorithms work under significantly more stringent conditions than the LLL. We give a new parallel algorithm that works under essentially the same conditions as the original algorithm of Moser & Tardos but uses only a single MIS computation, thus running in O(log(2) n) time. This conceptually new algorithm also gives a clean combinatorial description of a satisfying assignment which might be of independent interest. Our techniques extend to the deterministic LLL algorithm given by Chandrasekaran et al. (2013) leading to an NC-algorithm running in time O(log(2) n) as well. We also provide improved bounds on the runtimes of the sequential and parallel resampling-based algorithms originally developed by Moser & Tardos. Our bounds extend to any problem instance in which the tighter Shearer LLL criterion is satisfied. We also improve on the analysis of Kolipaka & Szegedy (2011) to give tighter concentration results.
Mean-payoff games (MPGs) have many applications, especially in the synthesis, analysis and verification of computer systems. Because of the size of these systems, there is a need to solve very large MPGs. Existing alg...
详细信息
ISBN:
(纸本)9783642041273
Mean-payoff games (MPGs) have many applications, especially in the synthesis, analysis and verification of computer systems. Because of the size of these systems, there is a need to solve very large MPGs. Existing algorithms for solving MPGs are sequential, hence limited by the power of a single computer. In this paper, we propose several parallel algorithms based on the sequential ones. We also evaluate and compare the parallel algorithms experimentally.
Let k be a positive integer, a subset Q of the set of vertices of a graph G is k-dependent in G if each vertex of Q has no more than k neighbours in Q. We present a parallel algorithm which computes a maximal k-depend...
详细信息
ISBN:
(纸本)9783540549451
Let k be a positive integer, a subset Q of the set of vertices of a graph G is k-dependent in G if each vertex of Q has no more than k neighbours in Q. We present a parallel algorithm which computes a maximal k-dependent set in a graph on n nodes in time O(log 4 n) on an EREW PRAM with O(n2) processors. In this way, we establish the membership of the problem of constructing a maximal k-dependent set in the class NC. Our algorithm can be easily adapted to compute a maximal k-dependent set in a graph of bounded valence in time O(log* n) using only O(n) EREW PRAM processors. Let f be a positive integer function defined on the set V of vertices of a graph G. A subset F of the set of edges of G is said to be an f-matching if every vertex v is-an-element-of V is adjacent to at most f(v) edges in F. We present the first Nc algorithm for constructing a maximal f-matching. For a graph on n nodes and m edges the algorithm runs in time O(log4 n) and uses O(n + m) EREW PRAM processors. For graphs of constantly bounded valence, we can construct a maximal f-matching in O(log* n) time on an EREW PRAM with O(n) processors.
Vehicle routing problems involve the navigation of one or more vehicles through a network of locations. Locations have associated handling times as well as time windows during which they are active. The arcs connectin...
详细信息
ISBN:
(纸本)0818680679
Vehicle routing problems involve the navigation of one or more vehicles through a network of locations. Locations have associated handling times as well as time windows during which they are active. The arcs connecting locations have time costs associated with them. In this paper, we consider two different problems in single vehicle routing. The first is to find least time cost routes between all pairs of nodes in a network for navigating vehicles;we call this the all pairs routing problem. We show that there is an O(log2 n) time parallel algorithm using a polynomial number of processors for this problem on a CREW PRAM. We next consider the problem in which a vehicle services all locations in a network. Here, locations can be passed through at any time but only serviced during their time window. The general problem is NP-complete under even fairly stringent restrictions but polynomial algorithms have been developed for some special cases. In particular, when the network is a line, there is no time cost in servicing a location, and all time windows are unbounded at either their lower or upper end, O(n2) algorithms have been developed. We show that under the same conditions, we can reduce this problem to the all pairs routing problem and therefore obtain an O(log2 n) time parallel algorithm on a CREW PRAM.
The objective of this research is to develop parallel algorithms for enabling fast and scalable analysis of large-scale high-throughput sequencing datasets. Genome of an organism consists of one or more long DNA seque...
详细信息
The objective of this research is to develop parallel algorithms for enabling fast and scalable analysis of large-scale high-throughput sequencing datasets. Genome of an organism consists of one or more long DNA sequences called chromosomes, each a sequence of bases. Depending on the organism, the length of the genome can vary from several thousand bases to several billion bases. Genome sequencing, which involves deciphering the sequence of bases of the genome, is an important tool in genomics research. Sequencing instruments widely deployed today can only read short DNA sequences. However, these instruments can read up to several billion such sequences at a time, and are used to sequence a large number of randomly generated short fragments from the genome. These fragments are a few hundred bases long and are commonly referred to as âreadsâ. This work specifically tackles three problems associated with high-throughput sequencing short read datasets: (1) parallel read error correction for large-scale genomics datasets, (2) Partitioning of large-scale high-throughput sequencing datasets, and (3) parallel compression of large-scale genomics datasets.
Multi-scale modeling, the simulation of coupled physicalprocesses that occur on different temporal or spatialscales, is becoming an increasingly important area ofresearch in computational *** such problems can be comp...
详细信息
Multi-scale modeling, the simulation of coupled physicalprocesses that occur on different temporal or spatialscales, is becoming an increasingly important area ofresearch in computational *** such problems can be computationally intensive;however, because of the increasing availability of large computationalresources, their solution can be *** important multi-scale application is the numericalsimulation of *** combustion, three different physical processes governthe dynamics of the problem: fluid flow (which can beturbulent or laminar), chemical reactions, and heat transfer,with radiative heat transfer being a dominant *** objective of this thesis is to createefficient sequential and parallel algorithms andsoftware that improve accuracy and performance ofcombustion *** purpose of this work is to create clean, easy-to-usesoftware interfaces that can be readily used from both C/C++ and FORTRANapplications without significant changes to the original *** this thesis, we introduce two new software systems thatenable modeling of multi-scale phenomena in combustion applicationson single processor and distributed memory multiprocessorsystems and improve their accuracy and *** first system is called the Database On-Line forEfficient Function Approximation (DOLFA) for speeding upchemistry calculations in combustion applications.A second system, called Photon Monte Carlo (PMC),is used for solving the Radiative Transfer Equation (RTE)by calculating the radiative heat fluxes for the volume elementsof a computational *** PMC software system is capable of handling computational domains withcomplex enclosures and various radiation configurations.
The circuit value update problem is the problem of updating values in a representation of a combinational circuit when some of the inputs are changed. We assume for simplicity that each combinatorial element has bound...
详细信息
ISBN:
(纸本)9780897917179
The circuit value update problem is the problem of updating values in a representation of a combinational circuit when some of the inputs are changed. We assume for simplicity that each combinatorial element has bounded fan-in and fan-out and can be evaluated in constant time. This problem is easily solved on an ordinary serial computer in O(W + D) time, where W is the number of elements in the altered subcircuit and D is the subcircuit's embedded depth (its depth measured in the original circuit). In this paper, we show how to solve the circuit value update problem efficiently on a P-processor parallel computer. We give a straightforward synchronous, parallel algorithm that runs in O(W/P + D lg P) expected time. Our main contribution, however, is an optimistic, asynchronous, parallel algorithm that runs in O(W/P + D + lg W + lg P) expected time, where W and D are the size and embedded depth, respectively, of the 'volatile' subcircuit, the subcircuit of elements that have inputs which either change or glitch as a result of the update. To our knowledge, our analysis provides the first analytical bounds on the running time of an optimistic algorithm.
The longest common subsequence problem is to find a substring that is common to two given strings and is at least as long as any other such string. If m and n are the lengths of the two strings (m&len), we obtain ...
详细信息
The longest common subsequence problem is to find a substring that is common to two given strings and is at least as long as any other such string. If m and n are the lengths of the two strings (m&len), we obtain O(log m) time parallel algorithm with mn processors and an O(log2 n) time optimal parallel algorithm. Serial complexity on decision tree model is Θ(mn).
暂无评论