Optimistic Parallel biscrete Relaxation

Abstract

Discrete relaxation is frequently used to compute the fixed point of a discrete system X= /(X), where f is monotonic with respect to some partial order $. Given an appropriate initial value for X, discrete relaxation repeats the assignment X - /(X) until a fixed point for f is found. Monotonicity of f with respect to $ is a sufficient (but in general not necessary) condition for iterative, hill-climbing techniques such as discrete relaxation to find the fixed point of f. In this paper we introduce monotonic asynchronous iteration as a novel way of implementing parallel discrete relaxation in problem domains for which monotonicity is a necessary condition. This is an optimistic technique that maintains monotonicity without limiting concurrency, resulting in good parallel performance. We illustrate this technique with the parallel implementation of a constraint satisfaction system that computes globally consistent solutions, and present performance numbers for experiments on a shared-memory implementation. The performance numbers show that it is indeed possible to obtain a reasonable speedup when parallelizing global constraint satisfaction. We believe that monotonic asynchronous iteration is applicable to parallel discrete relaxation in general.