Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!caen!sol.ctr.columbia.edu!emory!hubcap!fpst From: zenith@ensmp.fr (Steven Ericsson Zenith) Newsgroups: comp.parallel Subject: Re: New i860 parallel machine Message-ID: <1991Apr22.122925.1759@hubcap.clemson.edu> Date: 20 Apr 91 13:50:03 GMT Sender: zenith@ensmp.fr Organization: Clemson University Lines: 141 Approved: parallel@hubcap.clemson.edu I actually got a bundle of mail, in addition to those posted, on this subject. I'll summarise that in a second note. Here I want to comment on Vaughan Pratt's message of the 18th and the subsequent response from "hugo@griggs.dartmouth.edu (Peter Su)" Vaughan Pratt said > The biggest obstacle is that we don't even know what concurrency is. > People think they know now, but in hindsight in 2020 they will be able > to see that they really did not know in 1991. Actually I agree fully with this comment and I hope to explain why. However Peter Su said in response: > One of the assumptions behind this statement is that concurrency as it > is defined by computer science ... is relavent to the construction of > parallel machines and algorithms for computational problems ... this > definition of concurrency, and the formal models surrounding it are > all motivated in some sense by the design and implementation of > operating systems. One could argue that they are largely irrelevant > to the design and implementation of parallel algorithms. > For example, in the theoretical computer science community, most > parallel algorithms are designed not with concurrent process algebras, > pomsets, or any of that. Rather, the model of computation is SPMD > shared memory. In other words, the emphasis is on operating on > parallel data structures, not on coordinating concurrent processes. I don't understand the point here, are you just having a dig at Vaughan? If I read you correctly you are distinquishing between "computer science" and "theoretical computer science"? You seem to suggest that the theories of concurrency have no place in "theoretical computer science". Well, frankly, lift your head up and take a look around you! Nor can I agree that the formal models of concurrency are motivated in any sense by the design and implementation of operating systems alone. As evidence of to support my contention I point to the work of Bill Roscoe, Tony Hoare, Robin Milner and many others. It is true that in the USA a lot of systems research has focused on operating system support for concurrent models but that is just one aspect of a multifaceted science. As Vaughan points out alot of work has been done in Europe. Another facet of computer science focuses on the design of algorithms ... very often the focus in such work is very narrow. Peter goes on to say: > The reason for this is simple, the amount of parallelism that you can > obtain scales naturally with the size of the problem. So, the most > natural way to get a lot of parallelism is to write one program, and > replicate it. Is it really realistic to expect that people could > program a 2K MIMD machine susing two thousand separate programs? I > don't think so. Well I think you are just plain wrong and here's why. You have too narrow a view of problems. Let's consider a problem I raised earlier. Control and management of a container terminal. Let us now consider the problem a little (just a little). I have ships arriving at n docks in intervals. Each ship carries x containers. Each container has y goods earmarked for collection to z departures. Ships are expected, we know their point of departure, we know what they carry in the containers. I also have m trunks arriving at land gates. Each dock has p robots which remove containers from arriving ships and place them directly on trunks (let's assume all custom checks are on ship). This one container terminal communicates and cooperates with other such terminals, points of departure and destination. And so forth ... Forget control - consider monitoring such a system which on it's own is already a >2K MIMD machine! Not convinced? Ok, there's a bigger one - consider air traffic control. Look, these are BIG machines. What are you going to do? Continue to program the whole problem in PASCAL? COBOL? ASSEMBLER :-) Further, in the back room of each container terminal (circa 2010ad), and each air traffic control system are several >10K SIGMA machines. Amoung other things, every day, for ten minutes it runs one of your wacky algorithms. Oh, it's neat. It's bulk synchronous, it does in ten minutes what it would take 5 years to compute now, it is one component in a mighty world built of concurrent systems. And great big ones at that! Don't misunderstand me. Replication is a very very important aspect of concurrent systems, and it will be used widely. So in answer to Peter's question "is it really realistic to expect that people could program a 2K MIMD machine susing two thousand separate programs?" - you bet your sweet bippy it is. People do it now. Talk to anyone programming an air traffic control system and ask them how many separate programs (read processes) they have currently! But ok, that's in the real world, and I'm reluctant to leave it. You want to consider a single big box of devices? Consider simulation models. Think about architectural design and simulation in the car industry. Consider the design and simulation of space probes. Think about geological and astro-physical simulations. Components of each of these may indeed be SPMD (or SIMD for that matter) but the whole will be a MIMD concurrent system. In the next century this will be small fry (i.e. 2K separate programs). Expect systems with 100's of millions of concurrent computing components. Two years ago I pooh poohed Ian Barron when he told me people should be thinking in millions of processes. He'd been having his house decorated at the time and I figured the fumes were getting to him. But he's right in my view now. The only obstacle is economic. No small obstacle that - ask yourself why there is no exploitation of the moon. It may be that we build one or two 10K processor machines before we reach the end of the century ... and nothing interesting happens beyond that until the year 2100! Imagination is what we need! We're too short sighted at the moment. But it's a problem. How is anyone going to manage such systems? Well, I don't think it will be one person - just as the large systems I've mentioned are not now programmed or even managed by a single person. I expect someone to discover the holy grail of concurrent systems in the next ten years or so ... and I think that's what Vaughan meant. Incidently, the theories of concurrency don't ignore data distribution. In fact, that's what we're all preoccupied with just now. Oh, and just in case someone comes back and says I can still do all the above using a SPMD model my reply must be that a) you must have enormous resource on each node and b) all you've done is provide a scheduling mechanism for a MIMD program. :-) Mmmm. I still haven't answered Vaughan's comments. Steven -- Steven Ericsson Zenith Center for Research in Computer Science Ecole Nationale Superieure des Mines de Paris. France -- =========================== MODERATOR ============================== Steve Stevenson {steve,fpst}@hubcap.clemson.edu Department of Computer Science, comp.parallel Clemson University, Clemson, SC 29634-1906 (803)656-5880.mabell