In the version of this network introduced by Tomas Lang and Harold S. Stone in 1976,[2] simplifying earlier work of Stone in 1971,[3] the shuffle-exchange network of order consisted of an array of cells, numbered by the different binary numbers that can be represented with bits. These cells were connected by communications links in two different patterns: "exchange" links in which each cell is connected to the cell numbered with the opposite value in its lowest-order bit, and "shuffle" links in which each cell is connected to the cell whose number is obtained by a circular shift that shifts every bit to the next more significant position, except for the highest-order bit which shifts into the lowest-order position. The "exchange" links are bidirectional, while the "shuffle" links can only transfer information in one direction, from a cell to its circular shift.[2]
Subsequent work on networks with this topology removed the distinction between unidirectional and bidirectional communication links, allowing information to flow in either direction across each link.[1][4]
Applicationsedit
The advantage of this communications pattern, over earlier methods, is that it allows information to be rapidly transferred through a small number of steps from any vertex in the network to any other vertex, while only requiring a single bit of control information (which of the two communications links to use) for each communications step.[2] Fast parallel algorithms for basic problems including sorting, matrix multiplication, polynomial evaluation, and Fourier transforms are known for parallel systems using this network.[4]
Layout areaedit
If this network is given a straightforward layout in the integer lattice, with the vertices placed on a line in numerical order, with each lattice edge carrying part of at most one communication link, and with each vertex or crossing of the network placed at a lattice point, the layout uses area , quadratic in its number of vertices. However, more compact and asymptotically optimal layouts with area were described by F. Thomson Leighton in his 1981 doctoral dissertation.[4]
Related networksedit
A related communications network, the "omega network" or multi-stage shuffle-exchange network, consists of a given number of stages, each consisting of vertices, with the shuffle links connecting pairs of vertices in consecutive stages and the exchange links connecting pairs of vertices in the same stage as each other.[5]
The same operations on binary words, of rotation and flipping the first bit, can also be used to generate the cube-connected cycles, a different cubic parallel communications network with a greater number of vertices. Instead of having the binary words themselves as its vertices, the vertices of the cube-connected cycles represent operations on words that can be generated by rotation and flipping, and the edges represent the composition of one of these operations with an additional rotation or flip.[6]
Referencesedit
^ abGraham, Niall; Harary, Frank (1993), "Hypercubes, shuffle-exchange graphs and de Bruijn digraphs", Mathematical and Computer Modelling, 17 (11): 69–74, doi:10.1016/0895-7177(93)90255-W, MR 1236511
^ abcLang, Tomas; Stone, Harold S. (January 1976), "A shuffle-exchange network with simplified control", IEEE Transactions on Computers, C-25 (1): 55–65, doi:10.1109/tc.1976.5009205
^Stone, H.S. (February 1971), "Parallel processing with the perfect shuffle", IEEE Transactions on Computers, C-20 (2), Institute of Electrical and Electronics Engineers ({IEEE}): 153–161, doi:10.1109/t-c.1971.223205
^ abcLeighton, F. Thomson (1981), Layouts for the Shuffle-Exchange Graph and Lower Bound Techniques for VLSI(PDF) (Ph.D. dissertation), Massachusetts Institute of Technology, MR 2941014, (PDF) from the original on February 27, 2021 – via Defense Technical Information Center
^Lawrie, Duncan H. (1975), "Access and alignment of data in an array processor", IEEE Transactions on Computers, C-24 (12): 1145–1155, doi:10.1109/t-c.1975.224157, MR 0383864
^Annexstein, Fred; Baumslag, Marc; Rosenberg, Arnold L. (1990), "Group action graphs and parallel architectures", SIAM Journal on Computing, 19 (3): 544–569, doi:10.1137/0219037
April 15, 2024
shuffle, exchange, network, graph, theory, shuffle, exchange, network, undirected, cubic, multigraph, whose, vertices, represent, binary, sequences, given, length, whose, edges, represent, operations, these, sequence, circular, shifts, flipping, lowest, order,. In graph theory the shuffle exchange network is an undirected cubic multigraph whose vertices represent binary sequences of a given length and whose edges represent two operations on these sequence circular shifts and flipping the lowest order bit 1 The order 4 shuffle exchange network with its vertices arranged in numerical order Contents 1 Definition 2 Applications 3 Layout area 4 Related networks 5 ReferencesDefinition editIn the version of this network introduced by Tomas Lang and Harold S Stone in 1976 2 simplifying earlier work of Stone in 1971 3 the shuffle exchange network of order d displaystyle d nbsp consisted of an array of 2d displaystyle 2 d nbsp cells numbered by the 2d displaystyle 2 d nbsp different binary numbers that can be represented with d displaystyle d nbsp bits These cells were connected by communications links in two different patterns exchange links in which each cell is connected to the cell numbered with the opposite value in its lowest order bit and shuffle links in which each cell is connected to the cell whose number is obtained by a circular shift that shifts every bit to the next more significant position except for the highest order bit which shifts into the lowest order position The exchange links are bidirectional while the shuffle links can only transfer information in one direction from a cell to its circular shift 2 Subsequent work on networks with this topology removed the distinction between unidirectional and bidirectional communication links allowing information to flow in either direction across each link 1 4 Applications editThe advantage of this communications pattern over earlier methods is that it allows information to be rapidly transferred through a small number of steps from any vertex in the network to any other vertex while only requiring a single bit of control information which of the two communications links to use for each communications step 2 Fast parallel algorithms for basic problems including sorting matrix multiplication polynomial evaluation and Fourier transforms are known for parallel systems using this network 4 Layout area editIf this network is given a straightforward layout in the integer lattice with the vertices placed on a line in numerical order with each lattice edge carrying part of at most one communication link and with each vertex or crossing of the network placed at a lattice point the layout uses area O 22d displaystyle O 2 2d nbsp quadratic in its number of vertices However more compact and asymptotically optimal layouts with area O 22d d2 displaystyle O 2 2d d 2 nbsp were described by F Thomson Leighton in his 1981 doctoral dissertation 4 Related networks editA related communications network the omega network or multi stage shuffle exchange network consists of a given number of stages each consisting of 2d displaystyle 2 d nbsp vertices with the shuffle links connecting pairs of vertices in consecutive stages and the exchange links connecting pairs of vertices in the same stage as each other 5 The same operations on binary words of rotation and flipping the first bit can also be used to generate the cube connected cycles a different cubic parallel communications network with a greater number of vertices Instead of having the binary words themselves as its vertices the vertices of the cube connected cycles represent operations on words that can be generated by rotation and flipping and the edges represent the composition of one of these operations with an additional rotation or flip 6 References edit a b Graham Niall Harary Frank 1993 Hypercubes shuffle exchange graphs and de Bruijn digraphs Mathematical and Computer Modelling 17 11 69 74 doi 10 1016 0895 7177 93 90255 W MR 1236511 a b c Lang Tomas Stone Harold S January 1976 A shuffle exchange network with simplified control IEEE Transactions on Computers C 25 1 55 65 doi 10 1109 tc 1976 5009205 Stone H S February 1971 Parallel processing with the perfect shuffle IEEE Transactions on Computers C 20 2 Institute of Electrical and Electronics Engineers IEEE 153 161 doi 10 1109 t c 1971 223205 a b c Leighton F Thomson 1981 Layouts for the Shuffle Exchange Graph and Lower Bound Techniques for VLSI PDF Ph D dissertation Massachusetts Institute of Technology MR 2941014 archived PDF from the original on February 27 2021 via Defense Technical Information Center Lawrie Duncan H 1975 Access and alignment of data in an array processor IEEE Transactions on Computers C 24 12 1145 1155 doi 10 1109 t c 1975 224157 MR 0383864 Annexstein Fred Baumslag Marc Rosenberg Arnold L 1990 Group action graphs and parallel architectures SIAM Journal on Computing 19 3 544 569 doi 10 1137 0219037 Retrieved from https en wikipedia org w index php title Shuffle exchange network amp oldid 1144345139, wikipedia, wiki, book, books, library,
