gdheinze@medusainformatik.uni-erlangen.de (Gerhard Heinzel ) (12/17/90)
In the Proceedings of the ICPP 1990 I found a very interesting paper suggesting that programs based on message passing are more efficient than those based on shared memory - even on shared memory architectures. The authors were very cautious about their results and suggested a broader study with more machine types and programs. Is anyone working on this ? Are there any intermediate results yet ? Looking forward for a fruitful discussion, Yours Gerhard Heinzel P.S.: the reference: %z InProceedings %K %A Calvin Lin %A Lawrence Snyder %T A Comparison of Programming Models for Shared Memory Multiprocessors %C International Conference on Parallel Processing 1990 %c 1990 %V II %P 163 170
roland@sics.se (Roland Karlsson) (12/18/90)
Hi Gerhard, > In the Proceedings of the ICPP 1990 I found a very interesting paper > suggesting that programs based on message passing are more efficient > than those based on shared memory - even on shared memory > architectures. I hope that neither you nor the authors in the article get offended, but this is nonsense. I assume you have simplified the results from the article. You can not compare two different ways of implementation without knowing what to implement. I have seen several examples of programs that have been improved when moved from a loosely coupled machine to a shared memory machine. The usual trick is to replace message passing with direct access of other processes memory. There are lots of references in the area of parallel simulation. Here is one: "Time Warp on a Shared Memory Multiprocessor - Richard M. Fujimoto - Technical report - CSD - University of Utah". One more example: I am working on a very efficient implementation of Or-parallel Prolog. There is no way of doing this, with the same efficiency, with message passing. There are no messages to transmit. The Or-parallel branches are independent but reuse already created (read: lots of) data. Message passing is a very appropriate method for many applications. The main advantage is the possibility to create issolated objects. This simplifies the design task. But efficiency on a shared memory multiprocessor is not the main issue. -- Roland Karlsson SICS, PO Box 1263, S-164 28 KISTA, SWEDEN Internet: roland@sics.se Tel: +46 8 752 15 40 Ttx: 812 61 54 SICS S Fax: +46 8 751 72 30
gdheinze@medusainformatik.uni-erlangen.de (Gerhard Heinzel ) (12/20/90)
My intention in posting this reference was to generate interest in the paper. Therefore I did not summarize it but gave an (exaggerated) impression of what I read from it. Let me just correct a few misunderstandings: - the authors do not state that message passing is better in all cases, instead they suggest, more studies are done on this subject - they experimented with two different parallel machines an two sample problems of (numerical) parallel problems (one of which was matrix multiplication) Gerhard
linc@cs.washington.edu (Calvin Lin) (01/18/91)
>From: roland@sics.se (Roland Karlsson) > Hi Gerhard, > > > In the Proceedings of the ICPP 1990 I found a very interesting paper > > suggesting that programs based on message passing are more efficient > > than those based on shared memory - even on shared memory > > architectures. > > Is anyone working on this ? Are there any intermediate results yet ? As far as we know, there has not been any further work in this area. > > I hope that neither you nor the authors in the article get offended, > but this is nonsense. I assume you have simplified the results from > the article. You can not compare two different ways of implementation > without knowing what to implement. I have seen several examples of > programs that have been improved when moved from a loosely coupled > machine to a shared memory machine. The usual trick is to replace > message passing with direct access of other processes memory. There No, we're not offended, but we'd like to point out that what you've stated does not contradict our work. Our paper does not compare the performance of a message-passing program on a loosely coupled machine against the performance of a similar program on a shared memory machine. Rather, we are interested in comparing the performance of a program written in the non-shared memory model with that of a shared memory program, both executing on the same machine. > ... One more > example: I am working on a very efficient implementation of > Or-parallel Prolog. There is no way of doing this, with the same > efficiency, with message passing. ... Just to set the record straight, our paper does not claim that any one model is superior for all applications. Calvin Lin linc@cs.washington.edu
baude@aar.alcatel-alsthom.fr (Francoise Baude) (01/21/91)
I have demonstrated that shared memory parallel programming model (represented by PRAMs) is almost equivalent to the message passing parallel programming model (represented by Actors) with the point of view of expressiveness and efficiency (product of parallel time and number of processors used). 'Almost' means that a O(log N) inneficiency factor, due to asynchronicity and distribution of message passing model, is unavoidable when you simulate a PRAM program by an Actor program. On the other side, the efficiency is constant when you simulate a PRAM program by an Actor program, because a O(log N) increase in parallel time is unavoidable but you can use less processors (in an order of magnitude of O(log N)). The comparisons of the two kinds of models are made by assuming the SAME underlying architecture (i.e. extendible, message passing, asynchronous, processors network) on which a unique universal 'Von Neuman' like execution model can be build for any parallel programming model. An article entitled 'Actors as a Parallel Programming Model' will appear in the 8th STACS proceedings, LNCS, in February 1990. If you are interested, I can send you a copy before the publication. Francoise Baude email: baude@aar.alcatel-alsthom.fr