Pipeline Optimizations in AND-Parallel Logic Programs

A common Charcteristis of several And parallel execution models is that the roducer has to generate a complete binding for a shered variable before the consumer may start its execution. This reduces the potential degree of parallelism offered by several logic programs. Sebveral cases exist where the data transmitted from the producer to teh consumer are concurrently executed and cooperate according to a pipeline mode. The definition of a pipeline And optimization requires a suitable notion of partial ground binding to be exchanged between teh producer and the consumer. This paper presents a bottom up abstract interpretation analysis able to detect cases when pipeline optimization may be applied. The notion of partial ground binding is obtained through a refinement of the notion of ground interdependency. The analysis will be implemented as a step of the compilation of logis programs for execution on a massively parallel system. A complete example is presented and discussed.