A method for maintaining cache coherence in a multiprocessor computer system

Claim 1

A method for maintaining cache coherence in a multiprocessor computer system (10) having a potential for duplication of data in a plurality of storage locations identifiable as coherence blocks, said multiprocessor computer system (10) employing doubly-­linked lists for identifying a previous master of said data and a next master of said data, said method comprising the steps of: passing (42) the current address (44) of a current master (20) from the current master (20) to the previous master (28), wherein the current address (44) is the location through which the current master (20) will respond; passing (42) the current address (44) of the current master (20) from the current master (20) to the next master (28); passing (42) the current index (46) of the current master (20) from the current master (20) to the previous master (28), wherein the current index (46) is a collection of information needed by the current master (20) to use the coherence block; and passing the current index (46) of the current master (20) from the current master (20) to the next master (28).

Claim 2

A method for maintaining cache coherence in a multiprocessor computer system (10) having a potential for duplication of data in a plurality of storage locations identifiable as coherence blocks, said multiprocessor computer system (10) employing doubly-­linked lists for identifying a previous master of said data and a next master of said data, said method comprising the steps of: passing (42) the current address (44) of a current master (20) from the current master (20) to the previous master (28), wherein the current address (44) is the location through which the current master (20) will respond; passing (42) the current address (44) of the current master (20) from the current master (20) to the next master (28); passing (42) the current index (46) of the current master (20) from the current master (20) to the previous master (28), wherein the current index (46) is a collection of information needed by the current master (20) to use the coherence block; and passing the current index (46) of the current master (20) from the current master (20) to the next master (28).

Claim 6

A method for maintaining cache coherence in a multiprocessor computer system (10) having a potential for duplication of data in a plurality of storage locations identifiable as coherence blocks, said multiprocessor computer system (10) employing doubly-linked lists for identifying a previous master (20) of said data and a next master (18) of said data, said method comprising the steps of: a) issuing from a first master (18) a first transaction (58) to a second master (28) requesting sharable data in a coherence block from said second master, said second master being a repository of known valid data, said first transaction including at least an address of the requested coherence block, a first master address for said first master and a first index useful by said second master for indexing into addresses of the first master; b) storing (60) a second master address of said second master and a second index of said second master in a previousmaster storage location (68) of said first master, thereby to indicate the previous link of said first master; thereafter c) issuing from said second master to said first master a second transaction (66) containing at least a portion of the sharable data and at least a third master address and a third index of a third master (20) from a nextmaster storage location (31) of said second master: thereafter d) storing said first master address and said first index in said nextmaster storage location (34) of said second master, thereby to indicate the next link (64) of said second master; e) storing said third master address and said third index in a nextmaster storage location (64) of said first master, thereby to indicate the next link (49) of said first master; thereafter f) issuing from said first master to said third master a third transaction (66) containing said first master address and said first index; g) storing said first master address and said first index in a previousmaster storage location (52) of said third master; and h) updating previous master addresses and indexes and next master addresses and indexes in selected linked masters to correct pointers (74).

Claim 7

A method for maintaining cache coherence in a multiprocessor computer system (10) having a potential for duplication of data in a plurality of storage locations identifiable as coherence blocks, said multiprocessor computer system (10) employing doubly-linked lists for identifying a previous master (20) of said data and a next master (18) of said data, said method comprising the steps of: a) issuing from a first master (18) a first transaction (58) to a second master (28) requesting sharable data in a coherence block from said second master, said second master being a repository of known valid data, said first transaction including at least an address of the requested coherence block, a first master address for said first master and a first index useful by said second master for indexing into addresses of the first master; b) storing (60) a second master address of said second master and a second index of said second master in a previousmaster storage location (68) of said first master, thereby to indicate the previous link of said first master; thereafter c) issuing from said second master to said first master a second transaction (66) containing at least a portion of the sharable data and at least a third master address and a third index of a third master (20) from a nextmaster storage location (31) of said second master: thereafter d) storing said first master address and said first index in said nextmaster storage location (34) of said second master, thereby to indicate the next link (64) of said second master; e) storing said third master address and said third index in a nextmaster storage location (64) of said first master, thereby to indicate the next link (49) of said first master; thereafter f) issuing from said first master to said third master a third transaction (66) containing said first master address and said first index; g) storing said first master address and said first index in a previousmaster storage location (52) of said third master; and h) updating previous master addresses and indexes and next master addresses and indexes in selected linked masters to correct pointers (74).

Claim 11

A method for maintaining cache coherence in a multiprocessor computer system (10) having a potential for duplication of data in a plurality of storage locations identifiable as coherence blocks, said multiprocessor computer system (10) employing doubly-linked lists for identifying a previous master (18) of said data and a next master (18) of said data, wherein a second master address and a second index are stored in a nextmaster storage location (34) of a second master (28), said method comprising the steps of: a) issuing from a first master (18) a first transaction (42) to said second master (28) requesting sharable data in a coherence block from said second master, said second master being a repository of known valid data, said first transaction including at least an address of the requested coherence block, a first master address for said first master and a first index useful by said second master for indexing into addresses of the first master; b) storing (60) said second master address of said second master and said second index of said second master in a previousmaster storage location (68) of said first master, thereby to indicate the previous link of said first master; thereafter c) issuing from said second master to said first master a second transaction (48) containing at least a portion of the sharable data and at least said second master address and said second index from the nextmaster storage (34) location of said second master; thereafter d) storing said first master address and said first index in said nextmaster storage location of said second master, thereby to indicate the next link of said second master; e) storing said second master address and said second index in a nextmaster storage location (62) of said first master, thereby to indicate the next link of said first master; and thereafter f) updating previous master addresses and indexes and next master addresses and indexes in selected linked masters to correct pointers.

Claim 12

A method for maintaining cache coherence in a multiprocessor computer system (10) having a potential for duplication of data in a plurality of storage locations identifiable as coherence blocks, said multiprocessor computer system (10) employing doubly-linked lists for identifying a previous master (18) of said data and a next master (18) of said data, wherein a second master address and a second index are stored in a nextmaster storage location (34) of a second master (28), said method comprising the steps of: a) issuing from a first master (18) a first transaction (42) to said second master (28) requesting sharable data in a coherence block from said second master, said second master being a repository of known valid data, said first transaction including at least an address of the requested coherence block, a first master address for said first master and a first index useful by said second master for indexing into addresses of the first master; b) storing (60) said second master address of said second master and said second index of said second master in a previousmaster storage location (68) of said first master, thereby to indicate the previous link of said first master; thereafter c) issuing from said second master to said first master a second transaction (48) containing at least a portion of the sharable data and at least said second master address and said second index from the nextmaster storage (34) location of said second master; thereafter d) storing said first master address and said first index in said nextmaster storage location of said second master, thereby to indicate the next link of said second master; e) storing said second master address and said second index in a nextmaster storage location (62) of said first master, thereby to indicate the next link of said first master; and thereafter f) updating previous master addresses and indexes and next master addresses and indexes in selected linked masters to correct pointers.

Claim 14

A method for maintaining cache coherence in a multiprocessor computer system (10) having a potential for duplication of data in a plurality of storage locations identifiable as coherence blocks, said multiprocessor computer system employing doubly-linked lists for identifying a previous master of said data and a next master of said data, said method comprising the steps of: a) issuing from a first master (18) a first transaction (88) to a second master (28) informing of a purge of sharable data in a coherence block in said first master, said first transaction including a third master address for a third master (20) and a third index useful by said third master for indexing into addresses of the third master; thereafter b) storing said third master address and third index in a nextmaster storage location (34) of said second master, thereby to indicate a next link; c) issuing from said second master to said third master a second transaction (90), said second transaction containing a second master address and a second index of said second master; thereafter d) issuing from said third master to said first master a third transaction (92) acknowledging completion of said first transaction; thereafter e) storing said second master address and said second index in a previousmaster storage location (52) of said third master, thereby to indicate a previous link; and f) marking said coherence block (76) of said first master as invalid.

Claim 15

A method for maintaining cache coherence in a multiprocessor computer system (10) having a potential for duplication of data in a plurality of storage locations identifiable as coherence blocks, said multiprocessor computer system employing doubly-linked lists for identifying a previous master of said data and a next master of said data, said method comprising the steps of: a) issuing from a first master (18) a first transaction (88) to a second master (28) informing of a purge of sharable data in a coherence block in said first master, said first transaction including a third master address for a third master (20) and a third index useful by said third master for indexing into addresses of the third master; thereafter b) storing said third master address and third index in a nextmaster storage location (34) of said second master, thereby to indicate a next link; c) issuing from said second master to said third master a second transaction (90), said second transaction containing a second master address and a second index of said second master; thereafter d) issuing from said third master to said first master a third transaction (92) acknowledging completion of said first transaction; thereafter e) storing said second master address and said second index in a previousmaster storage location (52) of said third master, thereby to indicate a previous link; and f) marking said coherence block (76) of said first master as invalid.