This paper presents a new compiler approach to minimizing the number of barriers executed in parallelized programs. A simple procedure is developed to reduce the complexity of barrier placement by eliminating certain ...
详细信息
This paper presents a new compiler approach to minimizing the number of barriers executed in parallelized programs. A simple procedure is developed to reduce the complexity of barrier placement by eliminating certain data dependences, without affecting optimality. An algorithm is presented which, provably, places the minimal number of barriers in perfect loop nests and in certain imperfect loop nest structures. This scheme is generalized to accept entire, well-structured control-flow programs containing arbitrary nesting of IF constructs, loops, and subroutines. It has been implemented in a prototype parallelizing compiler and applied to several well-known benchmarks where it has been shown to place significantly fewer synchronization points than existing techniques. Experiments indicate that on average the number of barriers executed is reduced by 70 percent and there is a three fold improvement in execution time when evaluated on a 32-processor SGI Origin 2000.
One of the earliest and still widely used methods for dense stereo correspondence is based on matching windows of pixels. The main difficulty of this method is choosing a window of appropriate size and shape. Small wi...
详细信息
One of the earliest and still widely used methods for dense stereo correspondence is based on matching windows of pixels. The main difficulty of this method is choosing a window of appropriate size and shape. Small windows may lack sufficient intensity variation for reliable matching, while large windows smooth out disparity discontinuities. We propose an algorithm to choose a window size and shape by optimizing over a large class of "compact" windows. The word compact is used informally to reflect the fact that the ratio of perimeter to area of our windows is small. We believe that this is the first area based method which efficiently constructs nonrectangular windows. Fast optimization over compact windows is achieved via the minimum ratio cycle algorithm for graphs. The algorithm has only a few parameters which are easy to fix.
The problem of finding a maximum induced matching is known to be NP-hard in general bipartite graphs. We strengthen this result by reducing the problem to some special classes of bipartite graphs such as bipartite gra...
详细信息
The problem of finding a maximum induced matching is known to be NP-hard in general bipartite graphs. We strengthen this result by reducing the problem to some special classes of bipartite graphs such as bipartite graphs with maximum degree 3 or C-4-free bipartite graphs. On the other hand, we describe a new polynomially solvable case for the problem in bipartite graphs which deals with a generalization of bi-complement reducible graphs. (C) 2002 Elsevier Science B.V. All rights reserved.
We present an algorithm that solves the all-pairs shortest-paths problem on a directed graph with n vertices and m arcs in time O(nm + n(2) logn), where the arcs are assigned real, possibly negative costs. Our algorit...
详细信息
We present an algorithm that solves the all-pairs shortest-paths problem on a directed graph with n vertices and m arcs in time O(nm + n(2) logn), where the arcs are assigned real, possibly negative costs. Our algorithm is new in the following respect. It computes the distance mu(v, w) between each pair v, w of vertices even in the presence of negative cycles, where mu(v, w) is defined as the infimum of the costs of all directed paths from v to w. (C) 2002 Elsevier Science B.V. All rights reserved.
We prove that MAXIMUM STABLE SET can be solved in polynomial time on two new subclasses of P-5-free graphs, extending some known polynomially solvable cases. (C) 2002 Elsevier Science B.V. All rights reserved.
We prove that MAXIMUM STABLE SET can be solved in polynomial time on two new subclasses of P-5-free graphs, extending some known polynomially solvable cases. (C) 2002 Elsevier Science B.V. All rights reserved.
We show that maximal matchings can be computed deterministically in O(log(4)n) rounds in the synchronous, message-passing model of computation. This is one of the very few cases known of a nontrivial graph structure, ...
详细信息
We show that maximal matchings can be computed deterministically in O(log(4)n) rounds in the synchronous, message-passing model of computation. This is one of the very few cases known of a nontrivial graph structure, and the only "classical" one, which can be computed distributively in polylogarithmic time without recourse to randomization.
We establish that the algorithmic complexity of the minimum spanning tree problem is equal to its decision-tree complexity. Specifically. we present a deterministic algorithm to find a minimum spanning tree of a graph...
详细信息
We establish that the algorithmic complexity of the minimum spanning tree problem is equal to its decision-tree complexity. Specifically. we present a deterministic algorithm to find a minimum spanning tree of a graph within vertices and m edges that runs in time O(T*(m, n)) where T* is the minimum number of edge-weight comparisons needed to determine the solution. The algorithm is quite simple and can be implemented on a pointer machine. Although our time bound is optimal, the exact function describing it is not known at present. The current best bounds known for T* are T*(m, n) = Omega(m) and T*(m, n) = O(m - alpha(m, n)), where alpha is a certain natural inverse of Ackermann's function, Even under the assumption that T- is superlinear, we show that if the input graph is selected front G(n,m), our algorithm runs in linear time with high probability, regardless of n, in, or the permutation of edge weights. The analysis uses a new martingale for G(n,m), similar to the edge-exposure martingale for G(n,p).
作者：
Koubková, AKoubek, VCharles Univ
Fac Math & Phys Dept Software Engn Prague 11800 1 Czech Republic Charles Univ
Fac Math & Phys Dept Theoret Comp Sci & Math Log Prague 11800 1 Czech Republic Charles Univ
Fac Math & Phys Inst Theoret Comp Sci Prague 11800 1 Czech Republic
Let sigma'(n) denote the number of all strongly connected graphs on the n-element set. We prove that sigma'(n) greater than or equal to 2(n2) (1- n(n - 1)/2(n-1)). Hence the algorithm computing a transitive cl...
详细信息
Let sigma'(n) denote the number of all strongly connected graphs on the n-element set. We prove that sigma'(n) greater than or equal to 2(n2) (1- n(n - 1)/2(n-1)). Hence the algorithm computing a transitive closure by a reduction to acyclic graphs has the expected time O(n(2)), under the assumption of uniform distribution of input graphs. Furthermore, we present a new algorithm constructing the transitive closure of an acyclic graph. (C) 2002 Elsevier Science B.V. All rights reserved.
The image foresting transform (IFT) reduces optimal image partition problems based on seed pixels to a shortest-path forest problem in a graph, whose solution can be obtained in linear time. Such a strategy has allowe...
详细信息
The image foresting transform (IFT) reduces optimal image partition problems based on seed pixels to a shortest-path forest problem in a graph, whose solution can be obtained in linear time. Such a strategy has allowed a unified and efficient approach to the design of image processing operators, such as edge tracking, region growing, watershed transforms, distance transforms, and connected filters. This paper presents a fast and simple method based on the IFT to compute multiscale skeletons and shape reconstructions without border shifting. The method also generates one-pixel-wide connected skeletons and the skeleton by influence zones, simultaneously, for objects of arbitrary topologies. The results of the work are illustrated with respect to skeleton quality, execution time, and its application to neuromorphometry. (C) 2002 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.
This paper considers the problem of augmenting a given graph by a cheapest possible set of additional edges in order to make the graph edge-biconnected. An application is the extension of an existing communication net...
详细信息
This paper considers the problem of augmenting a given graph by a cheapest possible set of additional edges in order to make the graph edge-biconnected. An application is the extension of an existing communication network to become robust against single link-failures. An evolutionary algorithm (EA) is presented which includes an effective preprocessing of the problem data and a local improvement procedure that is applied during initialization, recombination, and mutation. In this way, the EA searches the space of feasible, locally optimal solutions only. The variation operators were designed with particular emphasis on low computational effort and strong locality. Empirical results indicate the superiority of the new approach over two previous heuristic methods. (C) 2001 Elsevier Science B.V. All rights reserved.
暂无评论