Telecommunications – Receiver or analog modulated signal frequency converter – With particular receiver circuit
Reexamination Certificate
1999-02-17
2002-09-24
Maung, Nay (Department: 2681)
Telecommunications
Receiver or analog modulated signal frequency converter
With particular receiver circuit
C370S380000
Reexamination Certificate
active
06456838
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: 5467211 (1995-11-01), Hnaey et al.
patent: 5541914 (1996-07-01), Krishnamoorthy et al.
patent: 5634004 (1997-05-01), Gopinath
patent: 5856977 (1999-01-01), Yang et al.
patent: 6335930 (2002-01-01), Lee
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 for Challenges on 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., “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-Routed Torus,” IEEE Trans. Parallel 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
Gelin Jean A
Maung Nay
Suchyta Leonard Charles
Verizon Laboratories Inc.
Weixel James K.
LandOfFree
Generic approach to generating permutations for all-to-all... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Generic approach to generating permutations for all-to-all..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generic approach to generating permutations for all-to-all... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2874663