NetNews Usenet Archive 1992 #31/NN_1992_31.iso/spool/comp/parallel/2823

Text File | 1992-12-28 | 4.8 KB | 101 lines

Newsgroups: comp.parallel
Path: sparky!uunet!gatech!hubcap!fpst
From: [e-mail] (R.S. Nikhil)
Subject: Re: (comp.lang.functional) tree of frames
Message-ID: <[e-mail]>
Keywords:  tree of frames ...
Sender: [e-mail] (USENET News System)
Organization: DEC Cambridge Research Lab
References:  <[e-mail]>
Date: Mon, 28 Dec 1992 18:21:05 GMT
Approved: [e-mail]
Lines: 87

In article <[e-mail]>, [e-mail] (V.C. SREEDHAR) writes:
> Hello:
>
> I read in PRISC (Nikhil and Arvind) that they support
> tree of frame for function invocation.
> In a stack model it is much simpler to manage the stack of
> frames. For supporting tree of frames  one has to
> allocate space from the heap. This could an expensive operation.
> Also how does one manage the run time heap.
> How does one compile programs to  support tree of frames.
> In terms of storage space management, I find difficult to
> understand  management of tree of frames (unlike
> in stack based model,  which is simple to implement).
>

As one of the persons named above, let me respond:

- The tree structure is present in any parallel model.  Many parallel
  languages use a ``cactus stack''.  A tree of frames is the same
  thing, except at a finer granularity, where branching may occur at
  each frame.  In this sense, neither model is ``simpler'' than the
  other.

- If you are implementing a programming language that has GENERAL
  higher-order functions, you need a tree of environment frames anyway
  (even if the language is sequential, even if you use cactus stacks).
  A tree of frames can be used to handle both parallel calls and
  general higher-order functions.

- In the cactus stack model, the stacks themselves have to be
  allocated from some free space.  This may be a general heap that
  includes heap data structures, or could be from special space
  reserved for stacks.  Exactly the same choices can be made with a
  tree of frames--- allocate from the general heap, or from a special
  ``frame store'' area.

- In the cactus stack model, the following actions can be expensive:
  a) allocating a new stack (e.g., large object, load balancing issues)
  b) handling the exception when (if) a stack overflows and needs to be enlarged
  c) migrating an entire stack (for load balancing)
  Some of these can be easier to manage at the granularity of
  individual frames.

- Reclaiming stack space is easy.  Stacks also contribute to good
  locality.  Trees of frames have exactly the same properties:
  - it is easy to compile frame-reclaimation code inline (does not
    have to rely on a general heap garbage collector) and, further,
  - frames can be therefore be recycled quickly to improve locality
    (even if they are placed in a general-purpose heap)

Thorsten von Eicken adds:

>    I think the major cost in tree-of-frame allocation is in argument passing
>    and not so much in the heap allocation itself (if well done). You can't
>    pass arguments in registers easily (tree of frames implies parallel call).
>    Arguments have to be stored relative to the newly allocated frame. You also
>    have to pass an invisible `return pointer' so that the child knows where to
>    deposit result values (and what continuation to enable).

but I disagree.  Trees of frames support parallel calls, but they do not IMPLY a
parallel call.  A tree of frames can be used in a sequential implementation, and a
tree of frames can have long chains of calls (it does not HAVE to branch at every
frame).  In those situations where you could pass args/results in registers using a
stack model (i.e., local calls/returns), you can do exactly the same thing with a tree
of frames.  The main thing is that you have to know that it's a local call/return, but
that's a language/compiler issue, and trees of frames take no position on that.  I
note in passing that SML of NJ allocates its frames in the heap even though it is a
sequential language and a uniprocessor implementation.

So, to get back to the original question of whether stacks or trees of
frames are ``simpler'' or ``better'', this is something that we can
never answer in the absolute, because it depends on everything: your
programming language, your compiler, your run time system, your
architecture, and, ultimately, your application program and its
specific inputs.  So, it can only be answered by experience and, on
that dimension, I think it is still too early to tell.

The following reference has more details about compiling a higher-order
functional language for a fine-grain parallel model using a tree of frames.

    "The Parallel Programming Language Id and its Compilation
     for Parallel Machines",
    R.S.Nikhil, CSG Memo 313, MIT Laboratory for Computer Science,
    545 Technology Square, Cambridge, MA 02139, USA, July 30 1990.

Rishiyur Nikhil ([e-mail])