Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-07-03
2002-04-30
Gossage, Glenn (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S122000, C712S207000
Reexamination Certificate
active
06381679
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to an information processing unit having a hierarchical cache structure, and relates more particularly to an information processing unit equipped with a software prefetch instruction which can reduce an overhead due to a cache miss by transferring in advance, from a main memory to a cache, an operation data to be used for an operation.
In general, an information processing unit having a cache reads an operation from a main memory and uses it when the operation referred to by an instruction does not exist in the cache or when a cache miss has occurred. Usually, a reading of this operation takes numerous times (several times or dozens of times) that of the time required for a cache access. Accordingly, an information processing unit of this type has a problem in that when a cache miss has occurred, an execution of a succeeding instruction is delayed until an operation has been read from the main memory. Thus, the execution time of the information processing unit is extended, thereby restricting the performance of the information processing unit.
For solving the above-described problem, there is a technique which is known for transferring in advance from main memory to a cache an operation data to be used in the future and for reducing the penalty of a cache miss by achieving a cache hit at the time when the operation data is used. Research on a software prefetch instruction for achieving this has been carried out and a result of this study is being used in various information processing units.
As a conventional technique relating to the software prefetch instruction, a technique described in the following paper, for example, is known: Callahan, D, Kennedy, K. Porterfield, A., “Software Prefetching”, Proceedings of the 4th International Conference on Architectural Support for Programming Languages and Operating Systems, April 1991, pp. 40-52.
The operation of the software prefetching instruction by an information processing unit according to the conventional technique will be explained below with reference to drawings.
FIG. 5
is a block diagram for showing an example of the configuration of the information processing unit according to the conventional technique, and
FIGS. 6A and 6B
are time charts for explaining a processing operation according to a presence or absence of a software prefetch. In
FIG. 5
,
21
denotes a CPU (central processing unit),
22
a primary cache,
24
a SCU (storage control unit) and
25
a main memory.
The conventional technique shown in
FIG. 5
is an example of the information processing unit having a cache of one hierarchical level, and this information processing unit is structured by a CPU
21
for carrying out an information processing, a primary cache
22
, a main memory
25
and an SCU
24
for controlling a writing and reading of information to and from the main memory
25
. In this information processing unit, the CPU
21
searches an operation data in the primary cache
22
to refer to the operation data. When a cache miss has occurred, the CPU
21
issues a request for transferring the operation data, to the SCU
24
through a request line
201
and an address line
202
. The SCU
24
reads the operation data from the main memory
25
and transfers this data to the CPU
21
through a data line
204
. The CPU
21
stores the received operation data in the primary cache
22
and also uses this data for an operation.
The operation of the information processing unit shown in
FIG. 5
will be explained next by assuming that the processing of an instruction by the CPU
21
is carried out at five pipeline stages of IF (instruction fetch), D (decoding), E (execution), A (operation access) and W (register writing).
FIG. 6A
shows a time chart for the case where instructions
0
to
3
are sequentially inputted to the pipelines and a software prefetching is not carried out, in the information processing unit having the above-described structure.
An example shown in
FIG. 6A
shows a case where a cache miss has occurred in an operation access of the instruction
1
which is a load instruction. In this case, the processing of the instruction
1
is kept waiting until the operation has been read from the main memory at the stage A for carrying out an operation access, and the processing of the instruction
1
at the stage W is kept waiting until that time. Accordingly, the processings of the instructions
2
and
3
at the stages A and E respectively and the subsequent stages are kept waiting, with a result that all the time required for reading the operation from the main memory appears as a penalty due to the cache miss.
The time chart shown in
FIG. 6B
shows a case where a software prefetch is carried out. In this case, prior to the execution of the instruction
1
which is a load instruction, a software prefetch instruction designated by an instruction
1
is executed in advance by the time period required for transferring the operation from the main memory. As a result, the instructions
2
and
3
which follow the instruction
1
are executed without being interrupted by proceeding with the processing at the pipeline stages, during the period while the operation is being transferred from the main memory by the instruction
1
according to the software prefetch. By the time when the instruction
1
makes an access to the operation data, the operation data required by this instruction
1
has been stored in the primary cache
22
by the instruction
1
which is the software prefetch instruction, and a cache hit is achieved. Thus, it is possible to reduce a penalty attributable to the cache miss.
FIG. 7
is a block diagram for showing another example of the configuration of the information processing unit according to the conventional technique, and
FIGS. 8A and 8B
are time charts for explaining a processing operation according to a case where a software prefetch is carried out. In
FIG. 7
,
23
denotes a secondary cache and all other symbols denote the same items as those in FIG.
5
.
The conventional technique shown in
FIG. 7
shows an example of the configuration of the information processing unit having caches of two hierarchical levels. This information processing unit has the same structure as that of the conventional technique shown in
FIG. 5
, except the primary cache
22
is incorporated within the CPU
21
and a secondary cache
23
is provided.
According to the conventional technique shown in
FIG. 7
, the CPU
21
searches the primary cache
22
at first to refer to an operation data. When the primary cache
22
has a cache miss, the CPU
21
searches the secondary cache
23
. If the secondary cache
23
is hit, the operation data is transferred from the secondary cache
23
to the primary cache
22
. In the subsequent explanation, this transfer will be called a block transfer and the operation data to be transferred will be called a block.
When a miss occurs in the secondary cache
23
, the SCU
24
reads the operation data from the main memory
25
and transfers this data to the CPU
21
. In the subsequent explanation, this transfer will be called a line transfer and the data to be transferred will be called a line. Usually, the data quantity of the block is smaller than the data quantity of the line, and at the time of the line transfer, only data of the line is stored in the secondary cache
23
and only data of the block referred to is stored in the primary cache
22
.
The operation of the information processing unit shown in
FIG. 7
will be explained next by assuming that the processing of an instruction by the CPU
21
is carried out at five pipeline stages of IF (instruction fetch), D (decoding), E (execution), A (operation access) and W (register writing), in a manner similar to that explained above.
FIGS. 8A and 8B
show a case where instructions
0
to
3
are sequentially inputted to the pipelines and are processed, in the information processing unit having the above-described structure.
FIG. 8A
is a time chart of the case for executing a software prefetch i
Imori Hiromitsu
Kurihara Toshihiko
Matsubara Kenji
Antonelli Terry Stout & Kraus LLP
Gossage Glenn
Hitachi , Ltd.
LandOfFree
Information processing system with prefetch instructions... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Information processing system with prefetch instructions..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Information processing system with prefetch instructions... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2840262