The purpose of this workpackage is to develop tools for improving the performance of programs when executed in parallel. In this context, performance is measured not only in execution time but also according to storage utilization, etc.
Task 1.1: Infrastructure to Support the Exchange of Results -- To design of a common abstract syntax for CIAO-type languages with additional annotations to specify the pragmatic information resulting from the tools. This will allow ECRC and UPM to share tools despite their two distinct source languages, ElipSys and Ciao.
Task 1.2.1: Task Identification Tools for CIAO-Type Languages -- Through different forms of dependency analysis, to find which program segments are independent of each other and which segments depend on which other segments. Such segments will be scheduled in such a way that ``efficient'' parallel execution is guaranteed. First, parallelizers will be constructed for standard logic programming languages. Finally, issues involved in the extension of the tools and techniques to also work over domains different than Herbrand, will be considered.
Task 1.2.2: Task Identification Using Modeling of Control -- To investigate the applications of the modeling Prolog control approach to CIAO-type languages. An immediate potential benefit of this approach is to achieve better precision for task identification.
Task 1.3.1: Sequentialization of CIAO-Type Languages -- To develop techniques relating to granularity analysis and coalescing of parallel processes. One approach is deriving complexity functions at compile-time and comparing the complexity functions to a threshold at run-time. As an alternative, simpler estimation algorithms will also be explored based on recursion orders and other measures. A tool will be built using those techniques that are deemed most amenable to implementation.
Task 1.3.2: Schedule Analysis for Concurrent Logic Languages -- To develop schedule analysis which provides a way to introduce threads of totally ordered processes into a Concurrent Logic Language program without altering the termination properties of the program. The analysis will be developed as a general framework so that it can take input from various dataflow analyses, in particular from Task 1.5.3, and from more ad hoc techniques. The optimizations based on this analysis will be studied in detail and their implications for AKL investigated.
Task 1.3.3: Granularity Analysis for Concurrent Logic Languages and Implications for CIAO-type Languages -- To develop a thread-based granularity analysis for the efficient parallel evaluation of Concurrent Logic Languages. Schedule analysis will be integrated into a unified framework with techniques of granularity analysis based on estimating volumes of computation and communication associated with a process. The application of the unified granularity analysis to AKL will be outlined and its implications for CIAO-type languages will be investigated.
Task 1.4.1 Partial Evaluation for Improving the Parallel Execution of CIAO-Type Languages -- To develop a partial evaluator for CIAO-type languages. The work will be based on the PADDY system (for Prolog). The first step will be to investigate the methods appropriate to the partial evaluation of CIAO-type languages. An initial design based on the most promising methods will then be developed as the basis on which to implement an experimental prototype of the partial evaluator.
Task 1.4.2: Partial Evaluation for Improving the Parallel Execution of AKL -- To develop a partial evaluator for AKL. The partial evaluator will be based on a set of program transformation rules that preserve the semantics of the program. As most techniques developed in Mixtus (a partial evaluator for Prolog) are applicable when doing partial evaluation on AKL, it is possible to start almost directly with the implementation work. We will also investigate additional techniques more specific for Concurrent Logic Languages, partly by using results from other tasks in the project.
Task 1.5.1: Producer-Consumer Analysis for Concurrent Logic Languages -- To develop a semantic approach to producer and consumer analysis for the concurrent logic languages. It will use simple constructs so that the result will provide the basis of a simple and efficient compilation tool for concurrent logic languages such as AKL. A goal-independent, bottom-up analysis will be built by replacing matching with unification and using contextual detail to differentiate between a produced and a consumed term. The analysis will be developed with as few ad hoc features as possible, and then refined to the design of a compilation tool.
Task 1.5.2: Suspension Analysis for Concurrent Logic languages -- To analyze suspension freeness for concurrent programs and concurrent constraint programs with respect to a given goal. We want to abstract directly the transition system semantics of a generic (concurrent logic) language. Moreover, we want to investigate various abstract domains suitable for this kind of analysis. The outcome of this research can be quite useful to optimize compilers for concurrent (constraint) logic programs.
Task 1.5.3: Analysis of Suspension-Free Concurrent Logic Programs -- Many program properties can be derived by using much simpler techniques in the case of suspension-free programs. In fact, the reference semantics of a suspension-free concurrent program can be obtained by essentially considering the program as a pure logic program, i.e. by ignoring synchronization. Properties related to the program success set can then be derived using well known analysis techniques developed for pure logic languages. These include the basic properties (such as groundness, aliasing, sharing, freeness and types) and other higher-level properties, such as those related to task identification and sequentialization.
Task 1.5.4: Compositional Analysis of Suspension and Deadlock in Concurrent Logic Programs -- To study the ability of analyzing programs in a modular way. In the standard approach to program analysis, the entire program is supposed to be available at one time. This makes the analysis sometimes inapplicable to large programs, which are exactly those which could benefit from the results of the analysis. It is also useful to define incremental analysis (to be typically incorporated in an incremental compiler). Modular analyses can be obtained by using a reference semantics, which is compositional with respect to program union. We will extend the results of tasks 1.5.2 and 1.5.3 to compositionality.
Task 1.6.1: Task Storage Management for Improving Parallel Execution of AKL -- To develop a storage optimizer for the concurrent logic language AKL. One goal is to identify the consumption of the last reference to data structures, which may then be immediately reused, improving memory utilization, as well as execution performance. The analysis tool should identify last data references for AKL. The tool will be designed so as to accept scheduling and implicit synchronization annotated programs. Such annotations may be given by the user, or alternatively a result of scheduling/synchronization analysis.