home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / parallel / 2840 < prev    next >
Encoding:
Text File  |  1992-12-30  |  11.2 KB  |  217 lines
  1. Newsgroups: comp.parallel
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!usenet.ins.cwru.edu!gatech!hubcap!fpst
  3. From: Steven Ericsson Zenith <zenith@kai.com>
  4. Subject: Re: Linda / The Parform
  5. Message-ID: <1992Dec30.212742.24207@hubcap.clemson.edu>
  6. Sender: fpst@hubcap.clemson.edu (Steve Stevenson)
  7. Organization: Clemson University
  8. Date: Wed, 30 Dec 92 09:25:27 -0600
  9. Approved: parallel@hubcap.clemson.edu
  10. Lines: 205
  11.  
  12. Well, regular readers of comp.parallel over the years will know that
  13. this isn't the first time my idiosyncratic use of the english language
  14. has gotten me into trouble. Colorful, and perhaps inappropriate at
  15. times, it is a reflection of me, my background and culture (or lack of
  16. it) and I do not apologize for it. I never -ever- have malicious intent
  17. in my remarks - I am sorry if anything I say should be interpreted so.
  18.  
  19. I do, however, comment on areas in which I have some knowledge or have
  20. experience undertaking similar experiments. I may criticize the work of
  21. others in my field but such criticism should not be taken as an attack
  22. on the person - though I understand the temptation to initially
  23. interpret it so. I hope I am as gracious when receiving criticism of my
  24. own work. It too has strengths and weaknesses and that work and postings
  25. here over the years have revealed both - I have no shame of either.
  26.  
  27. I have read the "old" report to which Dr.Cap refers and as he points out
  28. it does not answer the questions raised in my posting. I look forward to
  29. reading his coming publication. I will also note that the ability to
  30. fund a project has never in my experience been an accurate reflection of
  31. its worth, most especially in Europe.
  32.  
  33. There are just a couple of points that need clarifying. When I referred
  34. to use of the same base compiler in these experiments I meant *the
  35. same*. Using different C compilers with the same switches is no
  36. guarantee of the same code generation. Therefore, if different compilers
  37. were used I do expect to see some variation. Depending on the problem
  38. the variation may or may not be important.
  39.  
  40. For example, in the graph presented in the referred paper a time of
  41. 1370.6 is reported under the table heading "Linda" and the table heading
  42. "PVM" and "PARFORM". The same number appears in the recent posting for
  43. Yale (SCA) Linda. Now, the last time I looked Yale (SCA) Linda had an
  44. integrated compiler while PVM and POSYBL were, as libraries, able to use
  45. a native compiler and there I expect to see a variation of some kind -
  46. even a small one (The source of this single number becomes clear in the
  47. paper and will be revealed in a following paragraph).  But whatever the
  48. case the central point is this: the actual compiler used, the maker and
  49. version number, was not reported - it is not good enough to say "all
  50. platforms use the C language and C compiler with identical compiler
  51. options": this was the same C compiler?  The native Sun C compiler? The
  52. GNU C compiler?  Which?
  53.  
  54. I am particularly interested in your base time because it, and not any
  55. caching artifact, may be the source of your superlinear speed up. I'm
  56. not saying that it is so, I'm simply asking the question.
  57.  
  58. However, you might like to consider the following scenario, a
  59. reinterpretation of your figures, that is the source for my concern:
  60.  
  61. Here are the original numbers.
  62.  
  63. >  Procs POSYBL SCA linda    PVM    MC-2    The Parform
  64. >    1    1370.6    1370.6         1370.6     --    1370.6 (1.0)*
  65. >    2     737.2     662.2         648.0     --     654.8 (2.1)
  66. >    4     442.6     342.6         328.0     921.4     332.3 (4.1)
  67. >    6     339.3     235.5         219.0     618.5     221.7 (6.2)
  68. >    8     284.6     175.8         168.4     466.7     170.2 (8.0)
  69. >   10     260.2     144.3         143.6     376.6     137.4 (10.0)
  70. >   12     244.7     122.1         116.6     318.2     116.0 (11.8)
  71. >   14     242.7     104.5         100.1     276.2     103.5 (13.5)
  72. >   16     239.5      92.8           90.0     240.0      89.0 (15.4)
  73. >   18     242.6      84.5          97.5     215.9      80.9 (16.9)
  74. >   20     241.6      76.0          85.8     196.6      73.5 (18.7)
  75. >   22           71.5          68.5     182.8      67.5 (20.3)
  76. >   24          66.5          63.6     170.9      62.5 (21.9)
  77. >   26          63.1          60.5     160.9      58.6 (23.4)
  78. >   28          58.5          56.7     151.9      55.8 (24.7)
  79. >   30          55.1          53.5     144.7       53.0 (25.9)
  80. >   32          54.0          54.0     138.5      51.0 (26.9)
  81. >   34          52.4          54.0          50.8 (27.0)
  82. >   36          51.4          52.0          48.5 (28.3)
  83. >   38          51.3          54.0          48.4 (28.3)
  84. >   40                  52.9          47.2 (29.0)
  85.  
  86. >    * speedup in parentheses
  87.  
  88. I assume speedup is computed using the same method for the graph on page
  89. 11 of the "old" paper. There it is stated that the speed up is "with
  90. respect to the sequential run on the slowest workstation in our LAN, a
  91. Sparcstation1." This is justified later by the comment "In the case of
  92. homogeneous partioning [of the problem] the slowest machine in the net
  93. is responsible for the speedup. All faster machines idle while waiting
  94. at the synchronization points, which are the communication statements.
  95. Thus it is reasonable to calculate speedup values with respect to the
  96. runtime on the slowest machine."
  97.  
  98. I understand the point here but I'm not convinced by the reasoning. I
  99. would disagree with the paper on this point arguing that the base time
  100. for a parallel speedup measure must be the fastest possible sequential
  101. time not the slowest, regardless of the disparate performance of the
  102. relative processing elements. By your reasoning I can sit a Cray on the
  103. network (which I'll assume here can do the task in zero time) and still
  104. we will see your "speed up" yet if I randomly walk up to your network
  105. and sit at the Cray I will not be able to prove your case - however, let
  106. us move on.
  107.  
  108. Reconsider the figures with the base numbers modified according to the
  109. time give for 2 processors times 2. So, this allows that each system,
  110. for this problem, speeds up perfectly for 2 processors (which it
  111. probably doesn't) but I'll argue it may give me a fair measure of the
  112. sequential code generation of each compiler and is equally fair to each
  113. system implementation. Not surprisingly we see the variation I expected.
  114. To save time permit me to focus on the Yale (SCA) Linda, PVM and PARFORM
  115. numbers.
  116.  
  117.   Procs SCA linda        PVM             The Parform
  118.     1     1324.4(1)              1296.0(1)       1309.6 (1)*
  119.     2      662.2(2)        648.0(2)        654.8 (2)    [2.1]**
  120.     4      342.6(3.86)        328.0(3.95)         332.3 (3.94) [4.1]
  121.     6      235.5(5.62) [5.82]    219.0(5.92) [6.26]  221.7 (5.9)  [6.2]
  122.     8      175.8(7.53) [7.8]    168.4(7.70) [8.14]  170.2 (7.69) [8.0]
  123.    10      144.3(9.18) [9.5]    143.6(9.03) [9.54]  137.4 (9.53) [10.0]
  124.    12      122.1(10.8) [11.23]    116.6(11.11)[11.75] 116.0 (11.29)[11.8]
  125.    14      104.5(12.67)        100.1(13)   [13.6]  103.5 (12.7) [13.2]
  126.    16       92.8(14.27)          90.0(14.4)          89.0 (14.71)[15.4]
  127.    18       84.5(15.67)         97.5(13.29)          80.9 (16.19)[16.9]
  128.    20       76.0(17.43)         85.8(15.01)          73.5 (17.82)[18.7]
  129.    22       71.5(18.52)          68.5(18.92)          67.5 (19.40)[20.3]
  130.    24       66.5(19.92)          63.6(20.38)          62.5 (20.95)[21.9]
  131.    26       63.1(20.99)          60.5(21.42)          58.6 (22.35)[23.4]
  132.    28       58.5(22.64)[23.4]     56.7(22.86)[24.2]   55.8 (23.47)[24.7]
  133.  ...
  134.  
  135.     * speedup in parentheses
  136.     ** old numbers in square brackets.
  137.  
  138. These numbers draw a slightly different graph - not greatly different
  139. I'll admit but, significantly, there are no superlinear artifacts.  Let
  140. me make it clear that this is a fiction because we do not have the real
  141. base times but I will argue that it is a legitimate interpretation of
  142. the numbers. I like these numbers better since there is no superlinear
  143. speedup (well you knew there wouldn't be) - and they illustrate the
  144. effect of a small change to the respective base times.  Imagine now the
  145. result if we had taken the SPARCstation2 base time (564) given in the
  146. paper - negative speedup on 2 processors - which may, in fact, be the
  147. right information to give a potential user with this application whose
  148. network configuration is two SPARC1s and one SPARC2.
  149.  
  150. I did read the paper. I understand the issues surrounding swapping, I
  151. know, as do most people by now, the effective increase in localized
  152. memory and cache size can produce superlinear artifacts - I'm just not
  153. convinced these numbers illustrate that with the 3800x100 problem size
  154. these numbers are for.
  155.  
  156. These are not trivial points either since they have ramifications in the
  157. subsequent analytical conclusions presented in the paper.
  158.  
  159. We certainly should not interpret from these numbers that the PARFORM
  160. implementation performs better than the other two. The Linda compiler
  161. may still be a version of an old GNU C compiler (it was the last time I
  162. -2+ years ago- dug into its guts) and thus its code generation may not
  163. be quite as good as the compiler used in the PVM and PARFORM case - we
  164. don't know since we don't know the compiler used - it may be enough to
  165. remove any disparity shown above.
  166.  
  167. I am not suggesting that the numbers were in any way faked, I am
  168. questioning the use, attribution and validity for the stated cause, of
  169. the numbers you have and I welcome clarification. I expect other peer
  170. review would do the same.
  171.  
  172. The stated cause is important here for my comments were aimed at the
  173. contention made in the earlier reposting of the numbers that they (the
  174. numbers) "heated up the discussion whether the Linda or message passing
  175. paradigm are superior" and I am particularly interested in the
  176. comparison of parallel programming *models*. The same implication is
  177. made in the paper. However, the explicit claim is different. The
  178. explicit claim is (pg18) "The presented results and experiences with our
  179. platform show that we can regard a workstation network as a tightly
  180. coupled multiprocessor system when exploiting its resources with a
  181. system like the PARFORM." with which I doubt anyone in this field would
  182. disagree. But let us be clear, these numbers do not tell us anything
  183. about the intrinsic merit of the models involved. They tell us something
  184. of the specific implementations, in this case I believe they tell us
  185. more about parallel decomposition of this problem: pretty much any
  186. interaction model will do, new scheduling techniques are important and
  187. applicable to all implementations.
  188.  
  189. To emphasize: comparing a poor implementation of Linda to any
  190. implementation of Message Passing and vice versa reveals no intrinsic
  191. knowledge about the relative merit of each model.
  192.  
  193. And so I must return to my earlier remarks and restate them: for a valid
  194. comparison of the models to be made the implementations must be shown to
  195. be comparable. The base compiler must be the same; i.e., the sequential
  196. code generation must be equivalent. The implementation techniques of the
  197. model must be comparable; i.e., process creation, synchronization,
  198. interaction implementations must be understood at the lowest level and
  199. be shown to be comparable. Further more, the problems run should
  200. exercise the primitives of the model. A straight comparison of a program
  201. running under Yale (SCA) Linda and PVM is not at all valid in this
  202. sense; just as the earlier comparison with POSYBL illustrated (yes,
  203. though I rest in silence, I do still read this news group).
  204.  
  205. The above comments should not be deemed to show favor by me to either
  206. message passing or Linda models, anyone knowing my work will know that I
  207. have arguments against both for general purpose parallel programming
  208. beit in shared or distributed environments. I have solutions but *that*
  209. is for another time.
  210.  
  211. Peace and balance to you all in this coming New Year.
  212. --
  213. Steven Ericsson Zenith
  214. Disclaimer: Opinions expressed are my own and not necessarily those of KAI.
  215.  
  216.  
  217.