System and method for providing forward progress and avoiding starvation and livelock in a multiprocessor computer system

An input/output (I/O) bridge for use in a distributed shared memory computer system comprising a plurality of interconnected processors and one or more shared memories that are coupled to the processors, the I/O bridge configured to provide intercommunication between one or more I/O devices and the plurality of processors or shared memories, the I/O bridge comprising:

• at least one coherent buffer configured to store information requested by a first I/O device coupled to the I/O bridge:
• at least one non-coherent buffer coupled to the coherent buffer and to the one or more I/O devices by an I/O bus having a bus cycle specifying a predetermined number of bits per I/O bus cycle;
• and
• a controller coupled to the coherent buffer and the non-coherent buffer, the controller configured to:
• store at least a portion of the information stored in the coherent buffer in the non-coherent buffer in response to receiving a system message originating from other than the first I/O device requesting the information stored in the coherent buffer,
• invalidate the information within the coherent buffer, and
• supply to the first I/O device at least some of the information copied into the non-coherent buffer,
• wherein the information supplied to the first I/O device from the non-coherent buffer is the predetermined number of bits of one bus cycle.

A method for avoiding livelock among two or more input/output (I/O) devices of a computer system comprising a plurality of interconnected processors, one or more shared memories coupled to the processors, and at least one I/O bridge in communicating relationship with the two or more I/O devices, the processors and the one or more shared memories, the method comprising the steps of:

• providing at least one coherent buffer and at least one non-coherent buffer at the I/O bridge, the non-coherent buffer coupled to the at least one coherent buffer and to at least one of the I/O devices;
• receiving a request for information from a first I/O device coupled to the I/O bridge;
• storing the device requested information in the coherent buffer of the I/O bridge;
• receiving a system message at the I/O bridge requesting the information stored in the coherent buffer, the system message originating from other than the first I/O device;
• copying at least a portion of the stored information to the non-coherent buffer;
• invalidating the stored information within the coherent buffer;
• supplying to the first I/O device at least some of the stored information copied into the non-coherent buffer;
• organizing information stored in the one or more shared memories of the computer system into respective cache lines;
• and
• providing one or more cache coherency directories, the one or more cache coherency directories configured to store an ownership status for each cache line,
• wherein
• the system message requesting information originates from one or more of the directories and the acknowledgement is sent to one or more of the directories.

A method for avoiding livelock among two or more input/output (I/O) devices of a computer system comprising a plurality of interconnected processors, one or more shared memories coupled to the processors, and at least one I/O bridge in communicating relationship with the two or more I/O devices, the processors and the one or more shared memories, the method comprising the steps of:

• providing at least one coherent buffer and at least one non-coherent buffer at the I/O bridge, the non-coherent buffer coupled to the at least one coherent buffer and to at least one of the I/O devices;
• receiving a request for information from a first I/O device coupled to the I/O bridge;
• storing the device requested information in the coherent buffer of the I/O bridge;
• receiving a system message at the I/O bridge requesting the information stored in the coherent buffer, the system message originating from other than the first I/O device;
• copying at least a portion of the stored information to the non-coherent buffer;
• invalidating the stored information within the coherent buffer;
• supplying to the first I/O device at least some of the stored information copied into the non-coherent buffer;
• issuing an initial miss message in response to the system message requesting the information stored in the coherent buffer;
• and
• searching the coherent buffer for the requested information following the issuance of the initial miss message.