US 5,692,149 AGranted

Block replacement method in cache only memory architecture multiprocessor

AssigneesSamsung Electronics Co., Ltd., University of Minnesota

InventorGyungho Lee

Life of this patent

Estimating the term…

Loading patent…

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.

Claims8

Dependent claims

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.

6 more elements

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.

8 more elements

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.

10 more elements

Dependencies are inferred from the claim text.