Instruction pipeline with a branch prefetch when the branch...

Details Instruction pipeline with a branch prefetch when the branch... Instruction pipeline with a branch prefetch when the branch...

1993-06-10

2003-10-07

Donaghue, Larry D. (Department: 2154)

Electrical computers and digital processing systems: processing

Processing control

Branching

C712S207000, C712S023000

Reexamination Certificate

active

06631464

ABSTRACT:

BACKGROUND OF THE INVENTION
This invention relates to a control system for fetching an instruction group following a branch target instruction when a branch instruction is executed in a computer system using a one-cycle pipeline system and more particularly, to an instruction fetching control system for performing a prior branch judgement by judging whether a condition judgement can be performed in a cycle preceding a branch judgement cycle in which the branch instruction is executed.
FIG. 1
shows a view for explaining an execution of a branch instruction in a prior-art one-cycle pipeline system. The numbers (
1
) to (
12
) at the top of the drawing represent respective timings of machine cycles and process part symbols D, A, T, B, E, and W of respective instructions represent respective processing states (which are also called “cycles” or stages hereinafter) in the pipeline control.
D indicates a decoding cycle for decoding an instruction to be executed. A is an address calculating cycle for performing an address calculation to fetch the branch target instruction, T is an address translating cycle for translating a logical address into a real address, B is a cycle for fetching a branch target instruction, E is a branch judging cycle for performing a judgement as to whether the branch condition is successful or not and W is a cycle for storing an arithmetic operation result. These cycles are well known.
In the pipeline system, an instruction to be executed is prefetched. The prefetch of the executed instruction is also conducted in a pipeline manner. The periods for period part symbols IA, IT and IB in the instruction prefetch pipeline in the lower part of
FIG. 1
represent process cycles for prefetching an instruction following the branch instruction and IA*, IT* and IB* represent process cycles for prefetching the instruction following the branch target instruction. For example, address calculating cycle IA, address translating cycle IT and cycle IB for fetching data from a buffer in the instruction prefetch pipeline shown in process IPP, is for fetching fetching instruction {circle around (N)}+3 where the branch of branch instruction B is not successful.
In
FIG. 1
, symbols “Next”, shown in the lower part of
FIG. 1
, represent the kind of the instruction to be prefetched. These symbols show that the instruction (also called “Next side” of the part) following the branch instruction is prefetched. “Target” indicates that an instruction (called “Target side” of the part) following the branch target instruction is prefetched and “(Next)” shows the case in which the instruction following the branch instruction is prefetched and the case in which the instruction is not fetched are selected.
Branch instruction {circle around (B)} is first executed in the example shown in FIG.
1
and instruction sets {circle around (N)}, {circle around (N)}+1, {circle around (N)}+2 and {circle around (N)}+3 following the branch instruction {circle around (B)} are then executed sequentially. The branch condition is successful in the branch judging cycle (E state) of branch instruction {circle around (B)} in timing step (
5
) and branch target instruction {circle around (T)} and instruction sets {circle around (T)} {circle around (T)}+1, {circle around (T)}+2, . . . following the branch target instruction are executed.
FIG. 1
shows the case where the number of branch target instructions {circle around (T)}, {circle around (T)}+1, {circle around (T)}+2 obtained by one time fetch of the branch instruction carried out during B state of branch instruction {circle around (B)} is three and the branch is carried out depending on the result of the branch judgement during E state of branch instruction {circle around (B)} and the execution of branch target instructions {circle around (T)}, {circle around (T)}+1, {circle around (T)}+2 is started smoothly.
In a pipeline system, as recited above, an instruction prefetch is processed as a pipeline. Thus, it is necessary to determine the fetch address at which an address calculation IA should be conducted in a stage which is two cycle prior to stage IB in which a prefetch of an instruction is actually carried out, as shown in FIG.
2
.
FIG. 2
shows a view for explaining an instruction prefetch pipeline. Period part symbols IA, IT, IB show respective process stages. IA designates an address calculation cycle (ADRS), IT represents an address translation cycle (TLB/TAG) and IB represents an instruction fetching cycle (FETCH).
Generally, i.e., without being limited to a branch instruction, it is necessary to determine the addresses of instructions “Next 1” and “Next 2” to be prefetched in the IA cycle two cycles prior to the IB cycle in which an instruction is actually fetched.
Where the pipeline process is carried out as shown in FIG.
1
and an instruction prefetch is executed in the form shown in
FIG. 2
, then, there is the problem that an instruction prefetch, which should be carried out in the same cycle at timing (
5
) in
FIG. 1
as branch judging cycle (E state) of branch instruction {circle around (B)} in
FIG. 1
or in the next cycle (timing (
6
) and (
7
) in FIG.
1
), is conducted as to a part (“target side”) following branch target instruction {circle around (T)} or a part (“next side”) following branch instruction {circle around (B)}.
As shown in
FIG. 3
, in the example (No. 1) where a target side instruction fetch does not exist when the branch target instruction starts, the branch condition of branch judging cycle (E state) of branch instruction {circle around (B)} is successful and only T of one machine instruction of the branch target occurring during B state (timing (
4
) in
FIG. 3
) is fetched, branch target instruction {circle around (T)} can then be executed during timing (
5
) but, at this time instruction {circle around (T)}+1 of Target Side is not yet fetched, and thus, execution of instruction {circle around (T)}+1 cannot start during timing (
6
).
In order to solve this problem, the means for fetching the branch target instruction {circle around (T)} together with instructions {circle around (T)}+1, {circle around (T)}+2 . . . , following the branch target instruction in B state of branch instruction {circle around (B)} is considered. In this case, the amount of instruction which can be fetched by one fetch operation, is about 1 to 2 instruction lengths, although the amount of instruction depends on the method of forming a central processor unit (CPU) and an instruction length. As shown in the example (No. 2) where the target side instruction is not fetched upon a start of the branch target instruction shown in FIG.
4
and where two instructions comprising branch target instruction {circle around (T)} and {circle around (T)}+1 are fetched, instruction {circle around (T)}+2 of the target side is not fetched at timings (
5
) and (
6
). Therefore, instruction {circle around (T)}+1 cannot be executed in timing (
7
) and the central processor unit (CPU) falls into a state of waiting for an instruction to be executed to be fetched.
In order to solve the problem, as shown in
FIG. 4
, for example, it is necessary to determine the fetch address, at least upon the timing (
4
) when an instruction {circle around (T)}+2 of a target side is fetched in timing (
6
). The determination of the fetch address uses a result of an address calculation at an A state of branch instruction {circle around (B)}. Thus, it is not necessary to wait for an E cycle to determine whether the branch condition is successful or not. However, when the target side instruction fetch is driven, it is necessary thereafter to add an extra hardware to switch the process to an instruction fetch of a part following the branch instruction.
Namely, when the branch target instruction address is maintained and the instruction fetch following the branch target instruction is conducted, the means for updating this instruction fetch, namely, the means for calculating an address of an instru

Affiliated with

Also associated with

Rating

Instruction pipeline with a branch prefetch when the branch... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Instruction pipeline with a branch prefetch when the branch..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Instruction pipeline with a branch prefetch when the branch... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3164950