home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / parallel / 2841 < prev    next >
Encoding:
Text File  |  1992-12-31  |  3.0 KB  |  69 lines
  1. Newsgroups: comp.parallel
  2. Path: sparky!uunet!cs.utexas.edu!zaphod.mps.ohio-state.edu!swrinde!gatech!hubcap!fpst
  3. From: kh <kh@dcs.gla.ac.uk>
  4. Subject: Re: (comp.lang.functional) tree of frames
  5. Message-ID: <1992Dec31.140836.3548@hubcap.clemson.edu>
  6. Apparently-To: hypercube@hubcap.clemson.edu
  7. Keywords: tree of frames ...
  8. Sender: fpst@hubcap.clemson.edu (Steve Stevenson)
  9. Organization: Computing Sci, Glasgow Univ, Scotland
  10. References: <1992Dec23.140907.21427@hubcap.clemson.edu> <1992Dec28.182105.9329@crl.dec.com>
  11. Date: Wed, 30 Dec 92 21:42:18 GMT
  12. Approved: parallel@hubcap.clemson.edu
  13. Lines: 54
  14.  
  15. In article <1992Dec28.182105.9329@crl.dec.com> nikhil@crl.dec.com (R.S. Nikhil) writes:
  16.  
  17. As Nikhil's aware, in our parallel functional implementation we use a
  18. segmented stack similar to the cactus stack model.
  19.  
  20. >- In the cactus stack model, the following actions can be expensive:
  21. >  a) allocating a new stack (e.g., large object, load balancing issues)
  22.  
  23. For our segmented scheme, the actual allocation cost is usually no
  24. greater than for a single small object (unless garbage collection is
  25. invoked).  I suspect that's true for most allocators currently used in
  26. functional/dataflow languages.  If dead stack segments can be reused,
  27. then the cost can be reduced further.
  28.  
  29. >  b) handling the exception when (if) a stack overflows and needs to be enlarged
  30.  
  31. This can certainly be significant if it occurs, but our measurements
  32. suggest that stack overflow is quite infrequent for the applications
  33. we run, even with fairly small [4K] stack segments (this can depend
  34. crucially on granularity, of course: large grained tasks are likely to
  35. require larger stacks).  Against this, you need to count the cost of
  36. extra GCs for allocated, but not yet used, slots in stack frames.
  37.  
  38. >  c) migrating an entire stack (for load balancing)
  39. >  Some of these can be easier to manage at the granularity of
  40. >  individual frames.
  41.  
  42. I've been pondering this for a while, but without coming to a definite
  43. conclusion.  Surely, if you migrate a task then you will eventually
  44. migrate most of the stack anyway (as each basic block returns to its
  45. caller, so the parent frame must be migrated, unless the child task is
  46. returned to the parent processor).  The difference is then a tradeoff
  47. between latency and communication time (with "cactus stacks" a few
  48. long packets transmit the entire stack, whereas many short packets may
  49. be necessary for the distributed frame model).  Of course, if
  50. migration is frequent, then the frame model is probably better, but
  51. otherwise the reduction in communication cost is likely to favour the
  52. stack model, isn't it (assuming that communication cost is cheaper
  53. per-byte if larger packets are used)?
  54.  
  55. > So, it can only be answered by experience and, on
  56. >that dimension, I think it is still too early to tell.
  57.  
  58. Is there any work which compares the two approaches within the same
  59. compilation environment (for functional/dataflow languages)?  The
  60. results could be interesting...
  61.  
  62. Regards,
  63. Kevin
  64. -- 
  65. Dept. of Computing Science, Glasgow University.    E-mail: kh@dcs.glasgow.ac.uk
  66.  
  67. This Signature Intentionally segmentation fault
  68.  
  69.