home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / parallel / 3038 < prev    next >
Encoding:
Internet Message Format  |  1993-01-28  |  1.4 KB
  1. Xref: sparky comp.parallel:3038 comp.theory:2918
  2. Newsgroups: comp.parallel,comp.theory
  3. Path: sparky!uunet!gatech!hubcap!fpst
  4. From: vram@cc.gatech.edu (Venkataraman Ramanathan)
  5. Subject: Re: Vertex disjoint routing on Hypercube
  6. Message-ID: <1993Jan23.153720.15389@hubcap.clemson.edu>
  7. Apparently-To: comp-parallel@gatech.edu
  8. Sender: news@cc.gatech.edu
  9. Reply-To: vram@cc.gatech.edu (Venkataraman Ramanathan)
  10. Organization: College of Computing
  11. Date: Sat, 23 Jan 1993 15:07:29 GMT
  12. Approved: parallel@hubcap.clemson.edu
  13. Lines: 26
  14.  
  15. Let's say V1 and V2 differ in n bits. By an easy transformation, we could
  16. get V1 to origin and V2 to V. Now, the problem is to find n disjoint routes
  17. from O (origin) to V.  For a 8 dim difference,
  18.  
  19.     1  2  3  4  5  6  7  8
  20.     2  3  4  5  6  7  8  1  (1 rotated)
  21.     3  4  5  6  7  8  1  2  (2 rotated)
  22.         ...
  23.     8  1  2  3  4  5  6  7  (7 rotated, n-1 in general).
  24.  
  25. consider the scheme above. There can be atmost n routes. 
  26. For each route, flip the bits (move in that dimension) according to
  27. the sequence defined by the row.
  28.  
  29. First route is : take dim 1, 2 ... (1 row)
  30. Second route is: take dim 2 first,  3 next, and so on..
  31. And so on..
  32.  
  33. Proof is easy. This rotate-router is very effective. Fill your route number in,
  34. increment and do mod + 1, keep flipping these bits..: that's all.
  35. -
  36. Venkat
  37. (vram@cc)
  38. PS.  I got 10/10 on this homework problem with Dr.Jim Burns.
  39. PPS. Ah! this didnt show up when i posted this through 're'. now it's ok!
  40.  
  41.