Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2007-12-25
2007-12-25
Holmes, Michael B. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
10468991
ABSTRACT:
Methods and systems for performing arithmetic functions. In accordance with a first aspect of the invention, methods and apparatus are provided, working in conjunction of software algorithms and hardware implementation of class network routing, to achieve a very significant reduction in the time required for global arithmetic operation on the torus. Therefore, it leads to greater scalability of applications running on large parallel machines. The invention involves three steps in improving the efficiency and accuracy of global operations: (1) Ensuring, when necessary, that all the nodes do the global operation on the data in the same order and so obtain a unique answer, independent of roundoff error; (2) Using the topology of the torus to minimize the number of hops and the bidirectional capabilities of the network to reduce the number of time steps in the data transfer operation to an absolute minimum; and (3) Using class function routing to reduce latency in the data transfer. With the method of this invention, every single element is injected into the network only once and it will be stored and forwarded without any further software overhead. In accordance with a second aspect of the invention, methods and systems are provided to efficiently implement global arithmetic operations on a network that supports the global combining operations. The latency of doing such global operations are greatly reduced by using these methods.
REFERENCES:
patent: 5471580 (1995-11-01), Fujiwara et al.
patent: 5590345 (1996-12-01), Barker et al.
patent: 5611070 (1997-03-01), Heidelberger et al.
patent: 5634096 (1997-05-01), Baylor et al.
patent: 5809292 (1998-09-01), Wilkinson et al.
patent: 6205532 (2001-03-01), Carvey et al.
patent: 6219762 (2001-04-01), Hasegawa et al.
patent: 6279092 (2001-08-01), Franaszek et al.
patent: 6434675 (2002-08-01), Hasegawa et al.
patent: 6539460 (2003-03-01), Castelli et al.
patent: 6606656 (2003-08-01), Carvey et al.
patent: 6622233 (2003-09-01), Gilson
patent: 6714552 (2004-03-01), Cotter
patent: 6810495 (2004-10-01), Castelli et al.
patent: 6895416 (2005-05-01), Gara et al.
patent: 6976064 (2005-12-01), Carvey et al.
patent: 7024512 (2006-04-01), Franaszek et al.
patent: 7039769 (2006-05-01), Castelli et al.
patent: 7051185 (2006-05-01), Gilson
patent: 7149920 (2006-12-01), Blumrich et al.
patent: 7174434 (2007-02-01), Blumrich et al.
patent: 7185226 (2007-02-01), Chen et al.
patent: 7210088 (2007-04-01), Chen et al.
Network decontamination with local immunization Fabrizio, L.; Pagli, L.; Santoro, N.; Parallel and Distributed Processing Symposium, 2006. IPDPS 2006. 20th International Apr. 25-29, 2006 p. 8 pp. Digital Object Identifier 10.1109/IPDPS.2006.1639553.
Polymorphic-torus architecture for computer vision Li, H.; Maresca, M.; Pattern Analysis and Machine Intelligence, IEEE Transactions on Vol. 11, Issue 3, Mar. 1989 pp. 233-243 Digital Object Identifier 10.1109/34.21792.
A unified formulation of honeycomb and diamond networks Parhami, B.; Ding-Ming Kwai; Parallel and Distributed Systems, IEEE Transactions on Vol. 12, Issue 1, Jan. 2001 pp. 74-80 Digital Object Identifier 10.1109/71.899940.
Efficient mapping algorithm of multilayer neural network on torus architecture Ayoubi, R.A.; Bayoumi, M.A.; Parallel and Distributed Systems, IEEE Transactions on Vol. 14, Issue 9, Sep. 2003 pp. 932-943 Digital Object Identifier 10-1109/TPDS.2003.1233715.
A Scalable Distributed Parallel Breadth-First Search Algorithm on BlueGene/L Yoo, A.; Chow, E.; Henderson, K.; McLendon, W.; Hendrickson, B.; Catalyurek, U.; Supercomputing, 2005. Proceedings of the ACM/IEEE SC 2005 Conference Nov. 12-18, 2005 pp. 25-25 Digital Object Identifier 10.1109/SC.2005.4.
Scalable distributed architecture of the terabit router Fan Li-Jun; Quan Cheng-bin; Luan Gui-Xing; Asian Green Electronics, 2004. AGEC. Proceedings of 2004 International IEEE Conference on the 2004 pp. 186-189 Digital Object Identifier 10.1109/AGEC.2004.1290899.
A peer-to-peer network based on multi-mesh architecture Murthy, S.; Sen, A.; Global Telecommunications Conference, 2003. GLOBECOM '03. IEEE Vol. 7, Dec. 1-5, 2003 pp. 3840-3844 Vol. 7 Digital Object Identifier 10.1109/GLOBECOM.2003.1258950.
Scalable distributed architecture of the terabit router Fan Li-Jun; Quan Cheng-bin; Luan Gui-Xing; Parallel and Distributed Computing, Applications and Technologies, 2003. PDCAT'2003. Proceedings of the Fourth International Conference on Aug. 27-29, 2003 pp. 472-475.
A communication model based on an n-dimensional torus architecture using deadlock-free wormhole routing Holzenspies, P.; Schepers, E.; Bach, W.; Jonker, M.; Sikkes, B.; Smit, G.; Havinga, P.; Digital System Design, 2003. Proceedings. Euromicro Symposium on Sep. 1-6, 2003 pp. 166-172 Digital Object Identifier 10.1109/DSD.2003.1231920.
The P-Mesh-a commodity-based scalable network architecture for clusters Nitzberg, B.; Kuszmaul, C.; Stockdale, I.; Becker, J.; Jiang, J.; Wong, P.; System Sciences, 1999, HICSS-32. Proceedings of the 32nd Annual Hawaii International Conference on Vol. Track8, Jan. 5-8, 1999 pp. 10 pp. Digital Object Identifier 10.1109/HICSS.1999.773070.
Data level parallel processing for object recognition on Recursive Torus Architecture Matsuyama, T.; Asada, N.; Aoyama, M.; Kamashita, A.; Asazu, H.; Yamamoto, H.; Ogawa, K.; Computer Architectures for Machine Perception, 1995. Proceedings. CAMP '95 Sep. 18-20, 1995 pp. 90-97 Digital Object Identifier 10.1109/CAMP.1995.521023.
Connected component labeling on polymorphic torus architecture Maresca, M.; Li, H.; Lavin, M.; Computer Vision and Pattern Recognition, 1988. Proceedings CVPR.'88., Computer Society Conference on Jun. 5-9, 1988 pp. 951-956 Digital Object Identifier 10.1109/CVPR.1988.196347.
Parallel image analysis on recursive Torus architecture Matsuyama, T.; Asada, N.; Aoyama, M.; Computer Architectures for Machine Perception, 1993. Proceedings Dec. 15-17, 1993 pp. 202-214 Digital Object Identifier 10.1109/CAMP.1993.622474.
Exploiting multiple degrees of BP parallelism on the highly parallel computer AP1000 Torresen, J.; Mori, S.; Nakashima, H.; Tomita, S.; Landsverk, O.; Artificial Neural Networks, 1995., Fourth International Conference on Jun. 26-28, 1995 pp. 483-488.
Bhanot Gyan
Blumrich Matthias A.
Chen Dong
Gara Alan G.
Giampapa Mark E.
Holmes Michael B.
International Business Machines - Corporation
Morris, Esq. Daniel P.
Scully , Scott, Murphy & Presser, P.C.
LandOfFree
Arithmetic functions in torus and tree networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Arithmetic functions in torus and tree networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arithmetic functions in torus and tree networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3840393