UPM Activities in PEPMA

• Development of basic technologies:
  • Global Analysis Technology: efficient parallel execution of programs, and, in particular, of logic programs requires gathering information at compile-time through global analysis of the program. One of the main roles of UPM in PEPMA has been to develop basic compile time technology and to implement tools based on this technology to cope with the problems involved in parallel execution of Prolog. UPM, in close collaboration with U. of Bristol, has explored the approach of ``abstract interpretation'' and developed several related techniques for the analysis of sharing and freeness of program variables (as well as other issues), basic characteristics for determining independence and thus parallelizability [9][6][12][11].

  • Theory of Independent And-Parallelism: general models of parallelism in logic programs, such as the Extended Andorra Model (EAM) developed in PEPMA, allow a combination of or- and and-parallelism to occur. While or-parallelism in general causes no problems, indiscriminate and-parallel execution of program segments can potentially be inefficient and even produce a slower program than the sequential version. Thus, a general model has to be controlled by additional rules. One example of such a rule is the ``Andorra Principle'' - running only determinate goals in parallel used in Andorra-I. Within PEPMA, UPM has developed additional rules - ``strict-'' and ``non-strict'' independent and-parallelism - which guarantee efficiency in and-parallel execution and developed the related compile-time and run-time checking technology required to ensure that the efficiency conditions are met [8].

• Compile-time tools:
  • Analyzers for Sharing and Freeness: two global analyzers have been developed, based on the previously described techniques, which can infer variable sharing and freeness [11]. These analysis tools have been shown to be useful as part of a number of program transformation tools (described below) related to program parallelization and program translation. In addition, the techniques has been used by U. of Bristol in the Andorra-I compiler [14].

  • Parallelization Algorithms: three parallelization algorithms based on the theory of (strict) independent and-parallelism have been proposed. These algorithms show promise in parallelizing programs on the &-Prolog system (a system directly implementing independent and-parallelism) [15][10][7].

  • Automatic Translators: the parallelism found by the above mentioned parallelizers can potentially be exploited by any execution model subsuming IAP. Two tools have been developed, implemented and benchmarked which automatically translate Prolog Programs into the Andorra Kernel (AKL) and Andorra-I Languages developed in PEPMA. In the case of AKL the ``Prolog to AKL'' translator, developed in collaboration with SICS, bridges other semantic and syntactic differences and is specially relevant: AKL is quite different from Prolog. The translator provides a compatibility path between AKL and the Prolog world by making it possible to run Prolog programs automatically under AKL [2][1]. In the case of Andorra-I the translation makes it possible to exploit independent and-parallelism, which is not natively supported by this system [13].

• Parallel Execution Models:

  The Basic Andorra Model proposed in PEPMA achieves early and parallel execution of dependent goals, thus focusing on Dependent And-Parallelism (DAP). This has been extended to also include independent and-parallelism in a new framework now called Extended Andorra Model (EAM). The EAM, being a very rich model, represents a fairly large departure from conventional parallel Prolog models and implementation techniques. Other more conventional and well understood models being studied in the context of PEPMA project: the Muse and Aurora models, which exploit Or-Parallelism, and the &-Prolog model, exploiting independent and-parallelism. In the spirit of achieving some of the capabilities of the EAM while preserving the efficiency of these models and combining their capabilities, two new models have been developed by UPM in PEPMA, namely the ACE model and the IDIOM model.

  IDIOM is aimed at combining all the three forms of parallelism (Dependent and Independent And- and Or-Parallelism), using well-understood implementation techniques. IDIOM is based on previous existing models, in particular in the Andorra-I and &-Prolog models for DAP and IAP and in the Aurora model for Or-Parallelism [5]

  The ACE model is aimed at combining Independent and-parallelism and Or-Parallelism in a very efficient way. It is based also in previous models, which already have efficient implementations exploiting one and the other forms of parallelism separately: the &-Prolog and Muse models. As mentioned in section 3, this combination may be specially relevant from a commercial exploitation point of view [4].

• Evaluation tools: A graphical tool has been developed in collaboration with U. of Bristol and SICS, with a first prototype running as a demo, which can show a visual representation of the parallel execution of programs. The aim is to design a good graphic representation for different parallelism models (e.g., Aurora Or, Andorra-I Or, Or + Andorra-I And, IAP, Or + IAP, Or + DAP + IAP) and a tool to visualize parallel program execution.

• Design and study of a large shared virtual address parallel architecture: in addition to collaborating in the design of the DDM system the activity of UPM in this area has concentrated in developing an analytical model of the DDM architecture. This effort complements the empirical evaluation done by U. of Bristol and SICS. The empirical evaluation will in turn validate the model [3].