Parallel consistent labeling algorithms

Mackworth and Freuder have analyzed the time complexity of several constraint satisfaction algorithms.⁽¹⁾ Mohr and Henderson have given new algorithms, AC-4 and PC-3, for arc and path consistency, respectively, and have shown that the arc consistency algorithm is optimal in time complexity and of the same order space complexity as the earlier algorithms.⁽²⁾ In this paper, we give parallel algorithms for solving node and arc consistency. We show that any parallel algorithm for enforcing are consistency in the worst case must have O(na) sequential steps, wheren is number of nodes, anda is the number of labels per node. We give several parallel algorithms to do arc consistency. It is also shown that they all have optimal time complexity. The results of running the parallel algorithms on a BBN Butterfly multiprocessor are also presented.This work was partially supported by NSF Grants MCS-8221750, DCR-8506393, and DMC-8502115.     

Massively parallel augmenting path algorithms for the assignment problem

In this paper we describe how to apply fine grain parallelism to augmenting path algorithms for the dense linear assignment problem. We prove by doing that the technique we suggest, can be efficiently implemented on commercial available, massively parallel computers. Using n processors, our method reduces the computational complexity from the sequentialO(n ³) to the parallel complexity ofO(n ²). Exhaustive experiments are performed on a Maspar MP-2 in order to determine which of the algorithmic flavors that fits best onto this kind of architecture.     

Constraint satisfaction algorithms1

Constraint satisfaction problems are ubiquitous in artificial intelligence and many algorithms have been developed for their solution. This paper provides a unified survey of some of these, in terms of three classes: (i) tree search, (ii) arc consistency (AC), and (iii) hybrid tree search/arc consistency algorithms. It is shown that several important algorithms, when slightly rearranged, are of the latter hybrid form, but with arc consistency components that do not necessarily achieve full arc consistency at the tree nodes. Accordingly, we define several new partial AC procedures, AC1/5, AC1/4, AC1/3, and AC½, analogous to the well-known full AC algorithms which Mackworth has called AC1, AC2, and AC3. The fractional suffixes on our AC algorithms are roughly proportional to the degree of partial arc consistency they achieve. Unlike traditional versions, our AC algorithms (full and partial) are presented in a parameterized form to allow them to be embedded efficiently at the nodes of a tree search process. Algorithm complexities are compared empirically, using the n-queens problem and a new version called confused n-queens. Gaschnig's Backmarking (a tree search algorithm) and Haralick's Forward Checking (a hybrid algorithm) are found to be the most efficient. For the hybrid algorithms, we find that it pays to do little arc consistency processing at the nodes, incurring more nodes, but sufficiently reducing the work per node so as to obtain less work over the whole tree. The unified view taken here suggests several new algorithms. Preliminary results show one of these to be the best algorithm so far.     

New algorithms for max restricted path consistency

Max Restricted Path Consistency (maxRPC) is a local consistency for binary constraints that enforces a higher order of consistency than arc consistency. Despite the strong pruning that can be achieved, maxRPC is rarely used because existing maxRPC algorithms suffer from overheads and redundancies as they can repeatedly perform many constraint checks without triggering any value deletions. In this paper we propose and evaluate techniques that can boost the performance of maxRPC algorithms by eliminating many of these overheads and redundancies. These include the combined use of two data structures to avoid many redundant constraint checks, and the exploitation of residues to quickly verify the existence of supports. Based on these, we propose a number of closely related maxRPC algorithms. The first one, maxRPC3, has optimal O(end ³) time complexity, displays good performance when used stand-alone, but is expensive to apply during search. The second one, maxRPC3 ^rm , has O(en ² d ⁴) time complexity, but a restricted version with O(end ⁴) complexity can be very efficient when used during search. The other algorithms are simple modifications of maxRPC3 ^rm . All algorithms have O(ed) space complexity when used stand-alone. However, maxRPC3 has O(end) space complexity when used during search, while the others retain the O(ed) complexity. Experimental results demonstrate that the resulting methods constantly outperform previous algorithms for maxRPC, often by large margins, and constitute a viable alternative to arc consistency on some problem classes.     

Comments on Samal and Henderson: “Parallel consistent labeling algorithms”

Samal and Henderson claim that any parallel algorithm for enforcing arc consistency in the worst case must have (na) sequential steps, wheren is the number of nodes, anda is the number of labels per node. We argue that Samal and Henderson's argument makes assumptions about how processors are used and give a counterexample that enforces arc consistency in a constant number of steps usingO(n[su2a²2^na) processors. It is possible that the lower bound holds for a polynomial number of processors; if such a lower bound were to be proven it would answer an important open question in theoretical computer science concerning the relation between the complexity classesP andNC. The strongest existing lower bound for the arc consistency problem states that it cannot be solved in polynomial log time unlessP=NC.     

A parallel algorithm for surface-based object reconstruction

This paper presents a parallel algorithm that approximates the surface of an object from a collection of its planar contours. Such a reconstruction has wide applications in such diverse fields as biological research, medical diagnosis and therapy, architecture, automobile and ship design, and solid modeling. The surface reconstruction problem is transformed into the problem of finding a minimum-cost acceptable path on a toroidal grid graph, where each horizontal and each vertical edge have the same orientation. An acceptable path is closed path that makes a complete horizontal and vertical circuit. We exploit the structure of this graph to develop efficient parallel algorithms for a message-passing computer. Givenp processors and anm byn toroidal graph, our algorithm will find the minimum cost acceptable path inO(mn log(m)/p) steps, ifp =O(mn/((m + n) log(mn/(m + n)))), which is an optimal speedup. We also show that the algorithm will sendO(p ²(m + n)) messages. The algorithm has a linear topology, so it is easy to embed the algorithm in common multiprocessor architectures.     

Computing the minimal relations in point-based qualitative temporal reasoning through metagraph closure

Computing the minimal representation of a given set of constraints (a CSP) over the Point Algebra (PA) is a fundamental temporal reasoning problem. The main property of a minimal CSP over PA is that the strongest entailed relation between any pair of variables in the CSP can be derived in constant time. We study some new methods for solving this problem which exploit and extend two prominent graph-based representations of a CSP over PA: the timegraph and the series-parallel (SP) metagraph. Essentially, these are graphs partitioned into sets of chains and series-parallel subgraphs, respectively, on which the search is supported by a metagraph data structure. The proposed approach is based on computing the metagraph closure for these representations, which can be accomplished by some methods studied in the paper.In comparison with the known techniques based on enforcing path consistency, under certain conditions about the structure of the input CSP and the size of the generated metagraph, the proposed metagraph closure approach has better worst-case time and space complexity. Moreover, for every sparse CSP over the convex PA, the time complexity is reduced to O(n²) from O(n³), where n is the number of variables involved in the CSP.An extensive experimental analysis presented in the paper compares the proposed techniques and other known algorithms. These experimental results identify the best performing methods and show that, in practice, for CSPs exhibiting chain or SP-graph structure and randomly generated (both sparse and dense) CSPs, the metagraph closure approach is significantly faster than the approach based on enforcing path consistency.     

基于多核CPU的表约束并行传播模式研究

并行传播是并行约束程序领域中的一个研究方向,其研究内容是如何并行执行在约束上的过滤算法.根据维持表约束网络广义弧相容（generalized arc consistency,简称GAC）的串行传播模式,提出了维持表约束网络临时广义弧相容（temporary generalized arc consistency,简称TGAC）的并行传播模式,该模式基于多核CPU,由并行传播算法和并行过滤算法两部分组成;之后,给出了并行传播模式的可靠性证明,而且通过对并行传播模式的最坏时间复杂度分析,可以认为并行传播模式在平均过滤时间较长的实例上要快于串行传播模式;最终的实验结果也验证了上述结论,并行传播模式在多数实例集上取得了从1.4~3.4不等的加速比.     

Scalable Load Balancing Strategies for Parallel A* Algorithms

In this paper, we develop load balancing strategies for scalable high-performance parallel A* algorithms suitable for distributed-memory machines. In parallel A* search, inefficiencies such as processor starvation and search of nonessential spaces (search spaces not explored by the sequential algorithm) grow with the number of processors P used, thus restricting its scalability. To alleviate this effect, we propose a novel parallel startup phase and an efficient dynamic load balancing strategy called the quality equalizing (QE) strategy. Our new parallel startup scheme executes optimally in Θ(log P) time and, in addition, achieves good initial load balance. The QE strategy prossess certain unique quantitative and qualitative load balancing properties that enable it to significantly reduce starvation and nonessential work. Consequently, we obtain a highly scalable parallel A* algorithm with an almost-linear speedup. The startup and load balancing schemes were employed in parallel A* algorithms to solve the Traveling Salesman Problem on an nCUBE2 hypercube multicomputer. The QE strategy yields average speedup improvements of about 20-185% and 15-120% at low and intermediate work densities (the ratio of the problem size to P), respectively, over three well-known load balancing methods-the round-robin (RR), the random communication (RC), and the neighborhood averaging (NA) strategies. The average speedup observed on 1024 processors is about 985, representing a very high efficiency of 0.96. Finally, we analyze and empirically evaluate the scalability of parallel A* algorithms in terms of the isoefficiency metric. Our analysis gives (1) a Θ(P log P) lower bound on the isoefficiency function of any parallel A* algorithm, and (2) a general expression for the upper bound on the isoefficiency function of our parallel A* algorithm using the QE strategy on any topology-for the hypercube and 2-D mesh architectures the upper bounds on the isoefficiency function are found to be Θ(P log²P) and Θ(P[formula]), respectively. Experimental results validate our analysis, and also show that parallel A* search has better scalability using the QE load balancing strategy than using the RR, RC, or NA strategies.     

PRAM和LARPBS模型上有向序列翻转距离并行算法

分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n²)处理器,时间复杂度为O(log²n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n³)处理器,计算时间复杂度为O(logn).     

On the complexity of admissible search algorithms

This paper analyzes the complexity of heuristic search algorithms, i.e. algorithms which find the shortest path in a graph by using an estimate to guide the search. In particular, algorithm A¹, due to Hart, Nilsson and Raphael, is shown to require O(2^N) steps, in the worst case, for searching a graph with N nodes, if the so called “consistency assumption” does not hold for the estimate. Furthermore, a new search algorithm is presented which runs in O(N²) steps in the worst case and which never requires more steps than A¹.     

Efficient parallel recognition of some circular arc graphs,I

We present the first efficient parallel algorithms for recognizing some subclasses of circular arc graphs including circular arc graphs and proper interval graphs. These algorithms run in O(log² n) time withO(n ³) processors on a CRCW PRAM. An intersection representation can also be constructed within the same resource bounds. Furthermore, we propose some new characterizations of circular arc graphs and proper interval graphs.Portions of this paper have appeared in preliminary form in theProceedings of the 1989 IEEE international Symposium on Circuits and Systems [9], theProceedings of the 1989 Workshop on Algorithms and Data Structures [10], and theProceedings of the 1990 Canadian Conference on Computational Geometry [11].     

Efficient parallel recognition of some circular arc graphs, II

Based on Tucker's work, we present an accurate proof of the characterization of proper circular arc graphs and obtain the first efficient parallel algorithm which not only recognizes proper circular arc graphs but also constructs proper circular arc representations. The algorithm runs inO(log² n) time withO(n ³) processors on a Common CRCW PRAM. The sequential algorithm can be implemented to run inO(n ²) time and is optimal if the input graph is given as an adjacency matrix, so to speak. Portions of this paper appear in preliminary form in theProceedings of the 1989Workshop on Algorithms and Data Structures [2], and theProceedings of the 1994International Symposium on Algorithms and Computation [5].     

虫孔路由Mesh上的连通分量算法及其应用

用倍增技术在带有Wormhole路由技术的n×n二维网孔机器上提出了时间复杂度为O(log²n)的连通分量和传递闭包并行算法,并在此基础上提出了一个时间复杂度为O(log³n)的最小生成树并行算法.这些都改进了Store-and-Forward路由技术下的时间复杂度下界O(n).同其他运行在非总线连接分布式存储并行计算机上的算法相比,此连通分量和传递闭包算法的时间复杂度是最优的.     

Reasoning about networks of temporal relations and its applications to problem solving

An interval algebra (IA) has been proposed as a model for representing and reasoning about qualitative temporal relations between time intervals. Unfortunately, reasoning tasks with IA that involve deciding the satisfiability of the temporal constraints, or providing all the satisfying instances of the temporal constraints, areNP-complete. That is, solving these problems are computationally exponential in the worst case. However, several directions in improving their computational performance are still possible. This paper presents a new backtracking algorithm for finding a solution called consistent scenario. This algorithm has anO(n ³) best-case complexity, compared toO(n ⁴) of previous known backtrack algorithms, wheren denotes the number of intervals. By computational experiments, we tested the performance of different backtrack algorithms on a set of randomly generated networks with the results favoring our proposal. In this paper, we also present a new path consistency algorithm, which has been used for finding approximate solutions towards the minimal labeling networks. The worst-case complexity of the proposed algorithm is stillO(n ³); however, we are able to improve its performance by eliminating the unnecessary duplicate computation as presented in Allen's original algorithm, and by employing a most-constrained first principle, which ensures a faster convergence. The performance of the proposed scheme is evaluated through a large set of experimental data.     

Efficient parallel algorithms for path problems in directed graphs

In this paper we describe a technique for finding efficient parallel algorithms for problems on directed graphs that involve checking the existence of certain kinds of paths in the graph. This technique provides efficient algorithms for finding dominators in flow graphs, performing interval and loop analysis on reducible flow graphs, and finding the feedback vertices of a digraph. Each of these algorithms takesO(log² n) time using the same number of processors needed for fast matrix multiplication. All of these bounds are for an EREW PRAM.     

Optimal Parallel Randomized Algorithms for the Voronoi Diagram of Line Segments in the Plane

Abstract. We present an optimal parallel randomized algorithm for the Voronoi diagram of a set of n nonintersecting (except possibly at endpoints) line segments in the plane. Our algorithm runs in O(log n) time with high probability using O(n) processors on a CRCW PRAM. This algorithm is optimal in terms of work done since the sequential time bound for this problem is Ω(n log n) . Our algorithm improves by an O(log n) factor the previously best known deterministic parallel algorithm, given by Goodrich, ó'Dúnlaing, and Yap, which runs in O( log ² n) time using O(n) processors. We obtain this result by using a new ``two-stage' random sampling technique. By choosing large samples in the first stage of the algorithm, we avoid the hurdle of problem-size ``blow-up' that is typical in recursive parallel geometric algorithms. We combine the two-stage sampling technique with efficient search and merge procedures to obtain an optimal algorithm. This technique gives an alternative optimal algorithm for the Voronoi diagram of points as well (all other optimal parallel algorithms for this problem use the transformation to three-dimensional half-space intersection).     

A stochastic analysis of robust estimation algorithms in H∞ with rational basis functions

In this paper, a two‐stage nonlinear identification algorithm parameterized in terms of rational basis functions with fixed basis poles is studied when disturbances are subject to mild stochastic assumptions. The two‐stage algorithm is the archetype for robust estimation algorithms in H_∞ and its first stage is linear‐in‐data. Conditions for the consistency of both the stages are derived. It is shown that the two‐stage algorithm enjoys a better stochastic as well as deterministic performance than those of the linear algorithms. Copyright © 2001 John Wiley & Sons, Ltd.     

Robust satisfactory fault-tolerant control of uncertain linear discrete-time systems: an LMI approach

Fault-tolerant control is an important issue in practical systems. Based on satisfactory control and estimation theory, a passive fault-tolerant control strategy is proposed for a class of uncertain linear discrete-time systems in this article. Manipulating linear matrix inequality (LMI) technique, robust fault-tolerant state-feedback controllers are designed which take the possible actuator faults and sensor faults into consideration, respectively. The closed-loop systems are guaranteed by the designed controllers to meet the required constraints on regional pole index φ(q, r), steady-state variance matrix X index and control-cost function V ²(u) index simultaneously. Then, whether possible faults occur or not, the closed-loop systems would maintain the three desirable performance indices accordingly. Meanwhile, the consistency of the performance indices mentioned earlier is also discussed for fault-tolerant control.     

Soft arc consistency revisited

The Valued Constraint Satisfaction Problem (VCSP) is a generic optimization problem defined by a network of local cost functions defined over discrete variables. It has applications in Artificial Intelligence, Operations Research, Bioinformatics and has been used to tackle optimization problems in other graphical models (including discrete Markov Random Fields and Bayesian Networks). The incremental lower bounds produced by local consistency filtering are used for pruning inside Branch and Bound search.In this paper, we extend the notion of arc consistency by allowing fractional weights and by allowing several arc consistency operations to be applied simultaneously. Over the rationals and allowing simultaneous operations, we show that an optimal arc consistency closure can theoretically be determined in polynomial time by reduction to linear programming. This defines Optimal Soft Arc Consistency (OSAC).To reach a more practical algorithm, we show that the existence of a sequence of arc consistency operations which increases the lower bound can be detected by establishing arc consistency in a classical Constraint Satisfaction Problem (CSP) derived from the original cost function network. This leads to a new soft arc consistency method, called, Virtual Arc Consistency which produces improved lower bounds compared with previous techniques and which can solve submodular cost functions.These algorithms have been implemented and evaluated on a variety of problems, including two difficult frequency assignment problems which are solved to optimality for the first time. Our implementation is available in the open source toulbar2 platform.