Multiplex communications – Wide area network – Packet switching
Patent
1995-01-24
1996-04-30
Bowler, Alyssa H.
Multiplex communications
Wide area network
Packet switching
370 60, 364229, 364DIG1, G06F 1500
Patent
active
055133711
ABSTRACT:
Two new classes of interconnection networks are described. The new classes of interconnection networks are referred to herein as the hierarchical shuffle-exchange (HSE) and hierarchical de Bruijn (HdB) networks. The new HSE and HdB networks are highly regular and scalable and are thus well suited to VSLI implementation. In addition, they can be adjusted to match any set of packaging constraints. These new networks are also efficient in supporting the execution of a wide range of algorithms on computers whose processors are interconnected via one of the networks fabricated in accordance with the teachings of the invention. Such computers, also contemplated by the invention, are referred to herein as HSE and HbB computers. Furthermore, methods for implementing the aforementioned wide range of algorithms, particularly those in the classes of Ascend and Descend algorithms, on the novel HSE and HdB computers, constitute a further aspect of the invention.
REFERENCES:
patent: 4583164 (1986-04-01), Tolle
patent: 4591981 (1986-05-01), Kassabov
patent: 4622632 (1986-11-01), Tanimoto et al.
patent: 4805091 (1989-02-01), Thiel et al.
patent: 4814970 (1989-03-01), Barbagelata et al.
patent: 4843540 (1989-06-01), Stolfo
patent: 4901360 (1990-02-01), Shu et al.
patent: 5020059 (1991-05-01), Gorin et al.
patent: 5134690 (1992-07-01), Samatham
patent: 5173689 (1992-12-01), Kusano
R. Cypher & J. L. C. Sanz, Hierarchical Shuffle-Exchange and de Bruijn Networks, Proceedings of the 4th IEEE Symposium on Parallel Dist. Processing, pp. 491-496, Dec. 14, 1992.
C. Chen, D. P. Agrawal, J. R. Burke, Proceedings, Advanced Computer Tech., Reliable Sys. & Applications, 5th Annual European Computer Conf. Design and WSI Layout for DBCube Networks, pp. 363-367, May 13-16, 1991.
C. Chen, D. P. Agrawal, J. R. Burke, A Class of Hierarchical Networks for VLSI/WSI Based Multicomputers, WLSI Design '91, Digest of Papers, 4th CSI/IEEE International Symposium on VLSI Design, New Delhi, India, pp. 267-272, Jan. 4-8, 1991.
K. Padmanabhan, Hierarchical Communication in Cube-Connected Multiprocessors, Proceedings, 10th International Conf. on Distributed Computing Systems, IEEE pp. 270-277, May 28 to Jun. 1, 1990.
T. Lang, H. Stone, A Shuffle-Exchange Network with Simplified Control, IEEE Transactions on Computers, vol. C-25 No. 1, pp. 55-65, Jan. 1976.
Roychowdhury et al., Efficient Algorithms for Reconfiguration in VLSI/WSI Arrays, IEEE Trans. on Computers, vol. 39, No. 4, Apr. 1990.
O. Collins, "Wiring Viterbi Decoders (Splitting deBruijn Graphs)", NASA, Pasadena, CA, The Telecommunications & Data Acquisition Progress Report 42-96, Oct./Dec. 1988.
Georgescu, "Communication in Parallel Processing Systems," Studies and Researches in Computer and Informatics, vol. 1, No. 1, Mar. 1990, pp. 7-44.
Hwang, "Hypernet: A Communication-Efficient Architecture for Constructing Massively Parallel Computers," IEEE Transactions on Computers, C-36(12), Dec. 1987, pp. 1450-1466.
Kumar et al., "The GF11 Parallel Computer: Programming and Performance," IBM Research Report RC15494 (#68945), Feb. 1990.
Fulgham et al., "A Comparison of SIMD Hypercube Routing Strategies," Proceedings of the International Conference on Parallel Processing, vol. III, 1990, pp. 236-243.
Cypher et al., "SIMD Architectures and Algorithms for Image Processing and Computer Vision," IEEE Transactions on Acoustics, Speech, and Signal Processing, 37(12), Dec. 1989, pp. 2158-2174.
Samatham et al., "The DeBruun Multiprocessor Network: A Versatile Parallel Processing and Sorting Network for VLSI," IEEE Transactions on Computers, 38(4), Apr. 1989, pp. 567-581.
Cypher, "Theoretical Aspects of VLSI PIN Limitations," Technical Report 89-02-01, University of Washington, Department of Computer Science, Feb. 1989.
Dandamudi et al., "Hierarchical Interconnection Networks for Multiprocessor Systems," IEEE Transactions on Computers, 39(6), Jun. 1990, pp. 786-797.
Ghose et al., "The Design and Evaluation of the Hierarchical Cubic Network," Proceedings of the International Conference on Parallel Processing, 1990, pp. 355-362.
Nassimi et al., "Data Broadcasting in SIMD Computers," IEEE Transactions on Computers, C-30(2), Feb. 1981, pp. 101-107.
Schwartz, "Ultracomputers," ACM Transactions on Programming Languages and Systems, 2(4), Oct. 1980, pp. 484-521.
Stone, "Parallel Processing with the Perfect Shuffle," IEEE Transactions on Computers, C-20(2), Feb. 1971, pp. 153-161.
Bermond et al., "DeBruijn and Kautz Networks: A Competitor for the Hypercube?" Hypercube and Distributed Computers, 1989, pp. 279-293.
Preparata et al., "The Cube-Connected Cycles: A Versatile Network for Parallel Computation," Communications of the ACM, 24(5), pp. 300-309, May 1981.
Batcher, "Sorting Networks and their Applications," Proceedings of the AFIPS Spring Joint Computer Conference, Apr. 1968, pp. 307-314.
Benes, "Optimal Rearrangeable Multistage Connecting Networks," The Bell System Technical Journal, Jul. 1964, pp. 1641-1656.
Waksman, "A Permutation Network," Journal of the ACM, 15(1), Jan. 1968, pp. 159-163.
Schwartz, "Fine Grained and Coarse Grained Parallel Supercomputers, or, Does Anything But Pin Count Matter," Proceedings of the Design Development and Manufacture of Large Computer Systems, Oct. 1984.
Lin et al., "Efficient Histogramming on Hypercube SIMD Machines," Computer Vision, Graphics and Image Processing, 49(1), Jan. 1990, pp. 104-120.
Cypher Robert E.
Sanz Jorge L. C.
Bowler Alyssa H.
Harrity John
International Business Machines - Corporation
Kaliko Joseph J.
Pintner James C.
LandOfFree
Hierarchical interconnection network architecture for parallel p does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hierarchical interconnection network architecture for parallel p, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hierarchical interconnection network architecture for parallel p will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-637377