A new approach to fast control of r2× r2 3-stage benes networks of r×r crossbar switches
Pages 50 - 59
Abstract
The routing control of Benes networks has proven to be costly. This paper introduces a new approach to fast control of N × N 3-stage Benes networks of r × r crossbar switches as building blocks, where N = r2 and r ≥ 2. The new approach consists of setting the leftmost column of switches to an appropriately chosen configuration so that the network becomes self-routed while still able to realize a given family of permutations. This approach requires that, for any given family of permutations, a configuration for the leftmost column be found. Such a family is called compatible and the configuration of the leftmost column is called the compatibility factor. In this paper, compatibility is characterized and a technique to determine compatibility and the compatibility factor is developed. The technique is used to show the compatibility and find the compatibility factor of Ω-realizable permutations, the permutations needed to emulate a hypercube, and the families of permutations required by FFT, bitonic sorting, tree computations, multidimensional mesh and torus computations, and multigrid computations. An O(log2 N) time routing algorithm for the 3-stage Benes will also be developed. Finally, as only 3 compatibility factors are required by the above families of permutations, it will be proposed to replace the first column by 3 multiplexed connections yielding a self-routing network with strong communication capabilities.
References
[1]
D. I'. Agrawal and J. -S. Leu, Dynamic accessibiIity testing and path length optimization of multistage interconnection networks, IEEE Trans. Comput., C-34, pp. 255-266, Mar. 1985.
[2]
M. Ajtai, J. Kanlos and E. Szemeredi, Sorting in clog n parallel steps, Combinatorics 3, pp. 1-19, 1983.
[3]
K. E. Batcher, Sorting networks and their applications, 1968 Spring Joint Comput. Conf., AFIPS Conf Vol. 32, Washington, D.C.: Thompson, 1968, pp. 307-314.
[4]
J. Beetem, M. Denneau, and D. Weingarten, The GFll Supercomputer, The 12th an?. Int'l Sump. on Camp. Arch., 1985, pp. 108-113.
[5]
V. E. Benes, Mathematical theory on connecting networh and telephone trafic, Academic Press, New York, 1965.
[6]
L. N. Bhuyan and D. P. Agrawal, Design and performance of generalized interconnection networks, IEEE Zkans. Comput., pp. 1081-1090, Dec. 1983.
[7]
A. Brandt, Multigrid Solvers on parallel computers, in Elliptic Problem Solvers (M. Schultz, ed.), New York, pp. 39-83, 1981.
[8]
T. F. Chan and Y. Saad, Multigrid algorithms on the Hypercube multiprocessor,' IEEE Trans. Comput., vol. C-35, pp. 969977, Nov. 1986.
[9]
T. Feng, A survey of interconnection networks, Computer, Vol. 14, pp. 12-27, Dec. 1981.
[10]
D. K. Lawrie, LAccess and alignment of data in an arrary processor IEEE Trans. Comput., C-24, pp. 1145-1155, Dec. 1975.
[11]
K. Y. Lee, On the rearrangeability of 2(logzN) - 1 stage permutation networks, IEEE lkans. Comput., C-34, pp. 412425, May 1985.
[12]
K. Y. Lee, A Nerw Benes Network Control Algo rithm, IEEE Trans. Comput., C-36, pp. 768-772, May 1987.
[13]
J. Lenfant, Parallel permutations of data: A Benes network control algorithm for frequently used permutations, IEEE Trans. Comput., C-27, pp. 637-647, July 1978.
[14]
G. F. Lev, N. Pippenger and L. G. Valiant, A fast parallel algorithm for routing in permutation networks, IEEE Trans. Comput., C-,30 pp. 93-100, Feb. 1981.
[15]
D. Nassimi ans S. Sahni, A self-routing Benes network and parallel permutation algorithms, IEEE Tram. Comput., C-30, pp. 332-340, May 1981.
[16]
D. C. Opferman and N. T. TsaoWu, On a class of rearrangeable switching networks, Parts I and II, Bell Syst. Tech. J., pp. 1579-1618, May-June 1971.
[17]
M. C. Pease, The indirect binary n-cube multiprocessor array, IEEE !lkans. Cornput., C-26, pp. 458473, May 1976.
[18]
H. J. Siegel and S. Smith, Study of multistage interconnection networks,' Proe. Fifth Annual Symp. Comp. Arch., pp. 223-229, Apr. 1978.
[19]
H. S. Stone, Parallel processing with the perfect shuffle, IEEE Trans. Comput., C-20, pp, 153-161, Feb. 1971.
[20]
Q. F. Stout, UHypercubes and Pyramids, in Pyramidal System for Computer Vision, edited by V. Cantoni and S. Levialdi, Springer-Verlag, Berlin, 1986.
[21]
T. H. Szymanski and V. C. Hamacher, On the permutation Capibility of multistage interconnection networks, IEEE Bans. Cornput., C-36, pp. 810-822, July 1987.
[22]
A. Waksman, A permutation network, JACM, Vol. 15, No. 1 pp. 159-163, Jan 1968.
[23]
C. Wu and T. Feng, On a class of multistage interconnection networks, IEEE Trans. Comput., C-29, pp. 694-702, Aug. 1980.
[24]
A. Youssef, Properties of multistage interconnection networka, Ph.D. dissertation, Princeton University, Feb. 1988.
Index Terms
- A new approach to fast control of r2× r2 3-stage benes networks of r×r crossbar switches
Recommendations
A new approach to fast control of r2× r2 3-stage benes networks of r×r crossbar switches
ISCA '90: Proceedings of the 17th annual international symposium on Computer ArchitectureThe routing control of Benes networks has proven to be costly. This paper introduces a new approach to fast control of N × N 3-stage Benes networks of r × r crossbar switches as building blocks, where N = r2 and r ≥ 2. The new approach consists of ...
Symmetric Crossbar Arbiters for VLSI Communication Switches
The design and implementation of symmetric crossbar arbiters are addressed. Severalarbiter designs are compared based on simulations of a multistage interconnectionnetwork. These simulations demonstrate the influence of the switch arbitration policy ...
Performance of the r-truncated Benes networks under randomized routing algorithms
ICPADS '97: Proceedings of the 1997 International Conference on Parallel and Distributed SystemsBenes networks have the potential for balanced traffic, fewer conflicts, and can route any permutation in one pass due to their multiplicity of paths. Omega networks, on the other hand, have fast set-up and low hardware cost, but could take more than ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 1990
356 pages
ISSN:0163-5964
DOI:10.1145/325096
- Chairmen:
- Jean-Loup Baer,
- Larry Snyder,
- James Goodman
May 1990378 pages
Copyright © 1990 Authors.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 May 1990
Published in SIGARCH Volume 18, Issue 2SI
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 493Total Downloads
- Downloads (Last 12 months)122
- Downloads (Last 6 weeks)29
Reflects downloads up to 12 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in