Method and apparatus for simulating an interconnection network
Patent 5299317 Issued on March 29, 1994. Estimated Expiration Date: October 2, 2012. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.
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, I1, O1, which characterize the first MIN and by means of the same two algorithms we generate third and fourth vectors, I2 O2, which characterize the second MIN. We then generate fifth and sixth vectors, U, V, where U=O2 * O1-1 and V=I1-1 * I2 where O1-1 and I1-1 are the inverses, respectively, of O1 and I1 and * is a two-operand permutation operation which permutes elements of a first operand (e.g., O2) in accordance with an order specified by a second operand (e.g., O1-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.
Other References
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(log2 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. 198
October 2, 2012. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.
