Arc Consistency Problem: A Case Study in Parallel Programming with Shared Objects

摘要

In this paper, we will describe our experiences with this model for implementinga parallel algorithm for the Arc Consistency Problem. We show how to develop a parallel algorithm for this application using shared objects. We provide measurements of the Orca program on two distributed systems, which use the same network (Ethernet) and operating system (Amoeba), but differ in processor speed and size of local memory. We use these systems to study the impact of processor speed and memory size on performance. We give a detailed analysis of the results, by measuring the different types of overhead (communication, search overhead, and load imbalance), using up to 50 processors.