Adaptive routing mechanism for torus interconnection network

Communications: electrical – Land vehicle alarms or indicators – Internal alarm or indicator responsive to a condition of the...

Patent

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

39520001, 34082502, 34082503, 340826, 340827, G06F 1516

Patent

active

057014167

ABSTRACT:
A routing mechanism includes two acyclic non-adaptive virtual channels having two types of virtual channel buffers to store packets along deterministic virtual paths between nodes in an n-dimensional networked system, and an adaptive virtual channel having a third type of virtual channel buffer to store the packets along non-deterministic virtual paths between the nodes. The packets are routed between the nodes along either selected portions of the deterministic virtual paths or selected portions of the non-deterministic virtual paths based on routing information such that a packet is never routed on a selected portion of one of the non-deterministic virtual paths unless the third type virtual channel buffer associated with the selected portion of the one non-deterministic virtual path has sufficient space available to store the entire packet.

REFERENCES:
patent: Re28577 (1975-10-01), Schmidt
patent: 4771391 (1988-09-01), Blasbalg
patent: 4868818 (1989-09-01), Madan et al.
patent: 4933933 (1990-06-01), Dally et al.
patent: 5008882 (1991-04-01), Peterson et al.
patent: 5031211 (1991-07-01), Nagai et al.
patent: 5105424 (1992-04-01), Flaig et al.
patent: 5157692 (1992-10-01), Horie et al.
patent: 5170482 (1992-12-01), Shu et al.
patent: 5175733 (1992-12-01), Nugent
patent: 5218601 (1993-06-01), Chujo et al.
patent: 5218676 (1993-06-01), Ben-Ayed et al.
patent: 5239545 (1993-08-01), Buchholz
patent: 5280474 (1994-01-01), Nickolls et al.
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: 5347450 (1994-09-01), Nugent
patent: 5353283 (1994-10-01), Tsuchiya
patent: 5440547 (1995-08-01), Easki et al.
patent: 5517497 (1996-05-01), LeBoudec et al.
patent: 5546549 (1996-08-01), Barrett et al.
patent: 5548639 (1996-08-01), Ogura et al.
patent: 5550589 (1996-08-01), Shiojiri et al.
patent: 5555542 (1996-09-01), Ogura et al.
R. Bolla, F., et al., "A Neural Strategy for Optimal Multiplexing of Circuit and Packet-Switched Traffic," Department of Communications, Computer and Systems Science (DIST), University of Genoa, pp. 1324-1330, 1992.
Y. Boura et al., "Efficient Fully Adaptive Wormhole Routing in n-dimensional Meshes", IEEE, pp. 589-596. (1994).
L. Gravano et al., "Adaptive Deadlock-and Livelock-Free Routing with all Minimal Paths in Torus Networks", IEEE Transactions on Parallel and Distributed Systems, 5, pp. 1233-1251, (Dec. 1994).
Z. Liu et al., "Grouping Virtual Channels for Deadlock-Free Adaptive Wormhole Routing", Parle '93 Parallel Architectures and Languages Europe, 5th International Parle Conference, Munich, Germany, pp. 255-265, (Jun. 14-17, 1993).
M. Shumway, "Deadlock-Free Packet Networks", Transputer Research and Applications 2, NATUG-2 Proceedings of the Second Conference of the North American Transputer Users Group, pp. 140-177, (Oct. 18-19, 1989).
"Deadlock-Free Routing Schemes on Multistage Interconnection Networks", IBM Technical Disclosure Bulletin, 35, 232-233 (Dec. 1992).
Robert Gallager, "Scale Factors for Distributed Routing Algorithms", NTC '77 Conference Record, 2 (1978).
Peter Nuth et al., "The J-Machine Network", IEEE 420-423 (1992).
C.S. Yang "Performance Evaluation of Multicast Wormhole Routing in 2D-Torus Multicomputers", IEEE, 173-178 (1992).
J. Yantchev et al., "Adaptive, low latency, deadlock-free packet routing for networks of processors", IEE Proceedings, 136, 178-186 (May 1989).
William Dally et al, "Deadlock-Free Message Routing in Multiprocessor Interconnection Networks", IEEE Transactions on Computers, C-36, 547-553 (May 1987).
William Dally, "Performance Analysis of k-ary n-cube Interconnection Networks", IEEE Transactions on Computers, 39, 775-785 (Jun. 1990).
William Dally, "Virtual-Channel Flow Control", IEEE, 60-68 (1990).
C.R. Jesshope, P.R. Miller and J.P. Yantchev, High Performance Communications in Processor Networks, proc. 16th International Symposium on Computer ARchitecture at 150-157, May 1989.
D.H. Linder and J.C. Harden, An Adaptive and Fault Tolerant Wormhole Routing Strategy for k-ary n-cubes, I.E.E.E. Trans. on Computers, at Feb. 12, Jan. 1991.
W.J. Dally and H. Aoki, Deadlock-Free Adaptive Routing in Multicomputer Networks Using Virtual Channels, I.E.E.E. Transactions on Parallel and Distributed Systems, vol. 4, No. 4, at 466-475, Apr. 1993.
C.J. Glass and L.M. Ni, The Turn Model for Adaptive Routing, Proc. 19th International Symposium on Computer architecture, at 278-287, May 1992.
A.A. Chien and J.H. Kim, Planar-Adaptive Routing: Low Cost Adaptive Networks for Multiprocessors, proc. 19th International. Symposium on Computer Architecture at 268-277, May 1992.
J. Duato, 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.
Adve, V.S. and M.K. Vernon, "Performance Analysis of Mesh Interconnection Networks with Deterministic Routing," Transactions on Parallel and Distributed Systems, pp. 225-246, Mar. 1994.
D. Talia; "Message-Routing Systems for Transputer-Based Multicomputers"; IEEE Micro; No. 3, pp. 62-72; (Jun. 13, 1993).

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Adaptive routing mechanism for torus interconnection network does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Adaptive routing mechanism for torus interconnection network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive routing mechanism for torus interconnection network will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-1807342

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.