Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
2006-07-04
2006-07-04
Najjar, Saleh (Department: 2155)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C709S243000, C710S001000, C710S031000, C710S033000, C710S034000, C710S038000, C370S351000
Reexamination Certificate
active
07072976
ABSTRACT:
Various embodiments of a scalable routing system for use in an interconnection fabric are disclosed. In this routing scheme, a routing directive describes a route in the interconnection fabric between a sending node and a destination node. Either the sending node or a sending device connected to the sending node encodes the routing directive in a message to be sent to the destination node. The routing directive may include a variable number of segments. Each segment includes a distance component and a direction component that tell each node along the route how it should send the message. Generally, each distance component describes a distance in the interconnection fabric while each direction component specifies a direction in the interconnection fabric.
REFERENCES:
patent: 4862496 (1989-08-01), Kelly et al.
patent: 4980822 (1990-12-01), Brantley et al.
patent: 5088032 (1992-02-01), Bosack
patent: 5101480 (1992-03-01), Shin et al.
patent: 5105424 (1992-04-01), Flaig et al.
patent: 5115495 (1992-05-01), Tsuchiya et al.
patent: 5175733 (1992-12-01), Nugent
patent: 5181017 (1993-01-01), Frey et al.
patent: 5187671 (1993-02-01), Cobb
patent: 5583990 (1996-12-01), Birrittella et al.
patent: 5602839 (1997-02-01), Annapareddy et al.
patent: 5612897 (1997-03-01), Rege
patent: 5613069 (1997-03-01), Walker
patent: 5625836 (1997-04-01), Barker et al.
patent: 5627990 (1997-05-01), Cord et al.
patent: 5646936 (1997-07-01), Shah et al.
patent: 5671356 (1997-09-01), Wang
patent: 5682479 (1997-10-01), Newhall et al.
patent: 5689646 (1997-11-01), Thorson
patent: 5689661 (1997-11-01), Hayashi et al.
patent: 5701416 (1997-12-01), Thorson et al.
patent: 5720025 (1998-02-01), Wilkes et al.
patent: 5729756 (1998-03-01), Hayashi
patent: 5737628 (1998-04-01), Birrittella et al.
patent: 5764641 (1998-06-01), Lin
patent: 5781534 (1998-07-01), Perlman et al.
patent: 5862312 (1999-01-01), Mann et al.
patent: 5912893 (1999-06-01), Rolfe et al.
patent: 5970232 (1999-10-01), Passint et al.
patent: 6016510 (2000-01-01), Quattromani et al.
patent: 6023753 (2000-02-01), Pechanek et al.
patent: 6049527 (2000-04-01), Isoyama et al.
patent: 6055618 (2000-04-01), Thorson
patent: 6072774 (2000-06-01), Natarajan et al.
patent: 6101181 (2000-08-01), Passint et al.
patent: 6128277 (2000-10-01), Bruck et al.
patent: 6145028 (2000-11-01), Shank et al.
patent: 6151299 (2000-11-01), Lyon et al.
patent: 6157962 (2000-12-01), Hodges et al.
patent: 6167502 (2000-12-01), Pechanek et al.
patent: 6330435 (2001-12-01), Lazaraq et al.
patent: 6338129 (2002-01-01), Pechanek et al.
patent: 6370145 (2002-04-01), Dally et al.
patent: 6405185 (2002-06-01), Pechanek et al.
patent: 6434637 (2002-08-01), DErrico
patent: 6567378 (2003-05-01), Yuan et al.
patent: 6658478 (2003-12-01), Singhal et al.
patent: 6718428 (2004-04-01), Lee et al.
patent: 6741561 (2004-05-01), Lee
patent: 6792472 (2004-09-01), Otterness et al.
patent: 2002/0065962 (2002-05-01), Bakke et al.
patent: 2002/0141345 (2002-10-01), Szviatovszki et al.
patent: 2003/0048771 (2003-03-01), Shipman
patent: 199 23 245 (1999-05-01), None
patent: 439 693 (1991-08-01), None
patent: 550 853 (1992-12-01), None
patent: 646 858 (1994-08-01), None
patent: 669 584 (1995-02-01), None
patent: 0 785 512 (1997-07-01), None
patent: 92/06436 (1992-04-01), None
patent: 94/12939 (1994-06-01), None
patent: 99/17217 (1999-04-01), None
patent: 99/26429 (1999-05-01), None
patent: 99/63442 (1999-12-01), None
patent: 00/14932 (2000-03-01), None
G. Albertengo, et al., “Optimal Routing Algorithms for Bidirectional Manhattan Street Network,” IEEE, 1991, 3 pages.
Bradley Kuszmaul, Mercury Computer Systems, Inc., “The RACE Network Architecture,” (posted at www.mc.com/techlit/#tech—brief prior to this), 6 pages.
R.Y. Wang, T.E. Anderson and D.A. Patterson, “Virtual Log Based File Systems For a Programmable Disk,” Proc. Third Symposium on Operating Systems Design and Implementation, Feb. 1999 (Also appeared as University of California Technical Report CSD-98-1031, 16 pages.
Prasant Mohapatra, Wormhole Routing Techniques for Directly Connected Multicomputer Systems, ACM Computing Surveys, vol. 30, No. 3, Sep. 1998, 37 pages.
Christopher Glass and Lionel Ni, “The Turn Model for Adaptive Routing,” Journal of the Association for Computing Machinery, vol. 41, No. 5, Sep. 1994, pp. 874-902.
Reddy, Dept. of Computer & Information Sciences, “A Dynamically Reconfigurable WDM LAN Based on Reconfigurable Circulant Graph,” IEEE. 1996, 4 pages.
Various Abstracts beginning with Funahashi, Jouraku and Amano, “Adaptive Routing for Recursive Diagonal Torus,” Transactions of the Institute of Electronics, Information and Communication Engineers D-I, vol. J83D-I, No. 11, Nov. 2000, pp. 1143-1153.
Milan Kovacevic, Center for Telecommunications Research, “On Torus Topologies with Random Extra Links,” IEEE 1996, pp. 410-418.
Dally, et al., The Torus Routing Chip, Distributed Computing, Springer-Verlag 1986, pp. 187-196.
Susan Hinrichs, “A Compile Time Model for Composing Parallel Programs,” IEEE Parallel and Distributed Technology, 1995, 19 pages.
“CRAY T3D System Architecture Overview Manual,” ftp://ftp.cray.com/product-info/mpp/T3D—Architecture—Over/T3D.overview.html, Cray Research, 1993, 40 pages.
Marco Fillo, et al., “The M-Machine Multicomputer,” Laboratory for Computer Science, Massachusetts Institute of Technology, A.I. Memo No. 1532, Ann Arbor,. Mar. 1995, 14 pages.
Noakes, et al., “The J-Machine Multicomputer: An Architectural Evaluation,” Proceedings of the 20thInternational Symposium on Computer Architecture, May 1993, 12 pages.
Dally, et al., “Architecture of a Message-Driven Processor,” International Conference on Computer Architecture, Jun. 1987, pp. 189-196.
Dennison, Lee and Dally, “High-Performance Bidirectional Signalling in VLSI,” Massachusetts Institute of Technology, Oct. 12, 1992, 20 pages.
Dally, et al., “Architecture and Implementation of the Reliable Router,” Mass. Institute of Technology, Proceedings of Hot Interconnects II, Stanford CA, Aug. 1994, 12 pages.
Dally, et al. “The Reliable Router: A Reliable and High-Performance Communication Substrate for Parallel Computers,” Proceedings of the First International Parallel Computer Routing and Communication Workshop, Seattle WA, May 1994, 15 pages.
Dennison, et al., “Low-Latency Plesiochronous Data Retiming,” Mass. Institute of Technology, Proceedings of the 1995 Advanced Research in VLSI Conference, Chapel Hill NC, Mar. 1995, 12 pages.
Whay S. Lee, “Mechanism for Efficient, Protected Messaging,” Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, Jan. 20, 1999, 147 pages.
Dennison, “Reliable Interconnect Networks for Parallel Computers,” Mass. Institute of Technology, Dept. of Electrical Engineering and Computer Science, Apr. 18, 1991, 79 pages.
Thucydides Xanthopoulos, “Fault Tolerant Adaptive Routing in Multicomputer Networks,” Dept. of Electrical Engineering and Computer Science, Mass. Institute of Technology, Jan. 20, 1995, 152 pages.
Dennison, “The Reliable Router: An Architecture for Fault Tolerant Interconnect,” Dept. of Electrical Engineering and Computer Science, Mass Institute of Technology, May 24, 1996, 145 pages.
“Introduction To Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes,” F. Thomson Leighton, Morgan Kaufmann Publishers, 1992, pp. 1-831.
Christopher J. Glass and Lionel Ni, “Fault-Tolerant Wormhole Routing in Meshes,” Technical Report, MSU-CPS-ACS-72, Oct. 30, 1992 (revised May 25, 1993), 28 pages.
Stefan Savage and John Wilkes, “AFRAID-A Frequently Redundant Array of Independent Disks,” Proceedings of the 1996 USENIX Technical Conference, pp. 27-39, San Diego, CA, Jan. 1996, 13 pages.
Steve Ward, et al., “A Modular, Scalable Commu
Kowert Robert C.
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Najjar Saleh
Won Michael Y.
LandOfFree
Scalable routing scheme for a multi-path interconnection fabric does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scalable routing scheme for a multi-path interconnection fabric, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scalable routing scheme for a multi-path interconnection fabric will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3603960