next up previous
Next: Program Transformation Up: Baseline Previous: Parallel Logic Programming Platforms

Program Analysis

Task identification is concerned with determining which parts of an (initially sequential) program meet some notion of independence and can thus be safely run in parallel. Independence notions proposed for logic programs include strict independence [40] (which corresponds to the traditional notion of independence when applied to goals) as well as non-strict independence [41] (which relaxes the previous notion allowing more parallelism).

Granularity analysis and control is concerned with avoiding parallel execution of threads whose execution cost is below a certain threshold which may make such parallel execution inefficient. In the context of logic programming, preliminary work has generally focused on upper bound cost analyses [20, 21].

Schedule analysis is concerned with deducing at compile-time a partial scheduling of processes in an (initially concurrent) program which is consistent with the program's behavior. An ordering of the atoms is determined that does not contradict data dependencies. The optimizations depend on the existence of a total ordering of atoms within a thread and follow from applying mode analysis, type analysis, and reference analysis to the threads [46]. This information is used to perform a producer/consumer analysis as a previous step for schedule analysis.

Suspension analysis is concerned with determining the patterns of activation of processes in concurrent programs [16]. Such an analysis provides information regarding reactive properties such as deadlock and floundering.

Type and alias analysis help to reduce memory consumption by allowing the low-level compiler to make destructive assignments and explicit disposal of memory cells where appropriate.

Abstract interpretation [17, 18] provides a semantic based approach to dataflow analyses. Different semantics definition styles lead to different approaches to program analysis. In the case of logic programs, there are mainly two approaches, namely, top-down analyses [10, 9, 19, 50, 53, 45, 52, 70, 8, 54] (which propagate the information in the same direction as SLD-resolution) and bottom-up analyses [53, 51]. As discussed in [52], there are applications for which each of the two approaches is more adequate. The technique of ``modeling Prolog control'' can bridge the gaps between these two techniques [4].


next up previous
Next: Program Transformation Up: Baseline Previous: Parallel Logic Programming Platforms

<webmaster@clip.dia.fi.upm.es> Last Modified: Fri May 9 18:15:08 MET DST 1997