home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / parallel / 2833 < prev    next >
Encoding:
Text File  |  1992-12-29  |  2.0 KB  |  52 lines
  1. Newsgroups: comp.parallel
  2. Path: sparky!uunet!gatech!hubcap!fpst
  3. From: heller@Think.COM (Steve Heller)
  4. Subject: Re: Torus vs. Hypercube
  5. In-Reply-To: David Karr's message of Tue, 29 Dec 1992 01:22:33 GMT
  6. Message-ID: <1992Dec29.210648.18508@hubcap.clemson.edu>
  7. Sender: fpst@hubcap.clemson.edu (Steve Stevenson)
  8. Nntp-Posting-Host: luna.think.com
  9. Organization: Thinking Machines Corporation, Cambridge MA, USA
  10. References: <1992Dec27.201910.28352@ee.eng.ohio-state.edu>
  11.     <1992Dec29.142815.27527@hubcap.clemson.edu>
  12. Date: 29 Dec 92 12:20:20
  13. Approved: parallel@hubcap.clemson.edu
  14. Lines: 36
  15.  
  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.    First of all, I was under the impression that the usual interpretation
  26.    of a "torus" network was *always* 2-D.  Perhaps the speaker meant "2-D
  27.    hypercube," i.e. the 4-node hypercube, which would in fact match the
  28.    4-node 2x2 torus.
  29.  
  30. To me, if unmodified, "grid" implies 2D, but I have no problem with either
  31. 3D grid or 3D torus, or higher dimensions of both.
  32.  
  33. Tommy Kelly mentioned that, both hypercubes and torii are k-ary n-cubes.  I
  34. usually think of hypercubes and grids in this fashion, but it's a small
  35. difference.
  36.  
  37.    Also, it turns out the 16-node (4-D) hypercube and the 16-node 4x4 torus
  38.    have the same topology.  But that's the largest number of nodes for
  39.    which this can occur, because in higher dimensions the hypercube nodes
  40.    have degree 5 or greater, but the torus nodes have degree 4.
  41.  
  42. The fact that the 4^2 torus is isomorphic to the binary 4-cube led to an
  43. interesting question here at TMC about six months ago.
  44.  
  45. Is the 4^k torus isomorphic to the binary 2k-cube?
  46.  
  47. The answer and the proof (which I found quite fun) is left as an excercise
  48. to the reader.
  49.  
  50. -steve
  51.  
  52.