home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / parallel / 2806 < prev    next >
Encoding:
Text File  |  1992-12-28  |  2.6 KB  |  59 lines
  1. Newsgroups: comp.parallel
  2. Path: sparky!uunet!gumby!destroyer!gatech!hubcap!fpst
  3. From: tve@crackle.CS.Berkeley.EDU (Thorsten von Eicken)
  4. Subject: Re: (comp.lang.functional) tree of frames
  5. Message-ID: <1992Dec28.160310.27135@hubcap.clemson.edu>
  6. Keywords: tree of frames ...
  7. Sender: fpst@hubcap.clemson.edu (Steve Stevenson)
  8. Nntp-Posting-Host: crackle.cs.berkeley.edu
  9. Organization: University of California, Berkeley
  10. References: <1992Dec23.140907.21427@hubcap.clemson.edu>
  11. Date: 24 Dec 1992 07:22:25 GMT
  12. Approved: parallel@hubcap.clemson.edu
  13. Lines: 44
  14.  
  15. In article <1992Dec23.140907.21427@hubcap.clemson.edu> sreedhar@cs.mcgill.ca (V.C. SREEDHAR) writes:
  16. >I read in PRISC (Nikhil and Arvind) that they support 
  17. >tree of frame for function invocation.
  18. >In a stack model it is much simpler to manage the stack of
  19. >frames. For supporting tree of frames  one has to
  20. >allocate space from the heap. This could an expensive operation.
  21.  
  22. Yes and no. Basically, instead of adding to or subtracting from the
  23. stack pointer, you ``call malloc''. This is the simple but expensive
  24. way. More realistically, you write your own memory allocator and inline
  25. the typical case. Usually you'd choose a binned allocator, i.e., a
  26. table of free lists per block size (good mallocs do that too). Notice
  27. that the frame size is normally static, so you can generate the index
  28. into the table at compile time. If you want, you can optimize the table
  29. to only have entries for frame sizes that actually occur in the
  30. program. The next optimization is to use ``stacklets'': small fixed
  31. sized stacks which allow you to use stack allocation for one child
  32. frame most of the time.  Haven't gotten around to implement that yet,
  33. others might be able to comment!?
  34.  
  35. >Also how does one manage the run time heap.
  36. >How does one compile programs to  support tree of frames.
  37.  
  38. I think the major cost in tree-of-frame allocation is in argument passing
  39. and not so much in the heap allocation itself (if well done). You can't
  40. pass arguments in registers easily (tree of frames implies parallel call).
  41. Arguments have to be stored relative to the newly allocated frame. You also
  42. have to pass an invisible `return pointer' so that the child knows where to
  43. deposit result values (and what continuation to enable).
  44.  
  45. >In terms of storage space management, I find difficult to
  46. >understand  management of tree of frames (unlike
  47. >in stack based model,  which is simple to implement).
  48.  
  49. Nothing magic. Just need to keep track of parent/child pointers explicitly
  50. as in any tree data structure.
  51.  
  52. >Thanks a lot
  53.  
  54. I'm sure others will have more to add...
  55.  
  56.     Thorsten von Eicken
  57.     tve@cs.berkeley.edu
  58.  
  59.