Distributed Shared Environments for Concurrent ML

Case for Support

Abstract

We will evaluate a new programming model for parallel computation, suggested by developments in language design. In place of a memory model, we propose a high-level view based on an environment providing access to a collection of abstract, structured data-values. Processes communicate (names of) arbitrary values via strongly-typed, dynamically created channels. Communication of complex values is implemented as “lazy” (ie. demand-driven) communication of pointers. Static analysis of source code is used to distinguish between mutable and immutable (read-only) values. We will exploit this distinction to determine when coherence between multiple copies of a value is automatic. Processes are first-class values, and may be passed to other processes for execution. Strategies for process placement and process migration will be evaluated. If successful, our approach will provide a practical route for the implementation of new parallel applications and suggest topics for further research.

1 Background

The most promising highly parallel architectures for general purpose computation are currently distributed memory MIMD machines with fixed communication topology. However, because of the lack of a uniform, tractable programming model, it has proved difficult to program such machines. Other workers have provided facilities for explicit annotations to declare the memory access class of a variable. We propose the implementation of a distributed memory that will support languages that combine static inference of such access classes with pointer-based recursive data structures and garbage collection. Our proposal provides a new perspective that evades some known problems.

1.1 Parallel Programming Models

Various groups have considered automated extraction of implicit parallelism from functional code [?, ?]. These approaches have failed to yield a general solution. Imperative languages poses further major challenges in dependency analysis [?]. The limitations of automatic parallelization lead us to consider languages providing explicit parallelism; the programmer is made responsible for defining processes which execute in parallel. An abstract programming model is needed, for portability, and because asynchronous parallel code is error-prone and almost impossible to debug.

Message Passing A message-passing model, formalized in calculi such as CSP [?] and CCS [?] corresponds closely to currently realisable massively parallel hardware. Data objects are local to processes, and the programmer must implement, using message-passing, any data-sharing that is required by the application. This model, which forms the basis of occam, has not provided a sufficiently abstract view; the user has to be aware of, and adapt to, the physical connectivity of the network and the granularity of communication provided by the hardware. Furthermore, all communication patterns must be statically specified.

The majority of message-passing systems today (e.g. CS Tools[?]) provide a higher-level model than occam. The programmer is typically presented with arbitrary point-to-point message-passing functionality. He need not explicitly construct networks of channels over which messages are passed, or the routing of these messages. This abstraction from physical connectivity greatly reduces the effort needed to program message-passing applications, allows dynamically specified communication patterns, and can lead to greater portability. However, the types of message that can be passed are limited. Furthermore, there is usually a flat name space in the communications environment. This lack of scoping of communications end-points makes it difficult to write correct code, and again leads to difficulties in the composition and reuse of code.

Shared Memory Much current research in parallel computation attempts to provide a shared-memory model for programming distributed memory MIMD hardware. In a simple shared memory model all data locations are considered shared. The programmer is responsible for implementing synchronization between processes to ensure the correct ordering of updates to shared data, and for the representation and management of complex data values. Different proposals vary in implementation detail and, more importantly, in the programming model they provide. Munin[?], for example, allows the programmer to restrict patterns of memory access, and exploits these restrictions. Bulk synchronous parallelism provides another promising approach.

Shared memory models are expensive to implement on distributed memory architectures. This is primarily because of the need to ensure coherence between different processes’ views of the content of the abstract shared memory as it is updated. Our proposal will complement this existing work by exploiting highlevel information about access class and data representation.

2 Research Programme

This proposal is motivated by the need to develop, run and maintain applications on parallel hardware. We believe that our approach will provide

• better support for developing and maintaining parallel applications, and

• new trade-offs that can be exploited to engineer an efficient implementation.

2.1 The Model

The programming model provides shared data, and asynchronous communication over channels; these are both abstracted from the hardware to a greater extent than in previous proposals. The model corresponds closely to a typed version of Milner’s π-calculus [?, ?].

The programmer deals with values instead of storage locations. Data consists of values of arbitrary types. The programmer is provided with the ability to name values. A collection of bindings of names to values is called an “environment”, so, to emphasize the difference in level of abstraction, we call this data model ‘shared environments’. Updatable values are represented explicitly as values of a special type.

The concurrency mechanism allows for the creation of light-weight processes which communicate via dynamically-created, strongly-typed channels. Channels are seen as a mechanism by which names can be shared, rather than as a mechanism for transferring data. They are used to pass names (and their meanings) between different processes. Call-by-value semantics ensures that this is indistinguishable from passing values.

Channels and processes are first class objects. This allows the programmer to express explicit process placement and migration.

2.2 Goals

We will evaluate the utility of this model as a basis for programming closecoupled MIMD hardware, and draw conclusions that may influence future language designs.

2.3 Implementation

Our proposal relies on a type system to ensure that objects of a particular type have an invariant structure, and to statically determine which objects may be updated. This was prompted by the type system of ML, an established language with advanced support for abstraction and programming in the large and wellunderstood semantics. [?]. Concurrent ML, an extension integrating abstract versions of message passing and shared memory, has been formally defined [?], and several implementations, based on the Poly/ML compiler, prototyped [?]. We propose to use Concurrent ML as the basis for our investigation.

In Concurrent ML channels and processes are first-class objects. Therefore, we can use ML modules and higher-order functions to provide software tools for concurrent programming. Information available at compile time, from the type system, provides opportunities for optimisation in implementing the abstract view of channels and memory. We will investigate the implementation of these optimisations, and the degree to which they can be exploited for various applications.

Poly/ML Concurrency primitives were added to Poly/ML to provide a mechanism for handling asynchronous events in a window system. This system was later ported to the Firefly shared-memory multiprocessor. There is already a basic implementation of Distributed Concurrent ML running on a local area network of RISC processors [?], and a prototype port to the more tightly-coupled Meiko system is almost complete. In each case the semantics of the concurrency primitives is unchanged.

Much of the implementation effort is closely linked to the systems aspects of our research and involves exploring trade-offs. This can only be done once a prototype is in place and there are representative applications available for testing. Most of the implementation effort will be directed at exploring alternative strategies for message passing (passing complex values introduces subtleties, since not all of the value need be communicated in one go) and garbage collection, and instrumenting the implementation so that we can draw general conclusions about performance. We will also use this information in the development of strategies for process placement and, if necessary, process migration.

Shared Environments The run-time system of an ML compiler can rely on a distinction between mutable and immutable objects; for most programs the vast majority of objects are immutable, and the programmer can (by adopting a functional style) ensure this. The predominance of immutable objects has long been exploited by ML garbage collectors [?].

We propose to exploit this distinction in our implementation of shared environments. If a data structure containing a mutable is shared between two processes they can both update it and should both have a coherent view of the changes. For shared immutables this is unneccessary, so the implementation can be optimised. The prototype network distributed implementation already exploits this property, using an extension of Matthews’ successful implementation of persistent store [?].

Name Passing Passing a complex object as a message can be implemented by passing its name. However, the structure of values is known at compile time, so pointers can be followed to transfer the whole object in a single communication. Between these extremes, we can transfer some part of the object, leaving the rest to follow automatically if and when it is referenced by the receiving process.

Our proposal is closely related to shared memory models. We will explore the optimizations allowed by static analysis of patterns of access in a predominantly functional setting, and exploit strong typing to allow communication of complex data values to be tuned to particular hardware in a transparent way. Programming in a functional style will reduce the coherency problems, but we will have to use existing work on shared memory to provide an efficient distributed implementation of mutables. Furthermore, the coherency problem is replaced by the need for distributed garbage collection.

Garbage Collection An applicative style of programming puts responsibility for storage management onto the garbage collector. The present prototype has a garbage collector which manages data structures which are entirely local to a machine. Objects which have been exported to or imported from another machine are currently not garbage collected. It will be necessary to devise a scheme for handling this. It is likely that different schemes will be appropriate for mutable and immutable objects. We anticipate that LeSergent from LAAS, Toulouse, who has worked on distributed garbage collection, will be working at Edinburgh during this project, and we will be able to draw on his experience.

Process Placement and Process Migration The existing concurrency primitives provide high level abstractions for concurrency and communication. They do not, however, provide any mechanism for the user to place a process on a given processor. We will provide primitives which afford the programmer control over process placement and migration. In designing such an interface it is important to provide the programmer with access to sufficient information to exploit this control. It is equally important to provide a machine-independent interface to these facilities. The primitives might not be available to users of the system but could be of use within modules which implement various communications abstractions.

Although process placement has no effect on the functional behaviour of a parallel program it can, depending upon the characteristics of the application and the platform on which it is running, have quite drastic effects on performance. Responsibility for process placement can be divided between the system and the programmer in several ways. We will evaluate a number of alternatives, and investigate system-controlled process placement and migration policies.

2.4 Foundations

Language Design The ability to distinguish mutable and immutable objects by static analysis is a straightforward consequence of the Hindley-Milner-Tofte type system. We will investigate the static analysis of other classes that may provide the basis for further optimisations — for example, single update and single reference. The implementation of our memory model will suggest other optimisations. We will explore the implications for new forms of static analysis and future language designs. This work will be of interest to a wider community including the designers of future languages for concurrent systems.

2.5 Parallel Applications

We intend that implementation work under this heading will be done as postgraduate student projects. Support is not requested for this work. However, we describe it in some detail here as feedback from users is essential in evaluating the success of the approach.

We propose to investigate the utility of our paradigm using application-based case studies. These will involve both direct implementation of specific applications, and the definition of a tool-kit of common patterns of parallel computation. We will work closely with Todd Heywood and Murray Cole (both lecturers at Edinburgh) who are investigating such tool-kits under other projects.

Clichés Existing parallel applications suggest a number of programming clichés — structures of communication and parallelism that appear repeatedly in different applications. Implementation of these must be optimized to best exploit the resources provided by a given platform — for example, by tuning the placement or migration of processes and the degree of parallelism created. The module system of Concurrent ML provides a basis for expression of such structures as reusable code, and a framework for controlled experimentation with such high-level optimisations. We are interested in determining what run-time information a module requires in order to configure itself most effectively on a particular platform, and understanding how this information can be represented and provided by the system. We will investigate both dynamic and static optimisations.

Algorithms Our scheme allows shared distributed memory to be optimized for functional code. Increasing the number of objects which can be recognised as immutable through this static analysis can significantly reduce the number of data items whose consistency needs to be maintained. This allows the user to trade-off updating for garbage collecting. Exploring this trade-off for particular applications will lead to new algorithms which may reap substantial performance benefits, and should provide general conclusions.

3 Related Work

The relationship of functional languages and concurrency has been explored from a number of different perspectives and is an active area of research. PFL [?] is an extension of an earlier version of ML with concurrency primitives and has been implemented on a uniprocessor. Reppy [?] has provided an alternative set of concurrency primitives for Standard ML. Facile [?] is a small language similar to ML but with concurrency built in. This work is particularly concerned with implementation on a distributed network.

Our proposal concerns the interplay between Language Design and Parallel Systems; Edinburgh has a strong record in both. The Edinburgh Parallel Computing Centre and its precursors have been at the forefront of the application of parallel computing in Europe, and have had extensive experience of parallel applications over the past decade. The EPCC will provide access to hardware, and expertise in both applications and implementation. We will maintain close links with the EPCC ‘Parallel Utility Libraries’ (PUL) project. The Laboratory for Foundations of Computer Science is a major international centre for theoretical computer science, and has made fundamental contributions to the development of ML, and to the foundations of concurrency. This project relates closely to current work on Declarative Languages, and on the Foundations of Concurrency. We will work closely with these groups. This project will draw from the experiences of EPCC and LFCS, contribute to their current research activities, and strenghten the links between them.

4 Project Management and Resourcing

Academic direction for this project will be provided by Professor Michael Fourman, a co-Director of the LFCS, and director of Abstract Hardware Limited who has been influential in the widespread adoption of ML, Profesor Roland Ibbett, Associate Director of EPCC, and Dr. Kevin Mitchell lecturer in Computer Science and implementor an early version of Concurrent ML. In particular Mitchell will work on many of the foundations issues described in this proposal. We request part-time support for David Matthews, the designer and implementer of the Poly/ML system. His input is crucial to the project. We request support for one RA (for two years on the 1A scale) ideally with 2 years with research experience in language implementation and parallel computing, to tackle the “Parallel Applications” aspects of our research goals. EPCC will provide access to parallel computing facilities. In addition, well configured workstations are required (1 per FTE) for systems development work. Network infrastructure will be provided by the LFCS. However, this project demands the use of a novel environment and non-routine access to the concurrent hardware. Therefore, during the critical implementation period (months 6 to 18) we request 33% support for a Computing Officer to provide the specialised support required. General system management and backup technical support will be provided from existing departmental resources.

Travel It is important that we keep abreast of developments in parallel software environments, architectures and applications. We have good links within Europe. It is important that we learn from the experience of the USA, so that we may apply our ideas to advantage. We know of several projects in related areas and request support for travel and subsistence to develop and maintain links, both within the UK, (eg. Southampton, Imperial, Manchester, Oxford), in Europe (eg. ECRC Munich, INRIA/IRISA) and the USA (eg. New York University, CMU, Cornell, CalTech, Syracuse).

The time-lag of journal publications makes conferences and workshops the primary route for dissemination of results in this area. These include the following conferences: PARLE, POPL, ACM Symposium on Principles of Distributed Computing, ACM Conference on LISP and Functional Programming, International Conference on Software Engineering, International Conference on Computer Languages, ASPLOS International Conference on Architectural Support for Programming Languages and Operational Systems, Symposium on the Frontiers of Massively Parallel Computing, International Symposium on Programming Language Implementation and Logic Programming, CONPAR Conference on Parallel Architecture, European Workshop on Parallel Computing, Conferences and Workshops organised by IFIP Working Group 10.3. We request support to attend a selection of Conferences from this list.

5 Exploitation

Background The Intellectual Property Rights in the ML compiler on which we will base our work belong to Lynxsvale Ltd and have been licensed to Abstract Hardware Ltd for support and marketing. IPR in the run-time system for Concurrent ML also belongs to Lynxsvale, but this is not a commercial product, and has been licensed to Edinburgh for research and development use. (Abstract Hardware Ltd’s Poly/ML run-time system is entirely different.) The major results of this project will be published as technical reports, presented at workshops and conferences and submitted for Journal publication. This knowledge will be in the public domain. We also intend to provide a short series of seminars for colleagues supporting applications work in the EPCC.

We are aware of three companies developing or marketing commercial ML systems, Harlequin Ltd, Abstract Hardware Ltd, and Integral Solutions Ltd, and are eager to encourage downstream use of our results. We therefore envisage the possibility of providing consultation for companies wishing to develop products based on our results, for commercial exploitation. However, we believe that it will require substantial development effort to integrate our results with any commercial ML compiler.