Multiplex communications – Wide area network – Packet switching
Patent
1997-11-17
1999-10-19
Pam, Daniel H.
Multiplex communications
Wide area network
Packet switching
370351, 370389, 39580013, G06F 1300, H04L 1254
Patent
active
059702320
ABSTRACT:
A multiprocessor computer system includes processing element nodes interconnected by physical communication links in a n-dimensional topology, which includes at least two global partitions. Routers route messages between processing element nodes and include ports for receiving and sending messages, and lookup tables having a local router table having directions for routing between processor element nodes within a global partition, and a global router table having directions for routing between processor element nodes located in different global partitions. The directions from the local table are selected for routing from the next router along a given route if the current processing element node is in a destination global partition or if the current processing element node is one plus or minus hop from reaching the destination global partition and the route is exiting on a port that routes to the destination global partition, else the directions from the global router table are selected for routing from the next router.
REFERENCES:
patent: Re28577 (1975-10-01), Schmidt
patent: 4330858 (1982-05-01), Choquet
patent: 4630259 (1986-12-01), Larson et al.
patent: 4771391 (1988-09-01), Blasbalg
patent: 4811214 (1989-03-01), Nosenchuck et al.
patent: 4868818 (1989-09-01), Madan et al.
patent: 4933933 (1990-06-01), Dally et al.
patent: 4980822 (1990-12-01), Brantley et al.
patent: 5008882 (1991-04-01), Peterson et al.
patent: 5031211 (1991-07-01), Nagai et al.
patent: 5036459 (1991-07-01), Den Haan et al.
patent: 5081623 (1992-01-01), Ainscow
patent: 5105424 (1992-04-01), Flaig et al.
patent: 5117350 (1992-05-01), Parrish et al.
patent: 5134690 (1992-07-01), Samatham
patent: 5157692 (1992-10-01), Horie et al.
patent: 5161156 (1992-11-01), Baum et al.
patent: 5170482 (1992-12-01), Shu et al.
patent: 5175733 (1992-12-01), Nugent
patent: 5195100 (1993-03-01), Katz et al.
patent: 5201044 (1993-04-01), Frey, Jr. et al.
patent: 5210705 (1993-05-01), Chauvel et al.
patent: 5218601 (1993-06-01), Chujo et al.
patent: 5218676 (1993-06-01), Ben-ayed et al.
patent: 5233618 (1993-08-01), Glider et al.
patent: 5239545 (1993-08-01), Buchholz
patent: 5274799 (1993-12-01), Brant et al.
patent: 5276899 (1994-01-01), Neches
patent: 5280474 (1994-01-01), Nicokolls et al.
patent: 5297137 (1994-03-01), Ofek et al.
patent: 5303244 (1994-04-01), Watson
patent: 5313628 (1994-05-01), Mendelsohn et al.
patent: 5313645 (1994-05-01), Rolfe
patent: 5331631 (1994-07-01), Teraslinna
patent: 5333279 (1994-07-01), Dunning
patent: 5341504 (1994-08-01), Mori et al.
patent: 5345565 (1994-09-01), Jibbe et al.
patent: 5347450 (1994-09-01), Nugent
patent: 5353283 (1994-10-01), Tsuchiya
patent: 5365228 (1994-11-01), Childs et al.
patent: 5383191 (1995-01-01), Hobgood et al.
patent: 5390164 (1995-02-01), Kremer
patent: 5402428 (1995-03-01), Kakuta et al.
patent: 5434995 (1995-07-01), Oberlin et al.
patent: 5440547 (1995-08-01), Easki et al.
patent: 5444701 (1995-08-01), Cypher et al.
patent: 5452444 (1995-09-01), Solomon et al.
patent: 5453978 (1995-09-01), Sethu et al.
patent: 5475858 (1995-12-01), Gupta et al.
patent: 5499337 (1996-03-01), Gordon
patent: 5513192 (1996-04-01), Janku et al.
patent: 5517497 (1996-05-01), LeBoudec et al.
patent: 5519844 (1996-05-01), Stallmo
patent: 5522031 (1996-05-01), Ellis et al.
patent: 5530948 (1996-06-01), Islam
patent: 5533198 (1996-07-01), Thorson
patent: 5546549 (1996-08-01), Barrett et al.
patent: 5546596 (1996-08-01), Geist
patent: 5548639 (1996-08-01), Ogura et al.
patent: 5550589 (1996-08-01), Shiojiri et al.
patent: 5555542 (1996-09-01), Ogura et al.
patent: 5590284 (1996-12-01), Crosetto
patent: 5596742 (1997-01-01), Agamal et al.
patent: 5659796 (1997-08-01), Thorson et al.
patent: 5721819 (1998-02-01), Galles et al.
"Deadlock-Free Routing Schemes on Multistage Interconnection Networks", IBM Technical Disclosure Bulletin, 35, 232-233, (Dec., 1992).
Adve, V.S., et al., "Performance Analysis of Mesh Interconnection Networks with Deterministic Routing", Transactions on Parallel and Distributed Systems, 225-246, (Mar. 1994).
Bolding, K., "Non-Uniformities Introduced by Virtual Channel Deadlock Prevention", Technical Report UW CSE-92-07-07, University of Washington, Seattle, WA, (Jul. 12, 1992),
Bolla, F.R., "A Neural Strategy for Optimal Multiplexing of Circuit and Packet-Switched Traffic", Department of Communications, Computer and Systems Science (DIST), University of Genova, 1324-1330.
Boura, Y.M., et al., "Efficient Fully Adaptive Wormhole Routing in n-dimenstional Meshes", IEEE, 589-596, (1994).
Bundy, A., et al., "Turning Eureka Stepsinto Calculations in Automatic Program", UK IT, (IEE Conf. Pub. 316), pp. 221-226, (1991).
Carlile, B.R., "Algorithms and Design: The CRAP APP Shared-Memory System", Comcon Spring '93, pp. 312-320, Feb. 22, 1993, San Francisco, CA.
Chien, A.A., et al., "Planar-Adaptive Routing: Low-Cost Adaptive Networks for Multiprocessors", Pro. 19th International. Symposium on Computer Architecture, 268-277, (May 1992).
Dally, W., "Performance Analysis of k-ary n-cube Interconnection Networks", IEEE Transactions on Computers, vol. 39, No. 6, 775-785, (Jun. 1990).
Dally, W., et al., "Deadlock-Free Message Routing in Multiprocessor Interconnection Networks", IEEE Transactions on Computers, C-36, 547-553, (May, 1987).
Dally, W.J., "Virtual Channel Flow Control", Pro. 17th International Symposium on Computer Architecture, pp. 60-68, May 1990.
Dally, W.J., et al., "Deadlock-Free Adaptive Routing in Multicomputer Networks Using Virtual Channels", I.E.E.E. Transactions on Parallel and Distributed Systems, vol. 4, No. 4, 466-475, (Apr. 1993).
Duato, J., "A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks", I.E.E.E. Transactions on Parallel and Distributed Systems, vol. 4, No. 12, at 1320-1331, Dec. 1993.
Gallager, R., "Scale Factors for Distributed Routing Algorithm", NTC '77 Conference Record, 2, at 2-1 through 2-5.
Glass, C.J., et al., "The Turn Model for Adaptive Routing", Pro. 19th Interanational Symposium on Computer architecture, 278-287, (May 1992).
Gravano, L., et al., "Adaptive Deadlock- and Livelock-Free Routing with all Minimal Paths in Torus Networks", IEEE Transactions on Parellel and Distributed Systems, vol. 5, No. 12, 1233-1251, (Dec. 1994).
Gupta, R., et al., "High speed Synchronization of Processors Using Fuzzy Barriers", International Journakl of Parallel Programming 19 (1990) Feb., No. 1, New York, US pp. 53-73.
Ishihata, H., et al., "Architecture of Highly Parallel AP1000 Computer", Scripta Technica, Inc., Systems and Computers in Japan 24, No. 7,, pp. 69-76, (1993).
Jesshope, C.R., et al., "High Performance Communications in Processor Networks", Proc. 16th International Symposium on Computer Architecture, at 150-157, (May 1989).
Kirkpatrick, S., et al., "Optimization by Simulated Annealing", Science, May 13, 1993, vol. 220, No. 4598, 671-680.
Linder, D., et al., "An Adaptive and Fault Tolerant Wormhole Routing Strategy for k-ary n-cues", IEEE Transactions on Computers, 40,, 2-12, (Jan., 1991).
Lui, Z., et al., "Grouping Virtual Channels for Deadlock-Free Adaptive Wormhole Routing", PARLE '93 Parallel Parallel Architectures and Languages Europe, 5th International PARLE Conference, Munich, Germany.backslash.. 255-265, (Jun. 14-17, 1993).
Nuth, P., et al., "The J-Machine Network", IEEE, 420-423, (1992).
O'Keefe, M.T., et al., "Static Barrier MIMD: Architecture and Performance Analysis", Journal of Parallel and Distrubuted Computing No. 2,, pp. 126-132, (Mar. 25, 1995).
Shumay, M., "Deadlock-Free Packet Networks", Transputer Research and Applications 2, NATUG-2 Proceedings of the Second Conference of the North American Transputer Users Group, 140-177, (Oct. 18-19, 1989).
Snyder, L., "Introduction to the Configurable, Highly Parallel Computer", IEEE, 47-56, (Jan. 1982).
Talia, D., "Message-Routing Systems for Transputer-Based Multicomputer", IEEE Micro, No. 3, pp. 62-72, (Jun. 13, 1993).
Wang, W., et al., "Trunk Congestion Control in Heterogeneous Circuit Switched Networks", IEEE, pp. 1156-1161.
Wu, M., et al., "Do and Forall: Temporal
Galles Michael B.
Passint Randal S.
Thorson Greg
Cray Research Inc.
Pam Daniel H.
LandOfFree
Router table lookup mechanism does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Router table lookup mechanism, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Router table lookup mechanism will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2067103