A PVM-based distributed parallel symbolic system

Advances in Engineering Software 28 (1997) 303-312

C 1997 Elsmer Science Limited All rights reserved. Printed in Gnat Britain ELSEVIER

PII:

SO965-9978(97)00017-3

Claudia Di Napoli,* Maurizio

096.5 9978;97/$17.OQ

Giordano & Mario Mango Fumari

Istituto di Cibernetica, C.N.R., Via Toiano, 6 I-80072 Arco Felice, Napoii. Italy

(Received 17 October 1995; accepted 3 1 December 1996) The purpose of this work is to provide a parallel programming environment for symbolic applications suited to run on Distributed Memory Parallei Systems (DMPS). This paper describesthe implementation of such an environment that is based on Sabot’s Paralation model (in particular its LISP implementation, Paralation LISP). In our opinion, the clear distinction between the communication and computation aspectsin the Paralation model allows a clearer and easier exploitation of the opportunities of parallelism in symbolic applications. Furthermore, the simple semantics of its parallel constructs seem well suited to run on a community of loosely coupled LISP interpreters. We chose to implement the Paralation model constructs on the top of the Parallel Virtual Machine (PVM) package becausethis tool allows one to have a cheap virtual distributed memory parallel machine simply by using some LAN interconnected powerful workstations. 0 1997 Elsevier Science Limited. 1 INTRODUCTION

problem-solving applications.“* To deal with the large amount of computation typical of these applications, one viable approach may be distributed computing. Distributed Memory Parallel Systems (DMPS) are currently experiencing renewed interest because they are scalable, cost-effective and capable of high bandwidths, due to the increasing performances of contemporary computer networks. The advent of new architectures with sustained high-speed microprocessors makes the use of DMPS attractive also for symbolic appiications. Therefore, our purpose is to build a unified and userfriendly parallel programming environment, suited to distributed memory parallel architectures, that handles coarse grain parallelism. The system we implemented is based on Sabot’s Paralation model (in particular its LISP implementation, Paralation LISP). The notion of global namespace in LISP is responsible for the intensive work done in implementing parallel extensions of this language on shared memory parallel architectures.3-5 Few extensions have been done for distributed memory parallel architectures, but they seem to keep using an approach based on a “virtually” shared memory. Furthermore, they usually rely on new computational mechanisms to manage the synchronisation in accessing shared data structures.6.7 We think the features of Paralation LISP are suitable to be implemented on distributed memory architectures without affecting the semantics of the basic LISP primitives. In this paper we describe our current research efforts

It is a well-known fact that a large class of problems can be processed efficiently in a multiprocessing setting. In fact, significant advances in designing parallel algorithms and architectures have proved the potential for applying concurrent computation techniques to a wide variety of problems. Today a parallel approach is widely accepted essentially for high-performance numerical processing typical of scientific applications. In the last few years symbolic problems have also been approached in a parallel framework. Parallel symbolic computation seems to be a difficult area, since symbolic applications generally offer several opportunities for small grain parallelism that are extremely irregular and therefore difficult to be “easily” managed by parallel systems. However, an increasing number of symbolic applications suited to be parallelized are emerging every day. In fact, symbolic applications in many AI domains extensively use state-space search procedures, whose complexity depends on potentially large solution spaces to be searched. The solution to a particular problem is usually obtained by composing or comparing different partial solutions. Natural language recognizers, expert systems, vision systems and theorem provers fall in this general class of * e-mail address: (Claudia, maug, mf)@zeus.na.cnr.it 303

C. Di Napoli et al.

304

paralation might be arranged in the form of a threedimensional grid, a ring, a butterfly, a pyramid or even a double ellipse. By default, a paralation has no inherent shape. The shape must be explicitly described by the user. A third kind of locality is the interparalation locality: sites and values in different, unrelated paralations are not necessarily near each other regardless of their indices. The paralation itself is never directly accessible, but only fields can be handled. Two special kinds of operators, associated with this new structure, operate upon the paralation fields. The first one is the elwise construct for carrying out parallel computations; the others are the match and < - (“move”) constructs for communications. The syntax of the parallel elwise construct is:

in developing parallel implementation strategies of Paralation LISP on DMPS. We first give an outline of the Paralation model, pointing out its main characteristics and describing its parallel constructs. Next, we describe the architectural model we refer to and the implementation strategy of Paralation LISP on this architecture. Finally, some experimental results and conclusions are given. 2 THE PARALATION

MODEL

The Paralation model is a parallel computational model developed by Sabots9 It is independent of the hardware architecture, both for system interconnections, and processor types. The central idea is the clear distinction between computation and communication. The basic entity is the new data structure, named paralation, which represents a set of virtual processors, or sites (see Fig. 1). A paralation instance is called a field, a collection of values, one for each site. In other words, the paralation may be viewed as a collection of fields, all with the same size. All the fields belonging to the sameparalation are aligned in the sensethat their ith elements are stored in the same site. This property is called the intrasite locality. A paralation has at least one associated field, named the index field, that enumerates the paralation elements. Paralation sites with nearby indices are not necessarily near each other. The “nearness’ is based upon the concept of paralation shape (intersite locality) that captures the communication costs. Paralation of any shape may be constructed. Thus, the sites of a particular (setq p (make-paralation => IF(0 1 2 3 4)

5))

(elwise (p) (* p 2)) => #F(O 2 4 6 8)

(elwise ()

where < var-list > is a list of symbols, which will be bound to fields given as arguments and belonging to the same paralation, while is the code that will be executed in parallel at each paralation site. The returned value is a new field in the same paralation. An example of elwise computation is given in Fig. 1. The Paralation model assumesa simple synchronization condition: the elwise evaluation terminates and returns its result only after all the paralation sites have finished executing the program

There are no restrictions on the code. This means that the program executed in parallel at each paralation site allows side-effects also on the site’s a paralation and its index field

;; ;:

Creates

;; ;;

computes multiplication and returns the elwise

returns

(elwise (p) '(orange apple pear grape tomato) (elt => #F(ORANGE APPLE PEAR GRAPE TOMATO)

p)))

;; ;; ;;

fields

Fig. 1. Paralation

in parallel field

result

assigns list elements in parallel to the elwise result field

paralation

index field

)

and elwise examples.

PI/M-based distributed parallel symbolic system

paralations according to a mapp&g given as argument, and returns a new field containing the transferred data. If it is necessary to move more than one 8&d value into the same site, a combining j&t&n is used to avoid conflicts reducing the multiple values into a single one. Examplesof match and < - operators are shown in Fig. 2.

values. Nevertheless, there exists a restriction on the side-effects type: since the elwise does not make any guarantee about synchronization between paralation sites as they execute the elwise body, having conflicting side-effects between sites is dejined as an erroneous behaviour. Side-effects may conflict it two or more sites simultaneously read and write the same memory location. The match and < - operators allow communication between the sites of paralations. The match operator accepts two key fields (destination and source) and an optional equality predicate as its arguments; it computes and returns a new object, called mapping, that encapsulates a communication pattern between two paralations by connecting the source paralation sites to the destination paralation sites if their key values are the same. The < - operator moves field values between

3 THE ARCHITECTURAL

MODEL

The architectural model we refer to is essentially composed of a set of independent processing elements (PE), interconnected through a high-speed communication network, and a host whose role is to communicate with the user. Each PE has a local memory, i.e. a memory private to the PE and invisible to the others, and it communicates with the others via a message-passing paradigm (see Fig. 3).

(setq map (match f2 fl)) => #SWAPPING #F(O 1 2 NIL 3 2) :TO-KEY-FIELD :FROM-KEY-FIELD #F(NIL 0 2 3 NIL 0 1))

field

305

;; ;; ;;

computes and returns a mapping between two fields

fl field

f2

mapping (setq def-field => #F(NO-VALUE

:; ;:

‘no-value))

:by map :with '+ :default def-field) => XF(6 6 2 NO-VALUE 3 2) (