Block replacement method in cache only memory architecture multiprocessor

• US 5,692,149 A
• Filed: 03/16/1995
• Issued: 11/25/1997
• Est. Priority Date: 03/16/1995
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd., University of Minnesota
• Original Assignee: Samsung Electronics Co. Ltd., University of Minnesota
• Inventors: Lee, Gyungho
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): Ellis, Kevin L.
• Application Number:
  US08/405,335
• Time in Patent Office: 985 Days
• Field of Search: 395/468, 395/471, 395/472, 395/460, 395/486, 395/485, 395/478, 395/461, 395/470
• US Class Current: 711/133
• CPC Class Codes: G06F 12/0831 using a bus scheme, e.g. with bus monitoring or watching means
• CPC Class Codes: G06F 2212/272 Cache only memory architecture [COMA]

Abstract

A block replacement method for use in a bus-based cache only memory architecture multiprocessor, is invoked when a block in a local memory of a first processing node in the multiprocessor is to be replaced to make a space for an incoming block supplied via a system bus from a local memory of a second processing node in the multiprocessor, and includes the following steps: (a) if the block of the first processing node is in an invalid state, or in a shared state, overwriting the block of the first processing node with the incoming block from the second processing node; (b) if the block of the first processing node is in an exclusive state, or in a shared owner state, relocating the block of the first processing node to a third processing node in the multiprocessor, selected in accordance with a predetermined priority scheme, and then overwriting the block of the first processing node with the incoming block from the second processing node; and (c) if the third single processing node cannot be determined among the processing nodes in the multiprocessor with the predetermined priority scheme in step (b), swapping the block of the first processing node for the incoming block from the second processing node.

Claims

1. An improved block replacement method for use in a bus-based multiprocessor employing cache only memory architecture, the multiprocessor including a multiplicity of processing nodes connected via a system bus, each processing node having a cache memory contained in a processing block and a local memory for storing data decomposed into a plurality of blocks, the local memory acting as a cache with no backing main memory provided in the multiprocessor, the method being invoked when a block in the local memory of a first processing node in the multiprocessor is to be replaced to make a space for an incoming block supplied via the system bus from the local memory of a second processing node in the multiprocessor, the method comprising the steps of:

(a) managing blocks in the local memory by using information on block states, each block state for denoting a current state of each block stored in the local memory, the block states containing;

an invalid state in which the block is not a current copy,

an exclusive state in which the block is the only valid copy in the multiprocessor,

a shared state in which the block is a valid copy, and at least one other valid copy exists in the system, and

a shared owner state in which the block of a processing node carries with it a responsibility for supplying its copy to another processing node upon receiving an access request for the block from said another processing node;

(b) if the block of the first processing node is in the invalid state, or in the shared state, overwriting the block of the first processing node with the incoming block from the second processing node;

(c) if the block of the first processing node is in the exclusive state, or in the shared owner state, relocating the block of the first processing node to a third processing node in the multiprocessor, selected in accordance with a predetermined priority scheme, and then overwriting the block of the first processing node with the incoming block from the second processing node; and

(d) if the third processing node cannot be determined among the processing nodes in the multiprocessor with the predetermined priority scheme in step (c), swapping the block of the first processing node for the incoming block from the second processing node.

2. The improved block replacement method as recited in claim 1, wherein the predetermined priority scheme gives the highest priority to a processing node in the multiprocessor, whose block, as accessed by an index field of a physical address of the block of the first processing node, has the same tag as a tag field of the physical address;

the next priority to processing nodes in the multiprocessors, whose blocks, as commonly accessed by the index field of the physical address, are in an invalid state and do not have the same tag as the tag field of the physical address; and

the lowest priority to processing nodes in the multiprocessor, whose blocks, as commonly accessed by the index field of the physical address, are in a shared state and do not have the same tag as the tag field of the physical address.

3. The improved block replacement method as recited in claim 2, wherein the processing nodes with the three different priorities compete for a system bus tenure using a distributed arbitration mechanism.

4. A local memory coherence method for use in a multiprocessor, the multiprocessor including a multiplicity of processing nodes connected via a system bus, each processing node having a local memory for storing data decomposed into a plurality of blocks, the local memory acting as a cache with no backing main memory provided in the multiprocessor, the method comprising the steps of:

(a) managing blocks in the local memory by using information on block states, each block state denoting a current state of each block stored in the local memory, the block states containing;

an invalid state in which the block is not a current copy,

an exclusive state in which the block is the only valid copy in the multiprocessor,

a shared state in which the block is a valid copy, and at least one other valid copy exists in the system, and

a shared owner state in which the block of a processing node carries with it a responsibility for supplying its copy to another processing node upon receiving an access request for the block copy from said another processing node;

(b) maintaining data coherence among the local memories in the multiprocessor by utilizing the state information; and

(c) if, in step (b), there arises a need to replace a block in the local memory of a first processing node in the multiprocessor with an incoming block supplied via the system bus from the local memory of a second processing node in the multiprocessor, executing the steps of;

(c-1) if the block of the first processing node is in the invalid state, or in the shared state, overwriting the block of the first processing node with the incoming block from the second processing node,

(c-2) if the block of the first processing node is in the exclusive state, or in the shared owner state, relocating the block of the first processing node to a third processing node in the multiprocessor, selected in accordance with a predetermined priority scheme, and then overwriting the block of the first processing node with the incoming block from the second processing node, and

(c-3) if the third processing node cannot be determined among the processing nodes in the multiprocessor with the predetermined priority scheme in step (c-2), swapping the block of the first processing node for the incoming block from the second processing node.

5. The improved block replacement method as recited in claim 4, wherein the predetermined priority scheme gives the highest priority to a processing node in the multiprocessor, whose block, as accessed by an index field of a physical address of the block of the first processing node, has the same tag as a tag field of the physical address;

the next priority to processing nodes in the multiprocessors, whose blocks, as commonly accessed by the index field of the physical address, are in an invalid state and do not have the same tag as the tag field of the physical address; and

the lowest priority to processing nodes in the multiprocessor, whose blocks, as commonly accessed by the index field of the physical address, are in a shared state and do not have the same tag as the tag field of the physical address.

6. The improved block replacement method as recited in claim 5, wherein the processing nodes with the three different priorities compete for a system bus tenure using a distributed arbitration mechanism.

7. A multiprocessor comprising:

a system bus; and

a multiplicity of processing nodes connected via the system bus, each processing node having a local memory means for storing data decomposed into a plurality of blocks, the local memory means acting as a cache with no backing main memory provided in the multiprocessor, wherein the local memory means includes;

a state information storage associated with the local memory, for storing a number of block states, each block state denoting the current state of each of data blocks stored in the local memory and the block states containing;

an invalid state in which the block is not a current copy,

an exclusive state in which the block is the only valid copy in the multiprocessor,

a shared state in which the block is a valid copy, and at least one other valid copy exists in the system, and

a shared owner state in which the block of a processing node carries with it a responsibility for supplying its copy to another processing node upon receiving an access request for such copy from said another processing node; and

block replacement means for, when a block in the local memory of a first processing node in the multiprocessor is to be replaced to make a space for an incoming block supplied via the system bus from the local memory of a second processing node in the multiprocessor, performing the replacement of the block of the first processing node by including;

means for, if the block of the first processing node is in the invalid state, or in the shared state, overwriting the block of the first processing node with the incoming block from the second processing node,

means for, if the block of the first processing node is in the exclusive state, or in the shared owner state, relocating the block of the first processing node to a third processing node in the multiprocessor, selected in accordance with a predetermined priority scheme, and then overwriting the block of the first processing node with the incoming block from the second processing node, and

means for, if the third processing node cannot be determined among the processing nodes in the multiprocessor with the predetermined priority scheme, swapping the block of the first processing node for the incoming block from the second processing node.

8. The multiprocessor as recited in claim 7, further comprising a cache memory coupled to the local memory means, wherein the cache memory has state information representing two cache states.