Thesis' Abstract
Parallelism and logic programming are two fields that have been successfully combined, as is shown by recent implementations of parallel logic programming systems. There are two main sources of parallelism in logic programming, namely or- and and-parallelism. Or-parallelism is exploited when several alternative clauses to a goal are executed in parallel. And-parallelism is exploited when we execute two or more goals of the same clause simultaneously. Exploitation of full or- and and-parallelism is limited by the number of physical processors available in a system. And-parallelism is also limited by the interdependence among goals in a clause.In parallel logic programming systems which exploit both and- and or-parallelism, a problem that arises is how to distribute processors between the dynamically varying amounts of and- and or-work that are available. Solutions have been reported for distributing only or-work, or distributing only and-work, but the issue of distributing processors between both kinds of work has not yet been addressed. In this thesis we discuss the problem of distributing and- and or-work in the context of Andorra-I, a parallel logic programming system that exploits determinate and-parallelism and or-parallelism, and propose scheduling strategies that aim at efficiently distributing processors between and- and or-work.
We study general criteria that every reconfigurer should meet to reconfigure processors without incurring too high overheads in the Andorra-I system. We propose two different strategies to reconfigure processors between and- and or-work based on these criteria. One strategy, work-guided, guides its decisions by looking at the amount of current and- and or-work available in an application during execution. The other strategy, efficiency-guided, is designed around the intuition that processors should spend most of their execution time doing useful work, i.e., performing reductions.
Our benchmark set consists of programs that contain both and-parallelism and or-parallelism and programs that contain a single kind of parallelism. We compare the results produced by our strategies with the results produced by a version of Andorra-I that provides only a fixed division of processors between and- and or-work. Results show the benefit of adding a reconfigurer to Andorra-I and show that both strategies perform better than any plausible fixed configuration for all benchmarks. Although our work is focussed on the Andorra-I system, we believe that both strategies could be applied to other parallel logic programming systems that aim at exploiting both and- and or-parallelism.
My home page.
Andorra-I.