home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / parallel / 2834 < prev    next >
Encoding:
Text File  |  1992-12-30  |  2.3 KB  |  74 lines
  1. Newsgroups: comp.parallel
  2. Path: sparky!uunet!gatech!hubcap!fpst
  3. From: maniattb@cs.rpi.edu (Bill Maniatty)
  4. Subject: Re: Torus vs. Hypercube
  5. Message-ID: <1992Dec30.124438.28257@hubcap.clemson.edu>
  6. Apparently-To: comp-parallel@cis.ohio-state.edu
  7. Sender: fpst@hubcap.clemson.edu (Steve Stevenson)
  8. Nntp-Posting-Host: electra.cs.rpi.edu
  9. Organization: Clemson University
  10. References: <1992Dec27.201910.28352@ee.eng.ohio-state.edu> <1992Dec29.210648.18508@hubcap.clemson.edu>
  11. Date: Tue, 29 Dec 1992 22:08:12 GMT
  12. Approved: parallel@hubcap.clemson.edu
  13. Lines: 59
  14.  
  15. In article <1992Dec29.210648.18508@hubcap.clemson.edu>, heller@Think.COM (Steve Heller) writes:
  16. |> 
  17. |> In article <1992Dec29.142815.27527@hubcap.clemson.edu> David Karr <karr@cs.cornell.EDU> writes:
  18. |> 
  19. |>    In article <1992Dec27.201910.28352@ee.eng.ohio-state.edu> bai@rainier.eng.ohio-state.edu (Baback A. Izadi) writes:
  20. |> 
  21. |>    >Couple of weeks ago, I think heard a speaker claiming that
  22. |>    >2-dimensional Torus and hypercube have basically the same
  23. |>    >topology. How could this be true?
  24. |> 
  25.     [Stuff Deleted]
  26.  
  27. The topology of the connections imbedded in the torus might make a 2
  28. dimensional torus more connected than the corresponding hypercube.
  29.  
  30. Consider an 8 nearest neighbor connectivity with toroidal wrap, with O being
  31. the central processor, the others labelled after the points on a compass:
  32.  
  33.            NW N NE
  34.              \|/
  35.             W-O-E
  36.              /|\
  37.            SW S SE
  38.  
  39. (a real world example of this is found in a MasPar MP-1),
  40. which is more connected than the corresponding ``Manhattan'' style connection:
  41.  
  42.               N
  43.               |
  44.             W-O-E
  45.               |
  46.               S
  47.  
  48. If we look at a simple 2 dimensional hypercube (square)
  49. versus the corresponding 8 nearest neighbor topology with toroidal wrap
  50. the hypercube requires 2 hops to go to opposing corners, while every node
  51. in the 8 nearest neighbor torus can be reached in just one hop.
  52.  
  53.     [Stuff Deleted]
  54.  
  55. |> The fact that the 4^2 torus is isomorphic to the binary 4-cube led to an
  56. |> interesting question here at TMC about six months ago.
  57. |> 
  58. |> Is the 4^k torus isomorphic to the binary 2k-cube?
  59. |> 
  60. |> The answer and the proof (which I found quite fun) is left as an excercise
  61. |> to the reader.
  62. |> 
  63. |> -steve
  64.  
  65. Is this a closely guarded corporate secret :-) ?
  66.  
  67. Bill
  68.  
  69. -- 
  70. |
  71. |    maniattb@cs.rpi.edu - in real life Bill Maniatty
  72. |
  73.  
  74.