Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!usc!wuarchive!emory!hubcap!Steven
From: zenith@ensmp.fr (Steven Ericsson-Zenith)
Newsgroups: comp.parallel
Subject: Heretics and Infidels(Part 3): Zenith replys to Gelernter.
Message-ID: <12496@hubcap.clemson.edu>
Date: 7 Jan 91 13:47:48 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 160
Approved: parallel@hubcap.clemson.edu
In-Reply-To: Steve Stevenson's message of Wed, 19 Dec 90 13:53:17 -0500 <9012191853.AA24710@hubcap.clemson.edu>


(continued from part 2)

In a message to comp.parallel on December 19th David Gelernter writes:

   Steven Zenith writes

     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...

   Two claims are made here: (a) Linda is unpredictable... the inference
   being, I assume, that it isn't suitable for realtime applications.
   (b) You have to understand the optimizer and subvert portability in
   order to get decent performance from Linda programs.

   Regarding (a), realtime is a difficult area.  The only substantial
   experiment I'm aware of involving realtime use of Linda is Mike
   Factor's work on an intensive care unit monitor.  He developed a
   performance model (for use by a heuristic scheduler) that predicted
   the runtime of his Linda application within a couple of percent.
   Factor's work has been described at length in the literature.  We've
   never made any blanket claims for Linda in realtime situations; on
   the basis of Factor's work, Linda is highly promising in this area,
   but that's our only claim for now.

I know this work too. Mike Factor's trellis ideas are interesting. They
are by no means dependent upon Linda for implementation. In fact, Mike
Factor's thesis far from showing Linda as "highly promising" provides
damning evidence to the contrary.

First of all, the category of real-time dealt with by Mike's thesis
(published December 1990) "The Process Trellis Software Architecture for
Parallel, Real-Time Monitors", is novel. It deals with a "soft
worst-case guarantee" where (page 5):

  "... given the worst-case senario of module invocations (i.e., most
  time consuming), the program will on average meet its deadline."

Having chosen this novel category he considers three possible
implementations (pages 49-51):

  "Full-Scale Processes: The obvious implementation of the trellis is to
  let each trellis process be a full-blown language or operating system
  process. For instance, in a Linda implementation the process would be 
  created by eval, in a Unix implementation by fork. ..."

This is dismissed because it reduces "efficiency and predictability", as
indeed it does.

  "It reduces efficiency because information at compile time that would
  be useful in scheduling is withheld from the program which performs
  the scheduling. ..."

  "It reduces predictability because a system other than the run-time
  kernel decides when a process gets CPU time. ..."

Indeed, this will come a no surprise to those with any experience in
real-time programming. It is surprising that Mike didn't junk the idea
of using Linda, or indeed any conventional UNIX platform at this point.
But such things are very often dependent upon who your supervisor is :-)

Mike then considers:

  "Dynamic-Worker: The dynamic worker kernel controls in a dynamic,
  distributed fashion when and where each process executes. ... 
  These workers ... are full-scale Unix-type processes..."

And he implemented this one but found (page 51):

  "the dynamic-worker kernel is inappropriate, even though it controls
  when and where processes execute. It's control is dynamic, and thus,
  the kernel is less efficient and predictable than it could be."

So finally:

  "The Static-Worker Run-Time Kernel: ... This kernel controls when and
  where processes execute in a static fashion. ... It is highly efficient
  accessing Linda's tuple space only when necessary. ..."

He overcame the problem by using Tuple Space as little as possible! Even
so, the process scheduler is written using Linda.

To return to Gelernter's comment's:

   Statement (b) is false.  The specific claim about 'most "succecessful'
   Linda applications' is also false.  "How to Write Parallel Programs"
   by Carriero and Gelernter (MIT Press 1990) presents 7 sets of
   performance results for a range of programs on a range of parallel
   machines (both shared and distributed memory).  (Look up "performance"
   in the index.)  These applications were developed with no regard for
   the optimizer whatever.  In fact, the book describes exactly how they
   WERE developed: on the basis of a simple and Linda-independent
   performance model.  We've reported similar performance results in the
   literature going back to 1986.

   (Zenith's statements ARE true to the vacuous extent that any system
   with an optimizer permits programmers who understand the optimizer to
   allow for its behavior in coding.  But the specific claim that you
   *must* do this to get good performance using Linda is false.)

Ah, that word "false" again - "true to a vacuous extent"?! Remember I
said, "You cannot predict the performance of the program, and you will
not know the performance until the task is complete. ..." and that,
"Most "successful" Linda programs are either written within a few feet
of the implementor of the optimizer ...". I did not make the "specific
claim that you *must* do this to get good performance using Linda" my
observation is stronger than that - the effect is subliminal even when
performance is less of an issue - a programmer *will* do this!

Let's return to Mike Factor's thesis, where in justifying "Why Linda"
(page 169) he says:

  "There is, however, one problem in predicting the execution time of a
  Linda program; Linda does not constrain the cost of accessing
  shared-memory; the time to complete a Linda operation is, in
  principle, unbounded. But a necessary condition for predicting a
  program's execution time is that it execute only time-bounded
  operations. Fortunately, the tuple space operations that occur in the
  static-worker kernel are predictable in practice given the Linda
  implementation; THIS WOULD HAVE BEEN EXTREMELY DIFFICULT TO VERIFY
  WITHOUT THE EXPERTISE OF LINDA'S IMPLEMENTORS, [the caps are mine] .."

Further, in July 1988, Ken Musgrave (a member of Mandelbrot's group at
Yale) published a paper entitled "Grid Tracing: Fast Ray Tracing for
Height Fields" in it he says:

  "Although the incipient scanline tasks are stored in a theoretically
  unordered "tuple space" in the Linda system, the implementation of
  this space is of course[?] an ordered list, and this virtual ordering
  in practice can be exploited to assure that the tasks will be executed
  by the "worker" processes in roughly the same order as the task
  "tuples" were output into the tuple space ... the image can still be
  expected to [be] rendered in an orderly fashion, such as
  top-to-bottom."

Wanna bet? Not if you run it on anything else it can't!  Ken also
acknowledges "the invaluable assistance" of the implementors.

As I mentioned before, I have not yet seen David's book and so cannot
comment. Perhaps MIT Press will send me a review copy? :-)

Steven
PS. This message ends my reply.
--
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