In this first year we have made what we believe is major progress towards achieving the project objectives. In particular, in this period activities have concentrated mainly on the first objective above, i.e. developing and applying basic program analysis and manipulation technology and building and integrating tools based on this technology. In addition, some preliminary work has also been done in enhancing the project partner platforms and in studying issues concerned with parallel program development.
One of our first steps has been to develop a common abstract syntax for CIAO-type languages, starting with a specification suitable for a parallel Prolog [13]. This syntax has been collaboratively designed by UPM and ECRC (with help from SICS). The interfaces defined are multi-purpose: for example, the information gathered by analyzers can be easily inspected by the user, passed over to other analyzers as start-up information, or provided to the task identification phase. They also allow the user to provide seed information which could help the analyzers. Care has been taken to design the abstract syntax to be readable by Edinburgh-like Prolog systems as a meeting-point for the different partner platforms. Similar objectives have guided the definition of an abstract syntax for AKL at SICS [76].
With respect to analysis tools several program analysis techniques have been investigated and a General-purpose Abstract Interpreter, GAIP, has been designed and partly implemented at ECRC [84]. Also, an existing general framework for abstract interpretation, PLAI (Programming in Logic with Abstract Interpretation, already developed at UPM), has been refined and enhanced, and the integration within our platform, the &-Prolog/Ciao-Prolog compiler and system, has been improved [14, 65]. GAIP and PLAI work over several domains, providing general frameworks for integrating multi-feature analyses based on abstract interpretation. Abstract semantics of programs are computed at different program levels: at the variable, the literal, and the predicate level. This semantics provides the necessary information for applications such as cost analysis, dependency detection, and grain-size control, which in turn are the basis for effective parallelization of programs.
From the point of view of annotation (i.e. task identification), at UPM a number of algorithms previously proposed by us for and-parallelism, integrated within &-Prolog, have been investigated further and extended, in particular to be able to exploit granularity information through cost analysis (as provided by the sequentialization tools being developed). Also, new algorithms have been defined which are independent from the notion of dependency used in the parallelization and can thus be used for several concepts of independence. Another achievement has been to enhance the concepts of independence themselves. UPM has defined a new, more relaxed version of non-strict independence (generalized non-strict independence) and provided new proofs for a number related results, most significantly for the fact that this notion of independence preserves the ``no slowdown'' property, i.e. that a parallelized program be guaranteed, modulo scheduling and communication overheads, to run no slower than its sequential counterpart [42]. We have also proposed algorithms for determining non-strict independence of goals using sharing and freeness information (as determined by PLAI or GAIP) as a starting point, and for efficiently isolating execution environments for independent goals at compile-time [15]. Finally, we have also proposed a series of guidelines for the design of Ciao-Prolog, the successor of &-Prolog, which incorporates support for constraints and better support for concurrency, and which is currently being implemented [43].
Regarding granularity control, the CASLOG (Cost Analysis System for LOGic programs) system has been studied both at ECRC and UPM. An interface between GAIP and CASLOG has been designed at ECRC and a similar interface between PLAI and CASLOG has been obtained at UPM, by supplying mode information to the latter from the former [56, 84]. At UPM a preliminary implementation of an annotator which transforms programs in order to perform dynamic run-time granularity control has been completed and some performance results obtained. Also a technique has been proposed which allows the efficient computation of term sizes (which are instrumental in granularity control) dynamically [57].
At ECRC program transformation techniques have been developed with the aim of rewriting programs to better exploit parallelism. ECRC has designed the transformation strategy which will form the basis of a partial evaluation system [68]. The strategy is provably correct for pure programs, mechanizable, gives good results on (non-parallel) benchmarks and, most importantly, will scale up to large programs. It is aimed at or-parallel programs in particular, and some preliminary results have been obtained for such programs.
At Southampton, a framework for schedule analysis has been developed[54]. It is formulated in terms of the operational semantics for a program and builds from the notion of a data-dependence to define a procedure for creating threads. All data-dependencies which can possibly occur between the atoms of a clause for any query, are collected together and compared, to identify those atoms of a clause which must be allocated to different threads. This gives a straightforward prescription for partitioning the atoms of a clause into threads. The threads generated by this procedure, however, in exceptional circumstances, can compromise the behavior of the program. Thus, a safety result has been presented which states the conditions under which the work of a scheduler can be safely reduced from scheduling processes to scheduling threads. The theorem provides a way to check the integrity of the threads so that erroneous threads can be identified and filtered out. The data-dependencies required for the analysis can be supplied by producer and consumer analysis.
To determine the data dependencies within a program, a method for identifying producers and consumers of data has been explored [48]. Specifically, instead of tracing all possible reduction sequences, for each branch of the proof tree it produces a set of other branches which must be executed before that branch. In so doing, the necessary ordering of goal execution is represented explicitly, rather than implicitly in (say) an enumeration of the possible interleavings. This provides information on producers and consumers of data: a producer must obviously precede a consumer of the same data [49].
The derivation of accurate variable sharing information is important for many applications, including the detection of producers and consumers. Sharing abstractions often exploit the interplay between groundness and aliasing information, and indeed, accurate analyses are often good at groundness propagation. A synergistic relationship also exists between sharing and type analysis but curiously, however, type information has only been exploited to a limited extent in sharing analysis (usually by tracing either freeness or linearity [50, 51]). A new approach to sharing analysis has been developed which infers sharing information to a higher degree of accuracy than that of previous proposals [52]. The analysis is founded on abstract substitutions which elegantly encode deep structural properties of substitutions. This enables the interplay between sharing and type information to be better exploited. Correctness is formally proven and the usefulness of the technique is demonstrated by the synthesis of a powerful depth-k sharing domain.
Significant effort has been devoted also to suspension analysis in concurrent logic languages. These languages can be seen as specifying reactive systems consisting of collections of communicating processes: if the computation reaches a state in which all the processes are stuck the program suspends. The concept of suspension and deadlock are consequences of the introduction of synchronization constructs. Pisa has defined a general and simple framework [21] which is based on the transition system operational semantics, and has then analyzed the property of suspension freeness for concurrent programs with respect to a given goal. Results include various abstract domains suitable for this kind of analysis, such as dependency relations, sharing, and extractor sharing analysis. All goals planned in this task have been achieved and also the results extended to the case of concurrent constraint programming, introducing the notion of confluence for concurrent constraint programming [22] (which is a generalization of the concept of concurrent logic programming) and showing that for a large class of programs, namely the ``confluent'' ones, the analysis of suspension can be performed very efficiently and accurately.
The results presented above could be applicable to the analysis of AKL, since AKL is an extension of concurrent logic languages. Yet, AKL differs from concurrent logic languages in that it supports deep guards. Thus, no suitable framework directly usable for analysis of parallel AKL available at the beginning of the project, a new framework closely related to abstract interpretation has been developed at SICS. Whereas abstract interpretation often has been viewed as an interpreter using an abstract domain for its data, we have found it necessary, due to the parallel nature of AKL, to more strictly set up semantic equations first and then solve them. Thus, our method follows quite closely the way in which abstract interpretation is formally defined. As an added advantage of this approach, it is very easy to experiment in this framework with different semantic equations, domains, and fixpoint solvers. Although correctness of the analysis is of course crucial for its usefulness, there has been little work on correctness proofs, but the work has rather focussed on an effective and efficient implementation. In order to improve the efficiency of the fixpoint solver we have been using some results from graph theory in order to avoid unnecessary computations.
In particular, SICS has developed and implemented an analysis framework for type and alias analysis of the concurrent constraint language AGENTS (AKL) [45, 73, 74, 75, 76]. The whole system was coded in the developing versions of the AGENTS programming system. The framework is a semantics which associates to each AGENTS program a set of program points and a set of semantic equations. This is solved using a generalized fixpoint computation framework developed within the project. The fixpoint solver utilizes various properties of the graph describing the set of equations to reduce the amount of computation necessary. We concentrated on a domain defined for our purpose in [75], the AT-domain, capturing alias and type information.
The above described lines of research allow collaboration within or outside the scope of the ParForCE project, and we also cooperate closely with the ESPRIT BR project ACCLAIM [85].
Several enhancements have been performed on our execution platforms to improve the support of the tools. This includes interfaces to visualization tools, improvement of memory management in order to support execution of larger programs, inclusion of granularity control primitives, as well as looking ahead to the incorporation of new types of parallelism [79, 36].
In the program development area, INRIA (-Rocquencourt), with strong participation from Bristol, has organized the working group with the purpose of facilitating exchanges between partners in the area. Most of our results in the area are still theoretical, although we also have some practical progress in visualization tools. The ParSee visualization tool [69] has been developed and implemented at ECRC. This is a profiling tool which aids performance debugging, and differs from most such tools by being aimed at the programmer rather than at the system developer. Fine details of the trace are abstracted away, yielding a high-level description of how the program parallelization affects the parallel execution. ParSee currently generates a set of color-coded diagrams, but we are experimenting with a new graphical interface which depicts several runtime properties in a single 3-dimensional picture. The picture can be rendered using either RenderMan or an interactive rendering tool developed at ECRC. The VisAndOr tool [16], developed at UPM, is another high-level visualization tool aimed at depicting the parallel execution of logic programs. It allows visualization of several forms of parallelism. VisAndOr shows a static picture of the parallel execution of the program which is useful at many user levels: at the (parallel) Prolog programmer level, at the low-level implementation programmer level, and also at the application user level. In addition to the parallel structure of the program execution, the tool presents accurate timing of events, task-processor and stack set-processor assignment, etc. VisAndOr is currently interfaced with the &-Prolog, Muse, Aurora [58] and Andorra-I [77] systems and with the visualization tool Must [82].
In summary, we feel that the project has had quite a number of major achievements in this first year, that it has met or exceeded its first year objectives, and it is well positioned for tackling the second year targets.