ASYNCHRONOUS PARALLEL ARC CONSISTENCY ALGORITHMS ON A DISTRIBUTED-MEMORY MACHINE

The use of arc consistency algorithms can greatly reduce the search sp ace of a constraint satisfaction problem by preprocessing and eliminat ing variable assignments which can never participate in a solution. Th is paper examines two variations in the frequency of communications of three parallel arc consistency algorithms on distributed memory machi nes. This paper also examines the effect of simple load balancing vers us the more robust mean field annealing graph partitioning heuristic o n speedup. Through actual machine experimentation, we compute time req uired for the algorithms based on such parameters as distribution of w ork, frequency of message passing, and load balancing. Results indicat e that the configuration with less frequent communications and the rob ust load balancing yields the best speedup. (C) 1995 Academic Press, I nc.