Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2000-03-21
2004-06-22
Chan, Eddie (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S240000
Reexamination Certificate
active
06754813
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an information processing apparatus and method for performing a pipeline process using a branch prediction mechanism.
2. Description of the Related Art
A recent computer has a branch prediction mechanism using a table to quickly perform an instruction process, especially a branch process. The branch prediction mechanism contains in the branch target table the prediction information about whether or not there is a branch instruction, and, if there is a branch instruction, about whether or not the branch is to be taken, and the information about a branch target instruction address, and searches the table using an instruction fetch address when an instruction is fetched. If there is a branch instruction and the information that the branch is taken is entered, then a branch target instruction fetch is invoked using a corresponding branch target instruction address.
Thus, a branch target instruction fetch can be invoked at an earliest possible timing without fetching and decoding an instruction. As a result, a wait time taken for fetching a branch target instruction can be shortened, and a process can be quickly performed by a computer.
The branch prediction using the above described table is described in detail in various documents and patent applications. For example, the Japanese Patent Laid-Open No.6-324865 (‘Multiprediction-type Branch Prediction Mechanism’, Japanese Patent Application No.3-252872) discloses the technology of using both branch prediction used in a decoding process and branch prediction used in an instruction fetching process. In this document, various prior art technologies relating to branch prediction are introduced.
A program having a loop structure can be quickly executed in most cases by predicting a branch because it is predicted that a branching operation using a previously branched instruction can occur again, and the branch prediction in a program in which a loop process is executed is correct except an exit from the loop. Especially, the prior art technologies which emphasize quick execution of a loop can be listed below.
Japanese Patent Application Laid-Open No.7-73104 (‘Cache System’, Japanese Patent Application No.6-117056)
Published Japanese Translation of PCT International publication for Patent Application No.10-510076 (‘Limited Run Branch Prediction’, Japanese Patent Application No.8-518876)
Japanese Patent Application Laid-Open No.10-333906 (‘Branch Prediction Apparatus’, Japanese Patent Application No.9-139736)
Japanese Patent Application Laid-Open No.4-101219 (‘Instruction Branch Prediction System’, Japanese Patent Application No.2-218655)
Japanese Patent Application Laid-Open No.63-141132 (‘Instruction Prefetch Apparatus’, Japanese Patent Application No.61-289363)
Japanese Patent Application Laid-Open No.1-271842 (‘Information Processing Apparatus’, Japanese Patent Application No.63-100818)
The above described technologies are generally classified as follows.
(1) To quickly fetch a branch target instruction
(2) To correctly predict the behavior of a loop
(3) To reduce the penalty when a branch prediction fails.
FIG. 1A
shows a general configuration of a common pipeline computer. When an instruction fetch address and a fetch request is transmitted from an instruction fetch control unit
11
to an instruction memory access pipeline (instruction fetch pipeline)
12
, an instruction code is fetched based on the address, and supplied to an instruction buffer
13
. The instructions stored in the instruction buffer
13
are passed to an instruction execution pipeline
14
, thereby starting the execution of the instructions.
The instruction execution pipeline
14
executes an operations instruction, makes a branch decision when a branch instruction is detected, and transmits the information about whether or not a branch is taken (branch taken information), a branch target address, etc. to the instruction fetch control unit
11
. Under the control by the instruction fetch control unit
11
, the instruction fetch continues based on the new instruction fetch address.
FIG. 1B
shows the configuration of the circuit of the instruction fetch control unit
11
. The circuit shown in
FIG. 1B
includes incrementers
21
and
22
, a branch target table (BTB)
23
, a comparison circuit (CMP)
24
, an AND circuit
25
, selection circuits (selector, SEL)
26
and
27
, and a prefetch program counter (PFPC)
28
.
When a branch prediction is not made in branch fetch control, a signal D_TA (branch target address of an instruction processed at the decoding stage), the BTB
23
, the CMP
24
, the AND circuit
25
, and the 2-input selector
26
are not required.
In this case, the first fetch address is selected by the selection circuit
27
through a signal PC, and enters the PFPC
28
. The address held in the PFPC
28
is an instruction fetch address, and transmitted to the instruction memory access pipeline
12
shown in FIG.
1
A. At this time, the incrementer
22
receives an output signal from the PFPC
28
, adds
8
to the signal, and outputs a resultant address.
If a signal indicating that a branch is taken (TAKEN described later) is not asserted (if the signal is not a logic ‘1’), then an output from the incrementer
22
is selected at the next clock, and the address is fetched. Thus, consecutive instructions are fetched. Here, it is assumed that an instruction occupies 4 bytes and two instructions are simultaneously fetched.
FIG. 1C
shows the circuit of the instruction execution pipeline
14
shown in FIG.
1
A. The circuit shown in
FIG. 1C
is provided with the BTB
23
, registers
31
,
33
,
34
,
35
,
36
,
38
,
39
,
41
,
42
,
43
,
44
,
45
,
46
,
47
,
48
,
49
,
51
,
53
,
54
,
55
,
56
,
57
,
58
, and
59
, a general purpose register (GR)
32
, an arithmetic and logic unit
37
, a decoder (DEC)
40
, a branch decision circuit (BRC_DECISION)
50
, and an adder
52
.
In
FIG. 1C
, the characters D, A, E, and W indicating the process stages of instructions respectively correspond to a decode stage (D stage), an address computation stage (A stage), an execution stage (E stage), and a write stage (W stage).
In this example, two instructions are executed in a pipeline operation. The preceding instruction is a comparison instruction (CMP). This instruction reads two values to be compared with each other from the general purpose register
32
, performs a comparing operation using the arithmetic and logic unit
37
at the E stage, and writes the resultant condition code (CC) to the register
38
.
The subsequent instruction is a branch instruction (BRC). This instruction computes the branch target address at the D stage according to the signal D_PC (a program counter of the instruction processed at the D stage), the branch target address offset portion (OFFS) in the branch instruction, and the constant of 4.
In a decoding operation, a signal D_BRC indicating whether or not an instruction is a branch instruction, and a signal D_CND indicating the condition of branching are generated, managed as pipeline tags, and transferred to the subsequent stage. Since the CC of the result of the preceding comparison instruction is used in a branch decision, a branch decision for the subsequent branch instruction is made at the E stage. In this example, the branch decision is made by the branch decision circuit
50
using the condition of the CC selected by the E_CND.
When a branch is taken, the signal TAKEN from the branch decision circuit
50
is asserted, the signal E_TA (the branch target address of the instruction processed at the E stage) is selected as shown in
FIG. 1B
, and the address is input to the PFPC
28
.
The address E_TA corresponds to the address obtained by adding up the signal D_PC, the offset, and 4 at the D stage of the branch instruction as shown in
FIG. 1C
, managed as a pipeline tag, and transferred to the E stage. However, in this example, the branch target address of the branch instruction is defined as a sum of the value of the program counter
Chan Eddie
Fujitsu Limited
Harkness Charles
Staas & Halsey , LLP
LandOfFree
Apparatus and method of processing information for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method of processing information for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method of processing information for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3319371