Method for maintaining cache coherence in a multiprocessor computer system

Claim 1

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

Claim 2

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

Claim 6

A method for maintaining cache coherence in a multiprocessor computer system 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 to a second master a first transaction requesting sharable data in a coherence block of said second master, said second master being a repository of known valid data, said first transaction including at least an address of a requested coherence block, a first master address for said first master and a first index which identifies a storage location within the first master; b) storing a second master address of said second master and a second index of said second master in a previous master storage location of said first master, thereby to indicate a previous link of said first master; thereafter c) issuing from said second master to said first master a second transaction containing at least a portion of the sharable data and at least a third master address and a third index of a third master from a next master storage location of said second mater; thereafter d) storing said first master address and said first index in said next master storage location of said second master, thereby to indicate a next link of said second master; e) storing said third master address and said third index in a next master storage location of said first master, thereby to indicate a next link of said first master; thereafter f) issuing from said first master to said third master a third transaction containing said first master address and said first index; g) storing said first master address and said first index in a previous master storage location of said third master thereby to indicate a previous link of said third master; and h) updating previous master addresses and indexes and next master addresses and indexes in selected linked masters.

Claim 7

A method for maintaining cache coherence in a multiprocessor computer system 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 to a second master a first transaction requesting sharable data in a coherence block of said second master, said second master being a repository of known valid data, said first transaction including at least an address of a requested coherence block, a first master address for said first master and a first index which identifies a storage location within the first master; b) storing a second master address of said second master and a second index of said second master in a previous master storage location of said first master, thereby to indicate a previous link of said first master; thereafter c) issuing from said second master to said first master a second transaction containing at least a portion of the sharable data and at least a third master address and a third index of a third master from a next master storage location of said second mater; thereafter d) storing said first master address and said first index in said next master storage location of said second master, thereby to indicate a next link of said second master; e) storing said third master address and said third index in a next master storage location of said first master, thereby to indicate a next link of said first master; thereafter f) issuing from said first master to said third master a third transaction containing said first master address and said first index; g) storing said first master address and said first index in a previous master storage location of said third master thereby to indicate a previous link of said third master; and h) updating previous master addresses and indexes and next master addresses and indexes in selected linked masters.

Claim 11

A method for maintaining cache coherence in a multiprocessor computer system 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, wherein a second master address and a second index are stored in a next master storage location of a second master, said method comprising the steps of: a) issuing from a first master to said second master a first transaction requesting sharable data in a coherence block of said second master, said second master being a repository of known valid data, said first transaction including at least an address of a requested coherence block, a first master address for said first master and a first index which identifies a data storage location within the first master; b) storing said second master address of said second master and said second index of said second master in a previous master storage location of said first master, thereby to indicate a previous link of said first master; thereafter c) issuing from said second master to said first master a second transaction containing at least a portion of the sharable data and at least said second master address and said second index from the next master storage location of said second master; thereafter d) storing said first master address and said first index in said next master storage location of said second master, thereby to indicate a next link of said second master; e) storing said second master address and said second index in a next master storage location of said first master, thereby to indicate a 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 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, wherein a second master address and a second index are stored in a next master storage location of a second master, said method comprising the steps of: a) issuing from a first master to said second master a first transaction requesting sharable data in a coherence block of said second master, said second master being a repository of known valid data, said first transaction including at least an address of a requested coherence block, a first master address for said first master and a first index which identifies a data storage location within the first master; b) storing said second master address of said second master and said second index of said second master in a previous master storage location of said first master, thereby to indicate a previous link of said first master; thereafter c) issuing from said second master to said first master a second transaction containing at least a portion of the sharable data and at least said second master address and said second index from the next master storage location of said second master; thereafter d) storing said first master address and said first index in said next master storage location of said second master, thereby to indicate a next link of said second master; e) storing said second master address and said second index in a next master storage location of said first master, thereby to indicate a 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 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 to a second master a first transaction requesting a purge of sharable data in a coherence block of the first master, said first transaction including a third master address for a third master and a third index which identifies a data storage location within the third master; thereafter b) storing said third master address and third index in a next master storage location of said second master, thereby to indicate a next link of said second master; c) issuing from said second master to said third master a second transaction, said second transaction containing a second master address and a second index of said second master; thereafter d) issuing from said third mast to said first master a third transaction acknowledging completion of said first transaction; thereafter e) storing said second master address and said second index in a previous master storage location of said third master, thereby to indicate a previous link of said third master; and f) marking said coherence block of said first master as invalid.

Claim 15

A method for maintaining cache coherence in a multiprocessor computer system 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 to a second master a first transaction requesting a purge of sharable data in a coherence block of the first master, said first transaction including a third master address for a third master and a third index which identifies a data storage location within the third master; thereafter b) storing said third master address and third index in a next master storage location of said second master, thereby to indicate a next link of said second master; c) issuing from said second master to said third master a second transaction, said second transaction containing a second master address and a second index of said second master; thereafter d) issuing from said third mast to said first master a third transaction acknowledging completion of said first transaction; thereafter e) storing said second master address and said second index in a previous master storage location of said third master, thereby to indicate a previous link of said third master; and f) marking said coherence block of said first master as invalid.