Multiplex communications – Wide area network – Packet switching
Patent
1995-04-13
1997-08-19
Lee, Thomas C.
Multiplex communications
Wide area network
Packet switching
370409, G06F 1300, G06F 1312
Patent
active
056597967
ABSTRACT:
A method optimizes routing in a multiprocessor computer system by defining two types of virtual channels having virtual channel buffers for storing messages communicated between processing element nodes in the multiprocessor computer system. A dateline is associated to each type of virtual channel, and messages are restrained from crossing a dateline on its associated type of virtual channel to avoid deadlock. A cost function is defined which is correlated to imbalances in the utilization of the two types of virtual channels. The unrestrained messages are allocated between the two types of virtual channels to minimize the cost function by defining an initial virtual channel allocation, randomly modifying the virtual channel allocation, and accepting the random modification if the modification decreases the cost function, else accepting the modification based on a probability that slowly decreases during the allocating step.
REFERENCES:
patent: Re28577 (1975-10-01), Schmidt
patent: 4771391 (1988-09-01), Blasbalg
patent: 4933933 (1990-06-01), Dally 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: 5218676 (1993-06-01), Ben-Ayed et al.
patent: 5239545 (1993-08-01), Buchholz
patent: 5313645 (1994-05-01), Rolfe
patent: 5341504 (1994-08-01), Mori et al.
patent: 5546549 (1996-08-01), Barrett et al.
patent: 5550589 (1996-08-01), Shiojiri et al.
"A Neural Strategy For Optimal Multiplexing of Circuit-And-Packet-Switched Traffic", Bolla et al, IEEE, pp. 1324-1330. Feb. 1992.
Robert Gallager, "Scale Factors for Distributed Routing Algorithms", NTC '77 Conference Record, 2 (1978).
C.S. Yang et al., "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).
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 2-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.
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.
Dally W.J., "Virtual Channel Flow Control," Proc. 17th International Symposium on Computer Architecture, pp. 60-68, May 1990.
Kirkpatrick, S., C.D. Gellatt, Jr. and M.P. Vecchi, "Optimization by Simulated Annealing," Science, pp. 671-670, vol. 220, No. 4598, May 1983.
D. Talia, "Message-Routing Systems for Transputer-Based Multicomputer," IEEE Micro, No. 3, pp. 62-72, (Jun. 13, 1993).
K. Bolding; "Non-Uniformities Introducted by Virtual Channel Deadlock Prevention", Technical Report UW CSE-92-07-07, University of Washington, Seattle, WA, (Jul. 12, 1992).
Scott Steven L.
Thorson Gregory M.
Cray Research Inc.
Krick Rehana Perreen
Lee Thomas C.
LandOfFree
System for randomly modifying virtual channel allocation and acc does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for randomly modifying virtual channel allocation and acc, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for randomly modifying virtual channel allocation and acc will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1113693