Method and apparatus for simulating an interconnection network

Details Method and apparatus for simulating an interconnection network Method and apparatus for simulating an interconnection network

1992-10-02

1994-03-29

Shaw, Gareth D.

Boots, shoes, and leggings

364919, 3649291, 3649338, 36494061, 364DIG2, 395800, H04Q 1100

Patent

active

052993175

ABSTRACT:
A method and apparatus are described for simulating on one multi-stage interconnection network (MIN) the operation of a second MIN. By means of two algorithms we generate first and second vectors, I.sub.1, O.sub.1, which characterize the first MIN and by means of the same two algorithms we generate third and fourth vectors, I.sub.2 O.sub.2, which characterize the second MIN. We then generate fifth and sixth vectors, U, V, where U=O.sub.2 * O.sub.1.sup.-1 and V=I.sub.1.sup.-1 * I.sub.2 where O.sub.1.sup.-1 and I.sub.1.sup.-1 are the inverses, respectively, of O.sub.1 and I.sub.1 and * is a two-operand permutation operation which permutes elements of a first operand (e.g., O.sub.2) in accordance with an order specified by a second operand (e.g., O.sub.1.sup.-1). The fifth vector is then used to reorder the inputs to the first MIN; and the sixth vector is used to reorder the outputs from said first MIN. As a result, inputs to the first MIN are mapped to outputs from said first MIN in accordance with the interconnection pattern of said second MIN.

REFERENCES:
patent: 4523273 (1985-06-01), Adams, III et al.
patent: 4785446 (1988-11-01), Dias et al.
patent: 4965788 (1990-10-01), Newman
patent: 4968977 (1990-11-01), Chinnaswamy et al.
D. C. Opferman and N. T. Tsao-Wu, "On a Class of Rearrangeable Switching Networks", Part I and Part II, Bell Syst. Tech J., vol. 50, pp. 1579-1618, May-Jun. 1971.
C. Wu and T. Y. Feng, "On a Class of Multistage Interconnection Networks", IEEE Trans. on Computers, vol. C-29, pp. 694-702, Aug. 1980.
P. Yew and D. H. Lawrie, "An Easily Controlled Network for Frequently Used Permutations", IEEE Trans. on Computers, vol. C-30, No. 4, 1981.
G. B. Adams, III, and H. J. Siegal, "The Extra Stage Cube: A Fault-Tolerant Interconnection Network for Supersystems", IEEE Trans. on Computers, vol. C-31, pp. 443-454, May 1982.
C. P. Kruskal and M. Snir, "A Unified Theory of Interconnection Network Structure", Th. Comp. Sci., vol. 48, No. 1, pp. 75-94, 1986.
C. Clos, "A Study of Non-Blocking Switching Networks", Bell Syst. Tech. J., vol. 32, pp. 406-428, Mar. 1953.
V. E. Benes, "Permutation Groups, Complexes, and Rearrangeable Connecting Networks", Bell Syst. Tech. J., vol. 43, pp. 1619-1640, Jul. 1964.
A. Waksman, "A Permutation Network", J. ACM, vol. 15, pp. 159-163, Jan. 1968.
L. R. Goke and G. J. Lipowski, "Banyan Networks for Partitioning Multiprocessor Systems", 1st Annual Symposium on Computer Architecture, pp. 21-28, 1973.
T. Y. Feng, "Data Manipulating Functions in Parallel Processors and Their Implementations", IEEE Trans. Comput., vol. C-23, pp. 309-318, Mar. 1974.
B. E. Benes, "Proving the Rearrangeability of Connecting Networks by Group Calculations", Bell Syst. Tech. J., vol. 54, pp. 421-434, Feb. 1975.
D. Lawrie, "Access and Alignment of Data in an Array Processor", IEEE Trans. Comput., vol. C-24, pp. 1145-1155, Dec. 1975.
K. E. Batcher, "The Flip Network in Staran", Proc. Int. Conf. Parallel Processing, pp. 65-71, Aug. 1976.
M. C. Pease, "The Indirect Binary n-Cube Microprocessor Array", IEEE Trans. Comput., vol. C-26, pp. 458-473, May 1977.
H. J. Siegel and D. S. Smith, "Study of Multistage SIMD Interconnection Networks", Proc. 5th Annu. Symp. Comput. Arch., New York, NY pp. 223-229, Apr. 1978.
H. J. Siegel, "Interconnection Networks for SIMD Machines", IEEE Computer, vol. 12, pp. 57-65, Jun. 1979.
D. S. Parker, "Notes on Shuffle/Exchange-Type Switching Networks", IEEE Trans. Comput., vol. C-29, pp. 213-221, Mar. 1980.
P. Yew and D. H. Lawrie, "An Easily Controlled Network for Frequently Used Permutations", IEEE Trans. Comput., vol. C-30 No. 4, 1981.
G. P. Lev, N. Pippenger and L. G. Valiant, "A Fast Parallel Algorithm for Routing in Permutation Networks", IEEE Trans. Comput., vol. C-30, pp. 93-100, Feb. 1981.
J. H. Patel, "Performance of Processor-Memory Interconnections for Multiprocessors", IEEE Trans. Comput., vol. C-30, pp. 771-780, Oct. 1981.
T. Y. Feng, "a Survey of Interconnection Networks", IEEE Computer, vol. 14, No. 12, pp. 12-27, Dec. 1981.
H. J. Siegel and R. J. McMillen, "The Multistage Cube: A Versatile Interconnection Network", IEEE Computer, vol. 14, pp. 65-76, Dec. 1981.
U. V. Premkumer and J. C. Browne, "Resource Allocation in Rectangular SW Banyans", 9th Annual Symposium on Computer Architecture, pp. 326-333, 1982.
G. B. Adams, III, and H. J. Siegel, "The Extra Stage Cube: A Fault-Tolerant Interconnection Network for Supersystems", IEEE Trans. Comput., vol. C-31, pp. 443-454, May 1982.
D. P. Agrawal, "Graph Theoretical Analysis and Design of Multistage Interconnection Networks", IEEE Trans. Comput., vol. C-32, pp. 637-648, Jul. 1983.
H. J. Siegel, "Interconnection Networks for Large-Scale Parallel Processing", Lexington Books, pp. 113-174, 1985.
K. Y. Lee, "On the Rearrangeability of 2(log.sub.2 N)-1 Stage Permutation Networks", IEEE Trans. Comput., vol. C-35, pp. 412-425, Jul. 1986.
S. T. Huang and S. K. Tripathi, "Finite State Model and Compatibility Theory. New Analysis Tools for Permutation Networks", IEEE Trans. Comput., vol. C-35, pp. 591-601, Jul. 1986.
W. Lin and C. L. Wu, "Reconfiguration Procedures for a Polymorphic and Partitionable Multiprocessor", IEEE Trans. Comput., vol. C-35, pp. 910-916, Oct. 1986.
C. P. Kruskal and M. Snir, "A Unified Theory of Interconnection Network Strcuture", Th. Comp. Sci., vol. 48, No. 1, pp. 75-94, 1986.
J. C. Bermond and J. M. Fourneau, "Independent Connections: An Easy Characterization of Baseline-Equivalent Multistage Interconnection Networks", Proc. Int. Conf. Parallel Processing, pp. 187-190, 1988.
R. Boppana and C. S. Raghavendra, "On Self Routing in Benes and Shuffle Exchange Networks", Proceedings of International Conf. on Parallel Processing, pp. 196-200, 1988.
D. P. Agrawal, S. Kim, and N. K. Swain, "Analysis and Design of Nonequivalent Multistage Interconnection Networks", IEEE Trans. Comput., vol. C-37, pp. 232-237, Feb. 1988.

Affiliated with

Also associated with

Rating

Method and apparatus for simulating an interconnection network does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for simulating an interconnection network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for simulating an interconnection network will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-799731