home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / parallel / 1764 < prev    next >
Encoding:
Text File  |  1992-07-21  |  2.4 KB  |  88 lines
  1. Newsgroups: comp.parallel
  2. Path: sparky!uunet!europa.asd.contel.com!gatech!hubcap!fpst
  3. From: rvdg@cs.utexas.edu (Robert van de Geijn)
  4. Subject: Broadcasting on Hypercubes
  5. Message-ID: <l6bna3INNjjh@grit.cs.utexas.edu>
  6. Keywords: iPSC Hypercubes Broadcast
  7. Sender: fpst@hubcap.clemson.edu (Steve Stevenson)
  8. Organization: CS Dept, University of Texas at Austin
  9. Date: 16 Jul 1992 15:34:11 -0500
  10. Approved: parallel@hubcap.clemson.edu
  11. Lines: 75
  12.  
  13. I recently developed a broadcast routine for the iPSC/860
  14. that is considerable faster than the library call to
  15. csend with destination -1, at least for very large vectors.
  16.  
  17. While I am still working on the report, and I am not willing
  18. to disclose the algorithm at this time, I am willing to
  19. make the object code available to whoever needs it in a
  20. hurry.
  21.  
  22. A time complexity shows that the algorithm is faster that
  23. a minimum spanning tree broadcast (which is used by csend)
  24. by a factor   (p log p) / (2 (p-1) ) (asymptotically).
  25.  
  26. Here are some timings on the ORNL iPSC/860:
  27. (n= # of bytes, p= # of nodes, times in seconds)
  28.  
  29. p=64
  30.      n    new      csend-1
  31.      =    ===      =======
  32.      0  0.00020    0.00022
  33.      1  0.00021    0.00022
  34.     10  0.00022    0.00024
  35.    100  0.00041    0.00041
  36.    500  0.00210    0.00188
  37.   1000  0.00263    0.00295
  38.   5000  0.00645    0.01163
  39.  10000  0.01021    0.02250
  40.  50000  0.04000    0.10796
  41. 100000  0.07391    0.21513
  42.  
  43. p=32
  44.      0  0.00017    0.00018
  45.      1  0.00018    0.00018
  46.     10  0.00019    0.00020
  47.    100  0.00034    0.00034
  48.    500  0.00163    0.00155
  49.   1000  0.00239    0.00245
  50.   5000  0.00622    0.00960
  51.  10000  0.00926    0.01854
  52.  50000  0.03779    0.08996
  53. 100000  0.07202    0.17925
  54.  
  55. The object file can be obtained via anonymous ftp
  56. from cs.utexas.edu, directory pub/rvdg/gcast.
  57. In this directory, there is a README file that
  58. explains the calling sequence.
  59.  
  60. ===========================
  61. ftp cs.utexas.edu
  62. Name: anonymous
  63. Password: anything
  64. cd pub/rvdg/gcast
  65. bin
  66. get rvdg_gcast.o
  67. get README
  68. ===========================
  69.  
  70. you may want to look at some of the postscript files
  71. in pub/rvdg as well.
  72.  
  73. Those who send a message to rvdg@cs.utexas.edu will
  74. be kept up to date on further developments wrt this
  75. and other communication algorithms.
  76.  
  77. We are working on a broadcast for the Intel Touchstone
  78. Delta as well, based on the same principles.
  79.  
  80. PLEASE, don't send messages asking for further details.
  81.  
  82. Robert van de Geijn
  83. Assistant Professor
  84. The University of Texas at Austin
  85. rvdg@cs.utexas.edu
  86.  
  87.  
  88.