Work distribution (task scheduling) is one of the most important components of a distributed system. Its objective is to determine an assignment of tasks to processors and to determine the order in which tasks will be executed in order to improve performance by balancing the workload.
We can classify schedulers in parallel logic programming systems that combine and-parallelism with or-parallelism according to its functionality, i.e., to find and-work, to find or-work, or to choose between and-work and or-work available. Therefore we distinguish three kinds of schedulers:
The schedulers are organised this way in order to minimise overheads of searching for work. Therefore, a processor first tries to find work that is closer to it in its subtree, either or-work or and-work. If there is no work available in its subtree, tries to select and-work or or-work from other subtrees.
We designed and developed several strategies to select or-work and to select between and-work and or-work. The DSLP (Distributed Scheduling for Logic Programming) model [33,32] was designed for the DAOS system. Therefore deals with the problems of selecting between and-work and or-work. DSLP assumes that and-scheduling must be done in a centralised fashion, because of the low granularity of this kind of work and high overhead incurred by distributed algorithms on distributed platforms. On the other hand, or-parallelism is much coarser-grained and can utilise more sophisticated scheduling strategies adapted to the distributed environment.
We developed other strategies to distribute only or-work for the Plosys system and for the pclp(FD) model [103,104]. Parallel constraint logic programming over finite domains - pclp(FD) - is a model that exploits multi-sequential or-parallelism in a distributed environment. The model assumes that workers (processing elements) are interconnected via a network and executes constraint logic programs [40,72]. The scheduling strategy is dynamic and totally distributed, based on incremental stack copying [2]. It is also based on Hwang's termination algorithm. In order to evaluate the strategy, the Tamagoshi prototype [105] was designed to simulate synthetic workloads in networks of processors. Tamagoshi simulates two kinds of strategies: one centralised as in the Plosys system and the one proposed for the pclp(FD) model.
The strategy developed for the Plosys system, Penelope [28], replaces the centralised algorithm, used originally, by a hierarchical scheduler that tries to minimise the bottleneck of the centralised scheduler while avoiding the overheads of totally distributed strategies.
The following sections describe Tamagoshi, Penelope and DSLP in more detail.