Multiplex communications – Pathfinding or routing – Through a circuit switch
Reexamination Certificate
1999-02-17
2002-09-24
Chin, Wellington (Department: 2665)
Multiplex communications
Pathfinding or routing
Through a circuit switch
C370S351000, C370S390000, C370S422000, C370S418000, C712S011000, C712S018000
Reexamination Certificate
active
06456620
ABSTRACT:
BACKGROUND OF THE INVENTION
This application generally relates to networks, and more specifically to communications in a network.
Collective communication generally involves global data movement and global control among a group of nodes in a network. Many scientific applications exhibit the need of such collective communication patterns. For example, efficient support for collective communication may significantly reduce communication latency and simplify the programming of parallel computers. Collective communication has received much attention in telecommunication and parallel processing in recent years.
All-to-all communication is one type of collective communication. In all-to-all communication, every node in a group sends a message to each other node in the group. Depending on the nature of the message to be sent, all-to-all communication can be further classified as all-to-all broadcast and all-to-all personalized exchange. In all-to-all broadcast, every node sends the same message to all other nodes. In all-to all personalized exchange, every node sends a distinct message to every other node. All-to-all broadcast and all-to-all personalized exchange may be used in networking and parallel computational applications. For example, all-to-all broadcasting may be used in performing matrix multiplication, LU-factorization, and Householder transformations. All-to-all personalized exchange may be used, for example, in performing matrix transposition and fast Fourier transforms (FFTs).
Techniques for all-to-all personalized exchange have been considered in different types of networks. A first class of techniques is used in a high-dimensional network type, such as the hypercube. One drawback of using the first class of techniques in a high-dimensional network type is the poor scalability due to the unbounded node degrees of the high-dimensional network topology.
A second class of techniques have been developed for use in mesh and torus networks. These techniques have an advantage over the first techniques in that these network types have bounded node degrees and are more scalable. However, these second techniques used in the mesh and torus networks have a drawback in that long communications delays may be experienced in all-to-all personalized exchange due to the network topology.
Thus, there is required a technique for performing all-to-all personalized exchanges which is scalable while simultaneously seeking to minimize communication delays.
REFERENCES:
patent: 4984237 (1991-01-01), Franaszek
patent: 5142686 (1992-08-01), Hecht et al.
patent: 5361255 (1994-11-01), Diaz et al.
patent: 5671222 (1997-09-01), Chen et al.
patent: 5689500 (1997-11-01), Chiussi et al.
patent: 6201808 (2001-03-01), Wang et al.
J. Duato, et al., “Interconnection Networks: An Engineering Approach”, Chapter 1 and 5, IEEE Computer Society Press, Los Alamitos, CA, 1997.
D.K. Panda, “Issues in Designing Efficient and Practical Algorithms for Collective Communication on Wormhole-Routed Systems,” Proceedings of the 1995 ICPP Workshop on Challenges for Parallel Processing, pp. 8-15, 1995.
Y. Yang, et al., “Nonblocking Broadcast Switching Networks,” IEEE Trans. Computers, vol. C-40, No. 9, pp. 1005-1015, 1991.
Y. Yang, et al., “Broadcast Ring Sandwich Networks,” IEEE Trans. Computers, vol. C-44, No. 10, pp. 1169-1180, 1995.
Y. Yang, “A Class of Interconnection Networks for Multicasting,” IEEE Trans. Computers, vol. C-47, No. 8, pp. 899-906, Aug., 1998.
Y. Yang, et al., “A New Self-Routing Multicast Network,” Proceedings of the First Merged IEEE International Parallel Processing Symposium & Symposium on Parallel and Distributed Processing (IPPS/SPDP '98), Orlando, FL, pp. 351-357, Mar., 1998.
S.L. Johnsson, et al, “Optimum Broadcasting and Personalized Communication in Hypercubes,” IEEE Trans. Computers, vol. C-38, No. 9, pp. 1249-1268, Sep., 1989.
D.S. Scott, “Efficient All-to-All Communication Patterns in Hypercube and Mesh Topologies,” Proceedings of the 6thConference: Distributed Memory Concurrent Computers, pp. 398-403, 1991.
R. Thakur and A. Choudhary, “All-to-All Communication on Meshes with Wormhole Routing,” Proceedings of 8thIEEE International Parallel Processing Symposium, pp. 561-565, Apr., 1994.
Y. Saad, et al., “Data Communication in Parallel Architectures,” Parallel Computing, vol. 11, pp. 131-150, 1989.
Y.-C. Tseng, et al., “All-to-All Personalized Communication in a Wormhole-Routes Torus,” IEEE Trans. Parallel and Distributed Systems, vol. 7, No. 5, pp. 498-505, May, 1996.
Y.-C. Tseng, et al., “Bandwidth-Optimal Complete Exchange on Wormhole Routed 2D/3D Torus Networks: A Diagonal-Propagation Approach,” IEEE Trans. Parallel and Distributed Systems, vol. 8, No. 4, pp. 380-396, Apr., 1997.
F. Petrini, “Total-Exchange on Wormhole K-ary n-cubes with Adaptive Routing,” Proceedings of the First Merged IEEE International Parallel Processing Symposium & Symposium on Parallel and Distributed Processing, pp. 267-271, Orlando, FL, Mar., 1998.
Y.J. Suh, et al., “All-to-All Communication with Minimum Start-up Costs in 2D/3D Tori and Meshes,” IEEE Trans. Parallel and Distributed Systems, vol. 9, No. 5, pp. 442-458, May, 1998.
Y.J. Suh, et al., “Efficient All-to-All Personalized Exchange in Multidimensional Torus Networks,” Proceedings of 1998 International Conference on Parallel Processing, pp. 468-475, Aug. 1998.
D. Gannon, et al., “On the Impact of Communication Complexity in the Design of Parallel Numerical Algorithms,” IEEE Trans. Computer, vol. C-33, pp. 1180-1194, Dec., 1984.
S.L. Johnsson, “Communication Efficient Basic Linear Algebra Computations on Hypercube Architectures,” Journal of Parallel Distributed Computing, vol. 4, pp. 133-172, Apr., 1987.
C.-L. Wu, et al., “On a Class of Multistage Interconnection Networks,” IEEE Trans. Computers, vol. C-29, No. 8, pp. 694-702, Aug., 1980.
C. Clos, “A Study of Non-Blocking Switching Networks,” The Bell System Technical Journal, vol. 32, pp. 406-424, 1953.
V.E. Benes, “Heuristic Remarks and Mathematical Problems Regarding the Theory of Switching Systems,” The Bell System Technical Journal, vol. 41, pp. 1201-1247, 1962.
L.R. Goke, et al., “Banyan Networks for Partitioning Multiprocessor Systems,” Proceedings of the First Annual Symposium on Computer Architecture, 1973, pp. 21-28.
D. Nassimi, et al., “A Self-Routing Benes Network and Parallel Permutation Algorithms,” IEEE Trans. Computers, vol. C-30, No. 5, pp. 332-340, May, 1981.
Wang Jianchao
Yang Yuanyuan
Chin Wellington
Phan M.
Suchyta Leonard Charles
Verizon Laboratories Inc.
Weixel James K.
LandOfFree
Method and apparatus for constructing a latin square matrix... 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 constructing a latin square matrix..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for constructing a latin square matrix... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2901104