hshi@maytag.waterloo.edu (12/12/90)
A naive question: We have two parallel programming models: shared memory model via shared variables and distributed memory model via message passing. Is there any model which is some where between? Will it be more suitable for the persent comptuter architectures?
zenith@ensmp.fr (Steven Ericsson-Zenith) (12/13/90)
>A naive question: > We have two parallel programming models: shared memory model via >shared variables and distributed memory model via message passing. >Is there any model which is some where between? Will it be more suitable >for the persent comptuter architectures? There is the Ease model which combines both and is efficient to implement on machines of both architectures. For example, if you tried to implement message passing on a shared memory machine you would suffer a copy penalty - the reason many parallel programs appear to run slower than expected :-). Implementing shared memory (single global space) architecture over distributed memory machines is complicated by the determination of locality. Ease provides a solution which allows processes to interact via well defined non-local spaces/scopes. The copy penalty is circumvented and locality is clearly expressed. Reference Yale University Research Report RR809, July 1990. "Programming with Ease: a semiotic definition of the language" by Steven Ericsson Zenith Contact Chris Hatchell at Yale (hatchell@cs.yale.edu) for a copy or send me your full address and I'll add you to the Ease mailing list. The Ease Project is now located at Ecole des Mines de Paris. -- Steven Ericsson Zenith * email: zenith@ensmp.fr * fax: (1).64.69.47.09 | | voice: (1).64.69.48.52 Ecole Nationale Superieure des Mines de Paris 35 Rue Saint-Honore 77305 Fontainebleau Cedex France "All see beauty as beauty only because they see ugliness" LaoTzu
ciancarini-paolo@CS.YALE.EDU (paolo ciancarini) (12/13/90)
In article <12221@hubcap.clemson.edu> hshi@maytag.waterloo.edu writes: >A naive question: > We have two parallel programming models: shared memory model via >shared variables and distributed memory model via message passing. >Is there any model which is some where between? Will it be more suitable >for the persent comptuter architectures? A naive answer: >From a linguistic point of view, "Infinite systems exist" (Dedekind). :) More seriously, I would say that Linda'a Generative communication through a Tuple Space is different from both. I believe that the Tuple Space model, that can be called also the blackboard model because it shares many interesting features with this architectural paradigm for AI applications, is NEITHER a msg passing model, because agents do not know about each other and the Tuple Space is Shared and communications are associative, NOR a shared memory model because agents do not shared variables or a global environment (in fact, for Linda exist both shared memory implementations and distributed memory implementations, but this is another issue). >From a semantic point of view, however, it seems to me that we have only two models: the CCS interleaving model and the Petri Net distributed model. It is unclear to me if does exist a third basic model in the sense that Linda seems to be basically different from shared memory and msg passing. Maybe the Chemical Abstract Machine could be the basis for such a third model. By the way, the CHAM has many features in common with Linda. Paolo Ciancarini Universita' di Pisa and Yale Computer Science Dept.
zenith@ensmp.fr (Steven Ericsson-Zenith) (12/14/90)
From: ciancarini-paolo@CS.YALE.EDU (paolo ciancarini) Subject: Re: parallel programming model In article <12221@hubcap.clemson.edu> hshi@maytag.waterloo.edu writes: >A naive question: > We have two parallel programming models: shared memory model via >shared variables and distributed memory model via message passing. >Is there any model which is some where between? Will it be more suitable >for the persent comptuter architectures? A naive answer: >From a linguistic point of view, "Infinite systems exist" (Dedekind). :) More seriously, I would say that Linda'a Generative communication through a Tuple Space is different from both. I can't agree with you here Paolo. In the Linda model processes interact via the global associative memory of Tuple Space. In a shared memory model processes interact via an addressable global space. In message passing processes interact via shared objects (which in some forms are dynamically addressable) called "channels" or "mailboxes" or somesuch. The behavioral characteristics may differ but what we have here are essentially variants of the same model - the persistent nature of the intermediary objects being the significant disinquishing characteristic. Another distinquishing feature of these variants is that in addition to the synchronization characteristics of the means by which processes "communicate", processes may interact via some distinct synchronization. For example, in the message passing model, epitomised by CSP, processes combined by a parallel sychronize when all the components of the parallel have terminated. In Linda the programmer must "coordinate" his programs via interactions with Tuple Space. It would seem desirable to have all process interactions defined by the associated "interaction model". As things stand in Linda processes are able to side-effect each other directly, i.e. outside of the tuple space model -- at least this is the case for the Yale C-Linda model. The process model in Linda is vague to say the least, with the semantics of process creation varying according to implementation. Linda's distinquishing characteristic is "value associative matching", which amounts to complex address translation in a global shared memory - this turns out to be an operation with unpredictable performance characteristics. For example, in the case of the Linda optimizer, write a Linda program or Linda-ize an existing C code. You cannot predict the performance of the program, and you will not know the performance until the task is complete - any imperical analysis you perform at any point in the development will likely be invalidated by subsequent changes to the program since the optimizer will almost certainly change stategy as you add new tuple types. Ok, so you learn everything there is to know about the optimizer - now you have subverted portability. Most "successful" Linda programs are either written within a few feet of the implementor of the optimizer or are so parallel and have such granularity that the Linda overhead disappears into insignificance and in such cases pretty much any model would do (e.g. a decent system of batch files with native job control language, and "sockets" is likely to do as well - maybe better - than any network distributed version of Linda, for as much effort). is NEITHER a msg passing model, because agents do not know about each other Well "agents" "know" about Tuple space and also must "know" about data structure and type. This is directly analogous to a "knowledge" of communication channels, mail boxes and protocols in message passing. and the Tuple Space is Shared and communications are associative, NOR a shared memory model because agents do not shared variables or a global environment (in fact, for Linda exist both shared memory implementations and distributed memory implementations, but this is another issue). Again, Tuple Space epitomises a "global environment" and in current implementations I've seen at Yale "agents" may indeed share variables .. I've already indicated that I view side effecting processes as undesirable. >From a semantic point of view, however, it seems to me that we have only two models: the CCS interleaving model and the Petri Net distributed model. It is unclear to me if does exist a third basic model in the sense that Linda seems to be basically different from shared memory and msg passing. Sorry Paolo, maybe it is your English I'm having trouble with, since you seem to be contradicting yourself here. I hope my view here is clear. Linda is a variant of a model I have come to call the "interacting process model"(nee MIMD), members of this model are distinquished by an associated "interaction model" which captures the means by which processes "communicate" and "synchronize" (in this sense Occam, Linda and indeed Ease are members of the Interacting Process Model). Steven -- Steven Ericsson Zenith * email: zenith@ensmp.fr * fax: (1).64.69.47.09 | | voice: (1).64.69.48.52 Ecole Nationale Superieure des Mines de Paris 35 Rue Saint-Honore 77305 Fontainebleau Cedex France "All see beauty as beauty only because they see ugliness" LaoTzu
ciancarini-paolo@CS.YALE.EDU (paolo ciancarini) (12/14/90)
In article <12242@hubcap.clemson.edu> zenith@ensmp.fr (Steven Ericsson-Zenith) writes: > (answering this statement of mine:) > More seriously, I would say that Linda'a Generative communication > through a Tuple Space is different from both. > >I can't agree with you here Paolo. In the Linda model processes interact >via the global associative memory of Tuple Space. In a shared memory >model processes interact via an addressable global space. When a discussion starts, is always useful to define terms. I will use your definitions. A global associative memory is NOT a global addressable memory. Normally an address is a name denoting a state. And a state should be something that I can see as a whole in an arbitrary point of time. Where are addresses in the Tuple Space? An associative memory has different properties from an addressable memory, especially from the point of view of parallelism; for instance, how can be you sure that a tuple is NOT contained in the Tuple Space? Which address are you going to look into? >In message passing processes interact via shared objects (which in some forms are >dynamically addressable) called "channels" or "mailboxes" or somesuch. >The behavioral characteristics may differ but what we have here are >essentially variants of the same model - the persistent nature of the >intermediary objects being the significant disinquishing characteristic. > So maybe YOU are self-contradictory! What do you think of the persistent nature of tuples in Linda? are they messages? Is Linda a msg oriented model? >It would seem desirable to have all process interactions defined by the >associated "interaction model". Again, we need to define a term: model. I believe that both you and I are using this word in two meanings, when speaking of programming paradigms and languages: 1) a model is a concrete implementation of a language (its run-time system); 2) a model is a semantic paradigm, i.e. an abstract framework and maybe a general formalism to specify abstract machines (i.e. operational semantics for programming languages).. I do not know what is the "interaction model" you are speaking about. I interpret it in the sense of 2). I know only two major semantic paradigms for parallelism: interleaving semantics (as given originally by Milner for CCS) and "truly distributed" semantics (as in Petri Nets). They seem very different to me, and by the way they can be used to characterize very different (abstract or concrete) implementations of the same language. Literature on this argument is growing. If interested, I can send you a paper by D.Yankelevich and myself on Linda formal semantics given in terms of Petri Nets, by translation in CCS, using the Chemical Abstract Machine, using Plotkin's SOS (this comes in two flavors: interleaving and truly distributed). > >Linda's distinquishing characteristic is "value associative matching", >which amounts to complex address translation in a global shared memory - This is an implementation issue, of course, and by the way in a very different context it is a feature of Prolog implementations based on WAM (so this is hardly "Linda's distinquishing characteristic"). The Linda global shared memory could be distributed; its consistency then should be maintained. I can send you a paper also about this, if interested. >i (e.g. a decent system of >batch files with native job control language, and "sockets" is likely to >do as well - maybe better - than any network distributed version of >Linda, for as much effort). > This is a statement that should be demonstred. My experiences with sockets and the Unix "job control language" when used for implementing a distributed runtime system across a network are quite discouraging. On the other side, some recent results obtained with Network Linda are astonishing (if you need more details, please ask). > >Well "agents" "know" about Tuple space and also must "know" about data >structure and type. This is directly analogous to a "knowledge" of >communication channels, mail boxes and protocols in message passing. > No. (I presume you are again speaking of semantic issues). Agents do not know about their Tuple Space. For instance, they CANNOT consume the entire tuple space - this is simply impossible in the abstract model. Actually the same concept of Tuple Space "state" is an empty concept, because in a truly distributed implementation you cannot take a snapshot of such a beast. > >Again, Tuple Space epitomises a "global environment" and in current >implementations I've seen at Yale "agents" may indeed share variables .. >I've already indicated that I view side effecting processes as >undesirable. > I am not aware of the implementations you are speaking about. In the pure Linda model, that is our argument of discussion, agents do not share variables. Period. (I agree that side effects are undesirable; this is not an issue). >Linda is a variant of a model I have come to call the "interacting >process model"(nee MIMD), members of this model are distinquished by an >associated "interaction model" which captures the means by which >processes "communicate" and "synchronize" (in this sense Occam, Linda >and indeed Ease are members of the Interacting Process Model). > Are you speaking about implementations again, or about semantic paradigms? Any reference to this "interacting process model"? Can I give semantics to Linda, or Ada, or Occam using this paradigm? Which is its relationship to more established abstract frameworks? Paolo Ciancarini Universita' di Pisa (Italy) and Yale University (USA)
eugene@nas.nasa.gov (Eugene N. Miya) (12/14/90)
I find this discussion all amusing.
I refer all comp.parallel readers to the latest issue of IEEE Computer.
First article. Read it. Look at Table 1. I think all discussants
are in the two categries. I plan to reproduce the table in the biblio
entry for the citation of this paper.
--e. nobuo miya, NASA Ames Research Center, eugene@orville.nas.nasa.gov
{uunet,mailrus,other gateways}!ames!eugeneig@uunet.UU.NET (Iain Bason) (12/16/90)
In article <12242@hubcap.clemson.edu> zenith@ensmp.fr (Steven Ericsson-Zenith) writes: > > From: ciancarini-paolo@CS.YALE.EDU (paolo ciancarini) > Subject: Re: parallel programming model > > In article <12221@hubcap.clemson.edu> hshi@maytag.waterloo.edu writes: > >A naive question: > > We have two parallel programming models: shared memory model via > >shared variables and distributed memory model via message passing. > >Is there any model which is some where between? Will it be more suitable > >for the persent comptuter architectures? > > A naive answer: > >From a linguistic point of view, "Infinite systems exist" (Dedekind). :) > > More seriously, I would say that Linda'a Generative communication > through a Tuple Space is different from both. > >I can't agree with you here Paolo. In the Linda model processes interact >via the global associative memory of Tuple Space. In a shared memory >model processes interact via an addressable global space. In message >passing processes interact via shared objects (which in some forms are >dynamically addressable) called "channels" or "mailboxes" or somesuch. >The behavioral characteristics may differ but what we have here are >essentially variants of the same model - the persistent nature of the >intermediary objects being the significant disinquishing characteristic. I don't see the point of this argument. The original poster was looking for a model "somewhere between" message passing and shared memory. You seem to be saying that message passing and shared memory are the same thing at some level, although I'm not sure what level you're referring to (perhaps that they both share data between processors?). In fact, Von Neumann machines and parallel processors are the same at some level (e.g., they are both digital computers). These facts don't help answer the question. >[stuff deleted] > > > is NEITHER a msg passing model, because agents do not know > about each other > >Well "agents" "know" about Tuple space and also must "know" about data >structure and type. This is directly analogous to a "knowledge" of >communication channels, mail boxes and protocols in message passing. > I don't see the point of this argument either. This "knowledge" is also directly analogous to a "knowledge" of shared memory addresses and data structures. >[stuff deleted] > >I hope my view here is clear. >Linda is a variant of a model I have come to call the "interacting >process model"(nee MIMD), members of this model are distinquished by an >associated "interaction model" which captures the means by which >processes "communicate" and "synchronize" (in this sense Occam, Linda >and indeed Ease are members of the Interacting Process Model). That seems like a reasonable point of view. I think shared memory parallelism also falls into an "interacting process model". Of course, I'm just trying to extrapolate a reasonable definition from the name "interacting process model". You may have a different definition. However, I think the original question asks us to distinguish between various sub-models of the interacting process model. If we examine the differences between shared memory and message passing, I think it is clear that Linda falls somewhere between the two. Are you trying to say that any parallel algorithm can be coded with equal ease in Occam, Linda or Ease? How about shared memory? How about sockets and daemons? How about remote procedure calls? I think you raised some interesting questions about how the implementation of a Linda system affects the design of Linda programs (I deleted that paragraph -- sorry). The performance of a parallel program is obviously going to depend upon the efficiency of the system services it relies on. In the case of Linda, the speed some of those services is strongly affected by the quality of software (e.g., can the programming tools optimize tuple space transactions into semaphores or message queues). However, any portable parallel programming model has to deal the with the strengths and weaknesses of hardware. Different hardware systems have different ratios of communication capacity to computation capacity. Many programs are going to have to decide whether to waste computation or communication (just as many serial programs have to decide whether to waste computation or memory). A balance that is appropriate for a shared memory machine probably will not be appropriate for a network of workstations, and vice versa. As a result, the program cannot be portable unless the balance can easily be changed. Ultimately, we have to choose whether the decision on where to strike the balance should be made by the programmer or the programming tools. -- Iain Bason ..uunet!caliban!ig
pratt@cs.stanford.edu (12/18/90)
From: caliban!ig@uunet.UU.NET (Iain Bason) I don't see the point of this argument. The original poster was... ... In fact, Von Neumann machines and parallel processors are the same at some level (e.g., they are both digital computers). I don't see the point of this argument in this context. The effect of levels on complexity is conjunctive: if all levels save one are distributed and that one is shared memory, and the shared memory turns out to be a bottleneck, then it kills your performance no matter how fast the other levels are. At the level at which Von Neumann machines and parallel computers are the same, both are distributed. The discussion was whether a particular level was distributed or centralized (i.e. von Neumann). Assuming this is the only level that hasn't yet committed to distributed, that's the only level that pertains to the discussion. Protocol implementations that mistake protocol levels for an implementation guideline instead of merely a way of structuring the semantics take a big performance hit due to this conjunctiveness of per-level computational complexity: every level slows you down a little bit more. If *any* level of Internet were implemented by looking things up over at NIC per packet it would slow you down a *lot* more. However it would not impact the main purpose of networking, which is not performance but rather simply to spare people the inconvenience, cost, and unreliability of moving data around on magnetic tapes and other portable media. Great performance is great, but not as great as convenience, economy, reliability, or sex. Vaughan Pratt
pratt@cs.stanford.edu (Vaughan Pratt) (12/18/90)
From: Vaughan Pratt <pratt@cs.stanford.edu> However it would not impact the main purpose of networking, which is not performance but rather simply to spare people the inconvenience, cost, and unreliability of moving data around on magnetic tapes Hmm, that isn't quite right. Let me add interactive computing (but that's a fine example of an application for which convenience, economy, and reliability are higher priority for many people than performance), and also replace "main" by "original." Hope that nips a few if not all flames in the bud. Note that I'm not saying people don't want performance, they do (I do). For example links with higher throughput facilitate interactive graphics, and the ever-increasing number and size of objects being shipped around means performance has to at least keep pace. But people badly want those other three attributes (convenience, economy, reliability) too, and you can't measure the quality of distributed and concurrent computing solely or even primarily on the basis of its performance. If you insist on concentrating on performance issues for concurrency, there is still room for good and bad perspectives. Don't think of the main performance gain of n-fold concurrency as being solving one problem up to n times faster. Think of it instead as being for solving n problems in the time of one. If you're lucky you may be able to solve n/k problems up to k times faster for k larger than 1, but you stretch your luck as you let k approach n. The situation at k = n is approximately that of low-level coding, as in assembly language and microcode: the investment is so high that only a very few returns on the investment can justify it, e.g. calculations for particle physics or cryptography. Such expensive high-k applications are far from being the only application of concurrent computing, in fact I venture to say they constitute only a small and unrepresentative fraction of the concurrency milieu. The twin offspring of sequential computing are Together and Faster. Together is the more sociable twin, a good organizer, likely to become a company president one day. Faster is a loner, always out on his bike trying to beat his personal best. Faster may make a big splash one day in the Indy 500, but his impact on the world economy will never match that of Together. Vaughan Pratt
hawley@uunet.UU.NET (David John Hawley) (12/18/90)
In article <12318@hubcap.clemson.edu> pratt@cs.stanford.edu (Vaughan Pratt) writes:
* If you insist on concentrating on performance issues for concurrency,
* there is still room for good and bad perspectives. Don't think of the
* main performance gain of n-fold concurrency as being solving one
* problem up to n times faster. Think of it instead as being for solving
* n problems in the time of one. If you're lucky you may be able to
* solve n/k problems up to k times faster for k larger than 1, but you
* stretch your luck as you let k approach n. The situation at k = n is
* approximately that of low-level coding, as in assembly language and
* microcode: the investment is so high that only a very few returns on
* the investment can justify it, e.g. calculations for particle physics
* or cryptography. Such expensive high-k applications are far from being
* the only application of concurrent computing, in fact I venture to say
* they constitute only a small and unrepresentative fraction of the
* concurrency milieu.
I don't understand what the difference is between solving n Problems
concurrently in time 1, and solving n SubProblems concurrently in time 1.
Unless we are talking about timesharing, on some black box which happens
to be a distributed computer? If so, I don't see the relevance to performance.
There may be another side to "faster". If you can take a general, but
slow algorithm, and get it to go "faster", to the point of being
practically useable, then you can recover your development cost by not
worrying so much about developing special-case algorithms. Although
generality usually implies bigger O(_) complexity, to some extent
concurrency can make it worthwhile.
David Hawley