Automatic compile-time parallelization of logic programs for restricted, goal-level, independent and-parallelism.

A framework for the automatic parallelization of (constraint) logic programs is proposed and proved correct. Intuitively, the parallelization process replaces conjunctions of literals with parallel expressions. Such expressions trigger at run-time the exploitation of restricted, goal-level, independent and-parallelism. The parallelization process performs two steps. The first one builds a conditional dependency graph (which can be implified using compile-time analysis information), while the second transforms the resulting graph into linear conditional expressions, the parallel expressions of the &-Prolog language. Several heuristic algorithms for the latter ("annotation") process are proposed and proved correct. Algorithms are also given which determine if there is any loss of parallelism in the linearization process with respect to a proposed notion of maximal parallelism. Finally, a system is presented which implements the proposed approach. The performance of the different annotation algorithms is compared experimentally in this system by studying the time spent in parallelization and the effectiveness of the results in terms of speedups.

Complete and efficient methods for supporting side effects in independent/restricted and-parallelism

It has been shown that it is possible to exploit Independent/Restricted And-parallelism in logic programs while retaining the conventional "don't know" semantics of such programs. In particular, it is possible to parallelize pure Prolog programs while maintaining the semantics of the language. However, when builtin side-effects (such as write or assert) appear in the program, if an identical observable behaviour to that of sequential Prolog implementations is to be preserved, such side-effects have to be properly sequenced. Previously proposed solutions to this problem are either incomplete (lacking, for example, backtracking semantics) or they force sequentialization of significant portions of the execution graph which could otherwise run in parallel. In this paper a series of side-effect synchronization methods are proposed which incur lower overhead and allow more parallelism than those previously proposed. Most importantly, and unlike previous proposals, they have well-defined backward execution behaviour and require only a small modification to a given (And-parallel) Prolog implementation.

An abstract machine for restricted and-parallel execution of logic programs

Although the sequential execution speed of logic programs has been greatly improved by the concepts introduced in the Warren Abstract Machine (WAM), parallel execution represents the only way to increase this speed beyond the natural limits of sequential systems. However, most proposed parallel logic programming execution models lack the performance optimizations and storage efficiency of sequential systems. This paper presents a parallel abstract machine which is an extension of the WAM and is thus capable of supporting ANDParallelism without giving up the optimizations present in sequential implementations. A suitable instruction set, which can be used as a target by a variety of logic programming languages, is also included. Special instructions are provided to support a generalized version of "Restricted AND-Parallelism" (RAP), a technique which reduces the overhead traditionally associated with the run-time management of variable binding conflicts to a series of simple run-time checks, which select one out of a series of compiled execution graphs.

Can seed production and restricted dispersal limit recruitment in Pinus pinaster Aiton from the Spanish Northern Plateau?

Natural regeneration faces increasing difficulties in dry forests from the Mediterranean basin, including for normally well-regenerating species such as maritime pine (Pinus pinaster Aiton). In this paper, we studied female fertility, seed dispersal and spread rates in P. pinaster from the Spanish Northern Plateau, where natural regeneration failure is a main concern for forest managers. For this purpose we periodically collected data from seed traps and trees located at two core locations across several years. We found significant variation in interannual cone production, with the best seed trees being the same across years. In addition, we found highly skewed distributions of female reproductive effort and large fertility differences across stands located few kilometres away. Annual seed dispersal kernels fitted lognormal or 2Dt models depending on the stand analysed, with median dispersal distances between 14 and 25 m. Kernels fitted for maximum dispersal periods showed an outstanding intraseasonal variation of median dispersal distances, from 10 to 54 m, in association to variable patterns of rainfall and maximum wind speed. The amount of seed produced appeared to be enough to guarantee the natural regeneration of the stands during the typical 20-year regeneration period. Colonisation simulations concluded that Mediterranean maritime pine has a notable dispersion capacity, which is strongly influenced by levels of fecundity and, especially, by the number and frequency of long-distance dispersal events. The latter play a key role in tree dispersion processes through enlarging the occupied area and fostering the invasion of abandoned crop land.