System and method for avoiding deadlock

Details System and method for avoiding deadlock System and method for avoiding deadlock

2007-04-10

2007-04-10

Fleming, Fritz (Department: 2181)

Electrical computers and digital data processing systems: input/

Input/output data processing

Input/output data buffering

C710S057000

Reexamination Certificate

active

10337833

ABSTRACT:
A system and method avoids deadlock, such as circular routing deadlock, in a computer system by providing a virtual buffer at main memory. The computer system has an interconnection network that couples a plurality of processors having access to main memory. The interconnection network includes one or more routing agents each having at least one buffer for storing packets that are to be forwarded. When the routing agent's buffer becomes full, thereby preventing it from accepting any additional packets, the routing agent transfers at least one packet into the virtual buffer. By transferring a packet out of the buffer, the routing agent frees up space allowing it to accept a new packet. If the newly accepted packet also results in the buffer becoming full, another packet is transferred into the virtual buffer. This process is repeated until the deadlock condition is resolved. Packets are then retrieved from the virtual buffer.

REFERENCES:
patent: 5237661 (1993-08-01), Kawamura et al.
patent: 5652885 (1997-07-01), Reed et al.
patent: 6185438 (2001-02-01), Fox
patent: 6279046 (2001-08-01), Armstrong et al.
patent: 6317427 (2001-11-01), Augusta et al.
patent: 6601083 (2003-07-01), Reznak
patent: 2002/0099918 (2002-07-01), Avner et al.
patent: 2004/0015686 (2004-01-01), Conner et al.
patent: 2004/0036159 (2004-02-01), Bruno
William Stallings, Operating Systems Internals and Design Principles, 2001, fourth edition, pp. 282-283.
Patterson & Hennessy, Computer Organization & Design, 2nd edition, pp. 540-549.
Microsoft Computer Dictionary 5th edition, 2002, Microsoft Press, p. 458.
Ozveren, Cuneyt et al. ACM SIGCOMM, London, England, “Reliable and Efficient Hop-by-Hop Flow Control,” 1994, pp. 1-12.
Dally, William J. IEEE “Virtual-Channel Flow Control,” Artificial Intelligence Laboratory and Laboratory for Computer Science, Massachusetts Institute of Technology, 1990 pp. 60-68.
Natvig, Lasse. “High-level Architectural Simulation of the Torus Routing Chip,” Department of Computer and Information Systems, Norwegian University of Science and Technology, Mar. 31, 1997.
Dally, William J. et al. “Deadlock-Free Message Routing in Mulitprocessor Interconnection Networks” 5231:TR:86 California Institute of Technology Jun. 30, 1986.
Cypher, Robert et al. “Requirments for Deadlock-Free, Adaptive Packet Routing” 1992.
Berman, Pablo E., et al. “Adaptive Deadlock- and Livelock-Free Routing With All Minimal Paths in Torus Networks,” 1992.
Leighton, Tom et al. “Method for Message Routing in Parallel Machines,” Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, 1992.
Pritchard, David J. “Load Balanced Deadlock-Free Deterministic Routing of Arbitrary Networks,” Department of Computer Science, University of Liverpool. 1992.

Affiliated with

Also associated with

Rating

System and method for avoiding deadlock 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 and method for avoiding deadlock, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for avoiding deadlock will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3724439