Load Balancing in a Distributed-Memory Or-Parallel System

We consider or-parallel logic programming implementations on parallel machines with no shared-memory. Traditional implementation techniques as employed in Aurora and Muse are not applicable. In our orparallel execution model, all processors perform identical work initially. At each choice point, processors are divided evenly among alternatives of the choice point. Backtracking is employed if there are not enough processors for such a division. As execution proceeds, the division of processors among alternatives becomes uneven. In this paper, we present two different methods of load balancing called equalization and apportion, aimed at improving the degree of parallelism. Equalization and apportion reallocates all processors to the or-parallel branches by copying heaps through a interprocessor communication network. 1 Introduction We consider or-parallel logic programmingimplementations on parallel machines with no shared-memory. Traditional implementation techniques as employed in Aur..