VIM: A Virtual Multicomputer

Proposal No: ERB4050PL930186
Contract No: ERBCHRXCT930401
Project officer: Luis Minguez Lara, tel: +32(2)295.00.79, fax: +32(2)296.32.70



Objectives

The three topics which bind this network together are parallel systems, advanced compilation techniques and artificial intelligence (AI) with a common substrate in the programming language Lisp. The research aim of this project is to demonstrate the advantages accruing from the combination of these three technologies.

There is also an educational aim: since these three areas are fundamental to future software developments, two workshops aimed at postgraduates-as well as at widening the expertise of the partners-will be held, one on parallel programming and compilation and another on artificial intelligence.

Both of these aims will be supported by a concrete output from the network, namely a public domain implementation of a parallel symbolic processing environment for at least a collection of Unix workstations and Unix shared-memory multiprocessors. Other outputs will be tools for monitoring the behaviour of parallel programs, for analyzing parallel programs statically, specialized compilers, applications in artificial intelligence and publications.

While research within each of the above mentioned topics will continue with collaboration between the interested partners, a point of the constitution of this network is that it permits the construction of feedback loops between system and application, compiler and application and between all three. What follows is an outline of the objectives for each research area. The detailed workplan divides these topics into six specialist subjects.


Parallel Systems

Eight of the partners have been working independently or bilaterally on parallel systems and parallel models of computation. The objective is to unify our experience, avoid duplication of effort and develop a common model (and at least two implementations) of parallel computing which can be supported on a variety of architectures (shared-memory, distributed and array). The use of object-oriented mechanisms will play a key rôle in abstracting architecture-dependent features, all but one of the partners in this group having significant experience in their use. The first version of the model will be established by the end of year 1, with revisions at the end of year 2 and a final version by the end of the project-detailed tasks contributing to this goal appear in sections on Parallel models and systems and Parallel Applications.


Compilation

Six partners are working on compilation techniques to support object-oriented languages in parallel environments. Of these, three are collaborating closely already under the APPLY project which finishes in the summer of 1994. This group has a significant overlap with the parallel systems group and a smaller one with AI. Its primary objective will be to demonstrate the total compilation (ie. construction of a delivery module) of at least one AI application for concurrent execution. The methodology will follow from the ICSLA project at INRIA and the APPLY project, leading to systems capable of delivering parallel symbolic applications, verification of such systems (Kiel) and automatic mapping (GMD-FIRST) to target architectures. As the project progresses, the targets for this component will simply scale up: at the end of year 1 it should be possible to demonstrate the total compilation of a small program for parallel execution and to follow this with larger examples, taken from the other partners, in succeeding years. Overlapping with this, but starting in year 2, it should be possible to show the application of techniques developed in the ProCoS project to a small parallel application, following with larger examples up to the end of the project. Detailed tasks contributing to this topic appear in the sections on Static analysis and Semantics and verification.


Artificial Intelligence

Eleven of the partners are working on various aspects of artificial intelligence. The objective of this part of the network is to serve as a forum for sharing experience, attempting to verify or replicate the results of others and exploring new problem-solving architectures. Thus, a major output here will be experimental implementations of ideas and papers reporting those experiences. There are three identifiable strands under AI in this network: (i) the design, construction and application of reflective architectures; (ii) methodologies for the construction of knowledge bases; (iii) the construction of multi-agent systems. One significant output from this group will be a number of AI programs (classifiers, expert system shells, blackboard systems, and others), which will provide valuable input for the other two topic areas. However, as well as inter-application parallelism, the issue of using them in concert as part of multi-agent systems leads to intra-application parallelism and another kind of exercise for the parallel systems group. Furthermore, the co-existence of a parallel environment and a reflective architecture will lead to the development of at least one new reflective concurrent AI application. Detailed tasks contributing to this topic appear in sections Reflective architectures, Knowledge representation and knowledge bases and Parallel applications.


Rôle of Participants

This network is relying almost entirely on the existing manpower of each partner, therefore the dependencies between tasks are intentionally kept to a minimum and the tasks themselves are designed to be achieved within the framework of the individual research programmes of each partner, but taking advantage of the experience and results of the partners in the network. The primary dependency is between the developers of AI applications to the developers of systems and compilers. This is because the latter will use the outputs from the former to test their systems, but also, the AI developers are keen to use parallelism in developing new systems. Thus, there is a dependency in both directions. Fortunately, both parties have systems that the other can experiment with already, therefore neither need wait for the other to begin.

Although this section is about the rôle of each of the partners, to structure the programme on that axis would obscure the common goals of the groups within the network. In consequence, six specialist subjects within the three gross topic areas of AI, compilation and parallel systems have been identified, and the rôle of a partner within these is described. The partners fall into two categories: those which are active in the specialist area and those which are interested, but unlikely to be able to be participate actively. If there is any dependency between tasks within a specialist subject, the tasks appear in the order in which they must be carried out. The specialist subjects are largely self-contained bar the global dependency noted above-however, this does not imply isolation because of the cross-involvement of the partners in different specialist subjects.

In order to support sharing of and access to partner's codes a NFS/AFS mountable disk will be installed at the University of Southampton which will serve as a repository for the network, with the data possibly being mirrored at other sites. This will greatly assist in avoiding version inconsistency as well as providing a focal point for the partners.


Reflective Architectures

The idea of a reflective architecture is that it can examine itself. This principle is being applied in both AI programs to enable them to examine their reasoning processes and in language design, specifically object systems, in the development of meta-object protocols (MOP) to enable programs to examine (and modify) their state. The active partners are: CEAB, GMD-FIT.KI, Ilog, Pisa, Warwick, Bath, Southampton, INRIA, UPC, URV, VUB.

  1. Analysis of the reflective aspects of Omega (Pisa), KRS (VUB), Babylon (GMD-FIT.KI) to find out the differences and commonalities and subsequently to synthesize a requirements definition for a new reflective architecture (Warwick).

  2. Development of a logic-based semantics to describe reflective systems (CEAB, Pisa, Warwick).

  3. Development of the EuLisp object system and its meta-object protocol through experience of a wider variety of applications (GMD-FIT.KI, Ilog, Warwick).

  4. Applications of reflection (and reification) to task migration, constraint satisfaction, cross-language calling and distributed multi-language client-server programs (Southampton, Bath, INRIA, Ilog).

  5. Applications of reflection on knowledge level models (in components of expertise) for integrated life-cycle support in KBS development, e.g. for knowledge level modeling, validation and verification. (VUB, UPC, URV, Warwick, CEAB)


Knowledge Representation and Knowledge Bases

Although the title is seemingly self-explanatory it is a skilled task, a priori, to choose a representation for the information in a knowledge base, or to determine what information needs to be stored, or how it should be related to other information in the knowledge base. Possible solutions lie in the use of reflective programming languages and in the application of AI to the construction of knowledge bases. Active partners are: CEAB, GMD-FIT.KI, Pisa, UPC, URV, VUB and Warwick. The interested partners are: Bath, GMD-FIRST, Salerno.

  1. Comparison of Omega (Pisa), Milord II (CEAB) and Elektra (Warwick) systems to discover in which ways they differ and in which ways they are the same, then analysis of the approaches to determine advantages and disadvantages (Salerno).

  2. Investigation of the use of Milord II (CEAB) in implementing the ``components of expertise approach'' developed at VUB (UPC, URV).

  3. Definition of requirements for a language well-suited to the components of expertise approach (CEAB, VUB).

  4. Development and application of an object-oriented knowledge representation formalism (GMD-FIT.KI, VUB, Pisa, CEAB, UPC, URV).

  5. Application of new forms of knowledge representation in intelligent tutoring systems (Salerno, GMD-FIT.KI, CEAB, UPC).

  6. Development of a methodology for the automatic generation and validation of knowledge bases from observations (URV, UPC, Pisa, VUB, Warwick).

  7. A workshop on knowledge representation (in conjunction with that on parallelism in AI).


Static Analysis

This term encompasses a large body of techniques for examining the structure of programs or fragments of programs to infer properties which can later be used to optimize the code being generated. This approach is central to the development of delivery systems for Lisp programs in order that only the essential components are included in the runtime. Active partners are: Bath, CNR, GMD-FIRST, Ilog, INRIA, Kiel, Southampton. The interested partners are: GMD-FIT.KI.

  1. Examination of the effectiveness of and subsequent refinement of automatic mapping and dynamic load balancing techniques by application to parallelized versions of existing AI programs (GMD-FIRST, CNR, CEAB, Pisa, UPC).

  2. Examination of the effectiveness of and subsequent refinement of automatic parallelization techniques applied to existing AI programs (GMD-FIRST, CEAB, Pisa, UPC).

  3. Development of a type inference tool for EuLisp to assist in static method selection and total compilation (Bath, GMD-FIT.KI, Kiel, Southampton).

  4. Development of an abstract interpretation tool for EuLisp as a basis for advanced source-level optimizations (Southampton, Bath, Kiel).

  5. Development of a restructuring tool for sequential programs to generate hierarchical task graphs for concurrent execution (CNR, GMD-FIRST).

  6. Comparison of the use of advanced module compilation techniques (Ilog) with static verification techniques (Kiel) with the aim of deriving benefit from their combination.

  7. A workshop on advanced compilation techniques (in conjunction with that on parallel systems).


Semantics and Verification

The distributed Scheme system developed at INRIA has been careful to define a continuation-based semantics for its primitives, while the design of EuLisp has taken a more informal approach. Neither has examined in detail the semantics of object systems, but this is a necessary starting point for the generation of verifiable systems. It must be admitted that, for practical languages, semantics are often a post facto affair, but this does have the advantage that a familiarity with the actual language behaviour helps in the writing of the formal description. This description can then be used to develop a verifiable compilation process for an object-oriented Lisp. Active partners are: Bath, GMD-FIT.KI, INRIA, Kiel, Pisa Southampton. The interested partners are: GMD-FIRST.

  1. Investigation of the implications of parallelism for the techniques employed in total compilation (Kiel, INRIA, Bath, Southampton).

  2. Development of a formal semantics for a concurrent object-oriented Lisp (Bath, INRIA, Kiel, Southampton).

  3. Development of an animator for pi-calculus specification (Southampton, Bath, Pisa).

  4. Application of techniques developed in the ProCoS project to concurrent object oriented programs and the development of a verifiable target abstract machine for the total compilation of concurrent object-oriented programs (Kiel, Southampton, Bath, INRIA).

  5. Application of verified implementation to at least one fair-sized AI program (Kiel, Southampton, Bath, INRIA).


Parallel Models and Systems

As noted in the section on parallel systems, the unifying factor in parallel systems is their diversity. However, it is becoming possible to identify clearly the primitive operations needed for parallel and distributed computation and, at the next level of abstraction, the primitive conceptual models needed for programming such systems. At the next level, the objective is for architecture independence, in which control and data parallelism are merged. Active partners are: Bath, CNR, GMD-FIRST, INRIA, Pisa, Salerno, Southampton. The interested partners are: GMD-FIT.KI.

  1. Comparison of parallel Lisp systems developed at Bath, GMD-FIRST, INRIA, Pisa, Southampton and CNR (i) to identify a set of primitive operations for the implementation of concurrent (distributed) systems; (ii) to construct extensions to support mixed control and data parallel paradigms; (iii) to assess them in the light of practical situations (Salerno).

  2. Comparison of the distributed virtual shared memory (DVSM) systems developed at Bath, GMD-FIRST and CNR and definition of a primitive functional model for DVSM (Southampton, INRIA).

  3. Comparison of the approaches to distributed garbage collection at Bath, GMD-FIRST and INRIA, and investigation of its interaction with DVSM, leading to a model integrating both facilities (CNR, Southampton).

  4. Demonstration of distributed execution of several small and at least one medium-sized Lisp application using nodes at more than one partner site (INRIA, Bath, Pisa, GMD-FIRST, Warwick, Southampton).

  5. Investigation of the requirements for the construction of a real-time implementation of EuLisp for use in the control of autonomous agents (Bath, VUB, Southampton).

  6. Transfer of the results of the language design work into the ISO process for the standardization of Lisp (WG16) (Ilog, Southampton, Bath, GMD-FIT.KI).

  7. A workshop on parallel systems (in conjunction with that on advanced compilation techniques).


Parallel Applications

This topic has two aspects: the parallelization of existing AI codes to improve performance and the development of new ones which exploit parallel techniques. In that sense, it is the simplest to describe, but the practice will be considerably harder. Active partners are: Bath, CEAB, CNR, GMD-FIRST, GMD-FIT.KI, INRIA, UPC, Salerno, Southampton.

  1. Retargetting the data-parallel classification program developed at GMD-FIRST, for the EuLisp environment (Bath), rewriting it to utilize higher level parallel constructs (Bath, CNR) and comparing its capabilities with LINNEO+ (GMD-FIRST, Bath, UPC).

  2. Application of control and data parallel paradigms in existing AI applications (CNR, CEAB, UPC).

  3. Development of a concurrent implementation of LINNEO+ in EuLisp (UPC, Bath) and its application to the classification of marine sponges.

  4. Integration of LINNEO+, Milord II and GAR (UPC, CEAB, URV, INRIA, Bath) and their combined application to problems in urban waste water treatment plants.

  5. Integration of LINNEO+ with the LATIDO (intensive care monitoring) project (UPC, URV, CEAB) as a distributed application.

  6. Performance analysis over distributed systems of and by the LISPSTAT package (Southampton, Bath, GMD-FIRST).

  7. Development of an intelligent tutoring system as a distributed application and its integration with other components, such as Milord II (Salerno, CEAB).

  8. Development of a process enactment environment with application to multiple information servers (multi-media) and distributed working (Southampton, INRIA).

  9. A workshop on the application of parallelism in AI (in conjunction with that on knowledge representation).


Julian Padget: jap@maths.bath.ac.uk