Broadcasting a message in a parallel computer

Details Broadcasting a message in a parallel computer Broadcasting a message in a parallel computer

2011-08-02

2011-08-02

Dinh, Khanh Q (Department: 2451)

Electrical computers and digital processing systems: multicomput

Network computer configuring

C709S203000, C709S228000, C370S216000

Reexamination Certificate

active

07991857

ABSTRACT:
Methods, systems, and products are disclosed for broadcasting a message in a parallel computer. The parallel computer includes a plurality of compute nodes connected together using a data communications network. The data communications network optimized for point to point data communications and is characterized by at least two dimensions. The compute nodes are organized into at least one operational group of compute nodes for collective parallel operations of the parallel computer. One compute node of the operational group assigned to be a logical root. Broadcasting a message in a parallel computer includes: establishing a Hamiltonian path along all of the compute nodes in at least one plane of the data communications network and in the operational group; and broadcasting, by the logical root to the remaining compute nodes, the logical root's message along the established Hamiltonian path.

REFERENCES:
patent: 4715032 (1987-12-01), Nilsson
patent: 4843540 (1989-06-01), Stolfo
patent: 5105424 (1992-04-01), Flaig et al.
patent: 5333279 (1994-07-01), Dunning
patent: 5513371 (1996-04-01), Cypher et al.
patent: 5541914 (1996-07-01), Krishnamoorthy et al.
patent: 5617538 (1997-04-01), Heller
patent: 5721828 (1998-02-01), Frisch
patent: 5822604 (1998-10-01), Ogasawara et al.
patent: 5832215 (1998-11-01), Kato et al.
patent: 5864712 (1999-01-01), Carmichael et al.
patent: 5878241 (1999-03-01), Wilkinson et al.
patent: 5892923 (1999-04-01), Yasuda et al.
patent: 5937202 (1999-08-01), Crosetto et al.
patent: 5949988 (1999-09-01), Feisullin et al.
patent: 5958017 (1999-09-01), Scott et al.
patent: 6000024 (1999-12-01), Maddox et al.
patent: 6067609 (2000-05-01), Meeker et al.
patent: 6076131 (2000-06-01), Nugent
patent: 6212617 (2001-04-01), Hardwick
patent: 6272548 (2001-08-01), Cotter et al.
patent: 6289424 (2001-09-01), Stevens
patent: 6292822 (2001-09-01), Hardwick
patent: 6334138 (2001-12-01), Kureya
patent: 6480885 (2002-11-01), Olivier
patent: 6714552 (2004-03-01), Cotter
patent: 6742063 (2004-05-01), Hellum et al.
patent: 6754211 (2004-06-01), Brown
patent: 6914606 (2005-07-01), Amemiya et al.
patent: 7133359 (2006-11-01), Weis
patent: 7263598 (2007-08-01), Ambuel
patent: 7284033 (2007-10-01), Jhani
patent: 7496699 (2009-02-01), Pope et al.
patent: 7499468 (2009-03-01), Montgomery, Jr.
patent: 7539989 (2009-05-01), Blackmore et al.
patent: 7664110 (2010-02-01), Lovett et al.
patent: 2002/0016901 (2002-02-01), Carvey et al.
patent: 2002/0144027 (2002-10-01), Schmisseur
patent: 2003/0188054 (2003-10-01), Yosimoto et al.
patent: 2003/0212877 (2003-11-01), Dally et al.
patent: 2004/0034678 (2004-02-01), Kuszmaul et al.
patent: 2004/0073590 (2004-04-01), Bhanot et al.
patent: 2005/0094577 (2005-05-01), Ashwood-Smith
patent: 2005/0165980 (2005-07-01), Clayton et al.
patent: 2005/0243711 (2005-11-01), Alicherry et al.
patent: 2005/0286411 (2005-12-01), Alicherry et al.
patent: 2006/0168359 (2006-07-01), Bissessur et al.
patent: 2006/0179181 (2006-08-01), Seong
patent: 2007/0110063 (2007-05-01), Tang et al.
patent: 2007/0174558 (2007-07-01), Jia et al.
patent: 2007/0288935 (2007-12-01), Tannenbaum et al.
patent: 2009/0064176 (2009-03-01), Ohly et al.
patent: 2009/0196361 (2009-08-01), Chan et al.
patent: 2009/0292905 (2009-11-01), Faraj
patent: 1835414 (2007-09-01), None
Sunggu Lee; Shin, K.G., “Interleaved all-to-all reliable broadcast on meshes and hypercubes,” Parallel and Distributed Systems, IEEE Transactions on, vol. 5, pp. 449-458, May 1994.
Wikipedia. “Depth-First Search” May 5, 2007. http://web.archive.org/web/20070505212029/http://en.wikipedia.org/wiki/Depth-first—Search.
Bruck J., et al. Efficient Algorithms for all-to-all communications in multiportmessage-passing systems, Parallel and Distributed Systems, IEEE Transactions on, vol. 8, Issue: 11, pp. 1143-1156, Nov. 1997.
U.S. Appl. No. 60/271,124, filed Feb. 24, 2001, pp. 12-13, 27 and 42-43.
Sistare, et al.; Optimization of MPI collectives on clusters of large-scale SMP's, Conference on High Performance Networking and Computing, Proceedings of the 1999 ACM/IEEE conference on Supercomputing; 1999.
Tanenbaum, Structured Computer Organization, Second Edition, Prentice-Hall, Inc., 1984.
Rosenberg; Dictionarty of Computers, Information Processing & Telecommunications, Second Edition, John Wiley & Sons, 1987.
Herbordt, M.C., Weems, C.C.; “Computing Parallel Prefix and Reduction Using Coterie Structures”; Frontiers of Massively Parallel Computation; 1992; Fourth Symposium; Oct. 19-21, 1992; pp. 141-149.
Fisher, et al.; “Computing the Hough Transform on a Scar Line Array Processor”; IEEE Transactions on Pattern Analysis and Machine Intelligence; vol. II, No. 3; Mar. 1989; pp. 262-265.
Office Action, U.S. Appl. No. 11/279,620, Mar. 4, 2008.
Office Action, U.S. Appl. No. 11/279,620, Sep. 3, 2008.
Office Action, U.S. Appl. No. 11/279,620, Dec. 29, 2008.
Office Action, U.S. Appl. No. 11/769,367, Apr. 3, 2009.
Office Action, U.S. Appl. No. 11/459,387, Dec. 13, 2007.
Office Action, U.S. Appl. No. 11/459,387, Jul. 11, 2008.
Office Action, U.S. Appl. No. 11/459,387, Mar. 18, 2009.
Office Action, U.S. Appl. No. 11/737,286, Feb. 9, 2009.
Office Action, U.S. Appl. No. 11/737,209, Jul. 20, 2009.
Office Action, U.S. Appl. No. 11/843,090, Sep. 4, 2009.
M. Matsuda, T. Koduh, Y. Kodama, R. Takano, Y. Ishikawa, “Efficient MPI Collective Operations for Clusters in Long-and-Fast Networks,” cluster, pp. 1-9, 2006 IEEE International Conference on Cluster Computing, Sep. 2006.
DADO: A Tree-Structured Machine Architecture for Production Systems, Stolfo et al. AAAI Proceedings, 1982, Columbia University.
Eunseuk Oh, An All-Reduce Operation in Star Networks Using All-to-All Broadcast Communication Patterns, 2005, 1-8.
Xin Yuan, Bandwidth Efficient All-reduce Operation on Tree Topologies, 2001, 1-8.
Final Office Action, U.S. Appl. No. 11/769,367, Sep. 28, 2010.
Final Office Action, U.S. Appl. No. 12/053,842, Oct. 18, 2010.
Advisory Action, U.S. Appl. No. 12/053,842, Jan. 11, 2011.
Office Action, U.S. Appl. No. 12/053,842, Mar. 1, 2011.
Office Action, U.S. Appl. No. 12/503,902, Oct. 6, 2010.
Office Action, U.S. Appl. No. 12/060,492, May 27, 2010.
Final Office Action, U.S. Appl. No. 12/060,492, Dec. 2, 2010.
Office Action, U.S. Appl. No. 12/124,763, Oct. 14, 2010.
Office Action, U.S. Appl. No. 12/124,756, Oct. 18, 2010.

Affiliated with

Also associated with

Rating

Broadcasting a message in a parallel computer does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Broadcasting a message in a parallel computer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Broadcasting a message in a parallel computer will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2656697