PARALLEL EXECUTION OF LOGIC PROGRAMS BY LOAD SHARING

Execution of a logic program can be sped up by load sharing among a gr oup of interconnected processors, Network contention and load imbalanc e are two potentially limiting factors that must be dealt with careful ly. In this paper, we discuss a task scheduling scheme in which proces sors share the workload by voluntarily following a universal task dist ribution rule. Communication is reduced by having processors cooperate without frequent exchange of information. However, load balancing is rendered more difficult. We propose solutions to the problem by alteri ng the shape of a search space to remove the so-called structural imba lance, and by following a statistically even task distribution rule. S imulation and experimental data indicate that the method is effective for a number of programs for which existing scheduling methods tend to generate overly fine-grained tasks that lead to heavy traffic in the network, Speed-up factors by the proposed technique are comparable to, or better than, that by a typical system which relies solely on dynam ic task migration to balance the workload. The scheme appears to be pa rticularly suitable for implementation on loosely coupled parallel pla tforms. (C) Elsevier Science Inc., 1997