home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / lang / function / 930 < prev    next >
Encoding:
Text File  |  1992-07-21  |  3.6 KB  |  74 lines
  1. Newsgroups: comp.lang.functional
  2. Path: sparky!uunet!cs.utexas.edu!torn!news.ccs.queensu.ca!qucis.queensu.ca!skill
  3. From: skill@qucis.queensu.ca (David Skillicorn)
  4. Subject: Bird-Meertens Formalism and Parallelism
  5. Message-ID: <1992Jul21.172747.7359@qucis.queensu.ca>
  6. Organization: Computing & Information Science, Queen's University
  7. Date: Tue, 21 Jul 1992 17:27:47 GMT
  8. Lines: 64
  9.  
  10.  
  11. Getting parallelism out of a functional language isn't nearly as easy
  12. as it appears. As far as I can tell there are really only two routes:
  13. using strictness or using speculation. Both have problems.
  14.  
  15. Strictness depends on having lots of strict primitives or a compiler
  16. that can detect strictness well. Proponents of higher order functional
  17. programming seem to have gone for compiler detected strictness.
  18. The Bird-Meertens formalism goes for a fixed set of second order
  19. functions chosen to express massive strictness. Both choices are
  20. sensible and arguments about the cost/benefits of higher orderness
  21. have been going for at least 15 years without any real resolution.
  22.  
  23. Speculation probably deserves more attention than it has received,
  24. but there are obvious problems with catching up and killing
  25. rogue speculation.
  26.  
  27. Earlier messages have explained the construction of categorical
  28. data types and some of the good things that go along with it. I'll
  29. fill in some stuff to do with parallelism that hasn't already been
  30. mentioned.
  31.  
  32. The CDT construction produces for each new type a generalized map
  33. operation and a generalized reduction operation. These have the
  34. obvious meaning on lists or bags. They do get more subtle when the
  35. data type being considered is more complex (such as trees, see
  36. Jeremy Gibbons thesis from Oxford, or arrays, see Banger's paper in
  37. the proceedings of the ATABLE meeting last month). However, the
  38. important thing is that these operations are both inherently parallel.
  39. A homomorphism theorem for each constructed type assures us that
  40. any homomorphism can be expressed as the composition of a generalized
  41. map and a generalized reduction; so parallelism comes easily.
  42.  
  43. More importantly, homomorphisms reflect the locality behaviour of
  44. the constructors of a type. If the type's constructors join
  45. objects at a single point when building new objects, then 
  46. homomorphisms will require computation to occur between the
  47. result of the homomorphism applied to the subobjects. Homomorphisms
  48. replace each constructor by a new operation.
  49.  
  50. This all means that we can look at the constructors and deduce the
  51. communication pattern that will be used to evaluate any homomorphism.
  52. If the interconnection topology of our target includes this communication
  53. pattern as a (sub)topology then homomorphisms will only use local
  54. communication and we can treat the target as a free communication
  55. machine. This dramatically simplifies working out the time complexity of
  56. computations. But it also means that computations in the BMF style can
  57. be relatively architecture independent since they will work the same
  58. on any architecture containing an appropriate subtopology.
  59.  
  60. Of course, all the other good features of the Bird-Meertens approach:
  61. transformation by equations that come for free, guarantees of
  62. completeness, abstraction from the details of decomposition
  63. and communication, apply in a parallel setting as well. Arguably
  64. BMF is a great model for parallel computation because it has
  65. just about the right level of abstraction.
  66.  
  67. You can get more details on all of this by ftping papers from
  68. ftp.qucis.queensu.ca in directory pub/skill. There's also an
  69. extensive Bibtex bibliography on parallel programming models
  70. there as well.
  71.  
  72.                               -david skillicorn
  73.                                skill@qucis.queensu.ca
  74.