|
Published Articles >> Table of Contents >> Abstract
August 2000 (Vol. 11, No. 8)
pp. 829-837
Performing Permutations on Interconnection Networks by Regularly Changing Switch States
Wei Kuang Lai
Full Article Text:
   
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/71.877940
Send link to a friend
| Abstract |
|
In this paper, we present an algorithm for performing permutations of messages on multistage interconnection networks. Permutations of messages are needed in many parallel algorithms. The proposed algorithm is feasible for any networks that can connect each input to each output using a set of $N$ nonblocking connections, where $N$ is the number of ports on the network. Messages are segmented into $N$ submessages that are sent independently in each time step. For any permutation, the settings of switches are changed with fixed patterns. Partitioning of the network into independent subnetworks is also supported, each capable of simultaneously routing a different permutation.
|
 References
|
[1] D.S. Parker, Jr., “Notes on Shuffle/Exchange-Type Switching Networks,” IEEE Trans. Computers, vol. 29, no. 3, pp. 213-222, Mar. 1980.
[2] C. Clos, “A Study of Non-blocking Switching Networks,” The Bell System Technical J., pp. 406-424, Mar. 1953.
[3] V.E. $$Bene\v{s}$$, “Optimal Rearrangeable Multistage Connecting Networks,” The Bell System Technical J., pp. 1,641-1,656, July 1964.
[4] H.S. Stone, “Parallel Processing with the Perfect Shuffle,” IEEE Trans. Computers, vol 20, pp. 153-161, Feb. 1971.
[5] T. Lang and H.S. Stone, “A Shuffle-Exchange Network with Simplified Control,” IEEE Trans. Computers, vol. 25, no. 1, pp. 55-65, Jan. 1976.
[6] L.G. Valiant and G.J. Brebner,"Universal Schemes for Parallel Communication," Proc. 13th Ann. ACM Symp. Theory of Computing, pp. 263-277, May 1981.
[7] L.G. Valliant, “A Scheme for Fast Parallel Communication,” SIAM J. Computing, vol. 11, no. 2, pp. 350-361, May 1982.
[8] C.-L. Wu and T.-Y. Feng, “The Reverse-Exchange Interconnection Network,” IEEE Trans. Computers, vol. 29, no. 9, pp. 801-811, Sept. 1980.
[9] C.L. Wu and T.-Y. Feng, “The Universality of the Shuffle-Exchange Network,” IEEE Trans. Computers, vol. 30, no. 5, pp. 324-332, May 1981.
[10] S.T. Huang and S.F. Tripathi,“Finite state model and compatibility theory: New analysis tools for permutation networks,” IEEE Trans. Computers, vol. 35, pp. 591-601, July 1986.
[11] V. Cherkassky and M. Malek, “On Permuting Properties of Regular Rectangular SW-Banyans,” IEEE Trans. Computers, vol. 34, no. 6, pp. 542-546, June 1985.
[12] H.J. Siegel and S.D. Smith, "Study of Multistage SIMD Interconnection Networks," Proc. Fifth Symp. Computer Architecture, pp. 223-229, Apr. 1978.
[13] J.H. Patel, “Performance of Processor-Memory Interconnections for Multiprocessors,” IEEE Trans. Computers, vol. 30, pp. 771-780, 1981. 1981.
[14] M.C. Pease III, “The Indirect Binaryn-Cube Microprocessor Array,” IEEE Trans. Computers, vol. 26, pp. 458-473, May 1977.
[15] D.H. Lawrie, “Access and Alignment of Data in an Array Processor,” IEEE Trans. Computers, vol. 24, pp. 1,145-1,155, Dec. 1975.
[16] K.E. Batcher, “The Flip Network in STARAN,” Proc. 1976 Int'l Conf. Parallel Processing, pp. 65-71, Aug. 1976.
[17] L. R. Goke and G. J. Lipovski,“Banyan networks for partitioning multiprocessor systems,”inFirst Ann. Symp. Comput. Archit., 1973, pp. 21–28.
[18] H.J. Siegel, “A Model of SIMD Machines and a Comparison of Various Interconnection Networks,” IEEE Trans. Computers, vol. 28, pp. 907-917, Dec. 1979.
[19] H.J. Siegel, “Analysis Techniques for SIMD Machine Interconnection Networks and the Effects of Processor Address Masks,” IEEE Trans. Computers, vol. 26, pp. 153-161, Feb. 1977.
[20] H.J. Siegal, “The Theory Underlying the Partitioning of Permutation Network,” IEEE Trans. Computers, vol. 29, pp. 791-801, Sept. 1980.
[21] A.E. Joel, Jr., “On Permutation Dwitching Networks,” The Bell System Technical J., pp. 813-821, May-June 1968.
[22] K.Y. Lee, "A New Benes Network Control Algorithm," IEEE Trans. Computers, vol. 36, no. 6, pp. 768-772, June 1987.
[23] D.C. Opferman and N.T. Tsao-Wu, “On a Class of Rearrangeable Switching Networks, Part I: Control Algorithm,” The Bell System Technical J., pp. 1,579-1,600, May-June 1971.
[24] T.Y. Feng, “A Survey of Interconnection Networks,” IEEE Computer, pp. 12-27, Dec. 1981.
[25] H.J. Siegel, Interconnection Networks for Large-Scale Parallel Processing, Second Ed., McGraw-Hill, New York, 1990.
[26] D. Nassimi and S. Sahni, “Parallel Algorithms to Set up the$$Bene\v{s}$$Permutation Network,” IEEE Trans. Computers, vol. 31, no. 2, pp. 148-154, Feb. 1982.
[27] A.Y. Oruc and M.Y. Oruc, “Programming Cellular Permutation Networks through Decomposition of Symmetric Groups,” IEEE Trans. Computers, vol. 36, no. 7, pp. 802-809, July 1987.
[28] D.P. Agrawal, “Graph Theoretical Analysis and Design of Multistage Interconnection Networks,” IEEE Trans. Computers, vol. 32, no. 7, pp. 637-648, July 1983.
[29] R. Handel, M.N. Huber, and S. Schroder, ATM Networks. Concepts, Protocols, Applications. Second ed., Addison-Wesley, 1994.
[30] P. Mohapatra and C.R. Das, “A Performance Model for Finite-Buffered Multistage Interconnection Networks,” IEEE Trans. Parallel and Distributed Systems, vol. 7, no. 1, pp. 18-25, Jan. 1996.
[31] A. Merchant,"A Markov chain approximation for the analysis of Banyan networks," Proc. ACM SIGMETRICS Conf. Measurement and Modeling of Computer Systems, pp. 60-67, May 1991.
[32] J. Lenfant, “Parallel Permutation of Data: A$$Bene\v{s}$$Network Algorithm for Frequently Used Permutations,” IEEE Trans. Computers, vol. 27, no. 7, pp. 637-647, July 1978.
[33] W.K. Lai, “High-Performance Communication in Parallel Computers,” PhD thesis, Purdue, West Lafayette, Ind., 1992.
[34] W.A. Waksman,“A permutation network,” J. ACM, vol. 15, pp. 159-163, 1968.
[35] C.L. Wu and T.Y. Feng,A Tutorial on Interconnection Network for Parallel and Distributed Processing. IEEE CS Press, 1984.
[36] C. Qiao and R. Melhem, "Reconfiguration with Time Division Multiplexed MIN's for Multiprocessor Communications," IEEE Trans. Parallel and Distributed Systems, vol. 5, no. 4, pp. 337-351, Apr. 1994.
|
 Additional Information
|
Index Terms- Permutation, multistage interconnection networks, deterministic.
Citation:
Wei Kuang Lai,
"Performing Permutations on Interconnection Networks by Regularly Changing Switch States,"
IEEE Transactions on Parallel and Distributed Systems,
vol. 11,
no. 8,
pp. 829-837,
Aug.,
2000
|
|
RSS Feed