# US 5,706,490 A · Method of processing conditional branch instructions in scalar/vector processor

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 5,706,490 A
- Document ID: US5706490A
- Status: Granted
- Kind: A
- Application number: 08/484,103
- Filed: 1995-06-07
- Granted: 1998-01-06
- Earliest claimed: 1989-12-29
- Assignees: Cray Research, Inc.
- Inventors: Douglas R. Beard; Andrew E. Phelps; Michael A. Woodmansee; Richard G. Blewett; Jeffrey A. Lohman; Alexander A. Silbey; George A. Spix; Frederick J. Simmons; Don A. Van Dyke
- Web page: https://patentgrep.com/patent/US5706490A

## CPC

- G06F 9/30087: {Synchronisation or serialisation instructions}
- G06F 8/433: {Dependency analysis; Data or control flow analysis}
- G06F 8/45: {Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions}
- G06F 9/30021: {Compare instructions, e.g. Greater-Than, Equal-To, MINMAX}
- G06F 9/3004: {to perform operations on memory}
- G06F 9/30094: {Condition code generation, e.g. Carry, Zero flag}
- G06F 9/3013: {according to data content, e.g. floating-point registers, address registers}
- G06F 9/30138: {Extension of register space, e.g. register cache}
- G06F 9/30141: {Implementation provisions of register files, e.g. ports}
- G06F 9/30149: {of variable length instructions}
- G06F 9/3802: {Instruction prefetching}
- G06F 9/3804: {for branches, e.g. hedging, branch folding}
- G06F 9/3814: {Implementation provisions of instruction buffers, e.g. prefetch buffer; banks}
- G06F 9/3816: {Instruction alignment, e.g. cache line crossing}
- G06F 9/3828: {with global bypass, e.g. between pipelines, between clusters}
- G06F 9/3834: {Maintaining memory consistency}
- G06F 9/3836: {Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution}
- G06F 9/3838: {Dependency mechanisms, e.g. register scoreboarding}
- G06F 9/3846: {using static prediction, e.g. branch taken strategy}
- G06F 9/3856: {Reordering of instructions, e.g. using queues or age tags}
- G06F 9/3858: {Result writeback, i.e. updating the architectural state or memory}
- G06F 9/3875: {Pipelining a single stage, e.g. superpipelining}
- G06F 9/3885: {using a plurality of independent parallel functional units}
- G06F 11/3632: {of specific synchronisation aspects}
- G06F 15/17381: {Two dimensional, e.g. mesh, torus}
- G06F 15/8076: {Details on data register access}
- G06F 15/8092: {Array of vector units}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A delayed branch mechanism maintains the flow of an instruction pipeline in a scalar/vector processor having an instruction cache and including instruction fetch means, a program counter, and instruction decode/issue means coupled to the instruction cache by means of the instruction pipeline. Conditional branch instructions are rated as likely conditional branch instructions or unlikely conditional branch instructions based on a probability that their branch conditions will be met. A number of pipeline clock periods required for testing the branch conditions are determined. The likely conditional branch instructions are issued and executed including transferring a branch-to-address to the program counter during the number of pipeline clock periods irrespective of a successful meeting of the branch conditions. A number of useful instructions sufficient to issue within the number of pipeline clock periods are placed into the instruction stream following the likely conditional branch instructions. A conditional branch instruction is canceled and returned to an instruction which would have followed the conditional branch instruction if the branch is not taken. No gap occurs in the instruction stream if the corresponding branch is successfully taken.

## Claims

### Claim 1

In a scalar/vector processor having an instruction cache and including instruction fetch means, a program counter, and instruction decode/issue means coupled to the instruction cache by means of an instruction pipeline, a method of maintaining the instruction pipeline to minimize the gaps in an instruction stream in the pipeline when issuing and executing conditional branch instructions, the method comprising the steps of:
rating each of at least ones of the conditional branch instructions as likely conditional branch instructions or unlikely conditional branch instructions based on a probability that branch conditions corresponding to each of the at least selected ones of the conditional branch instructions will be met and a corresponding branch taken;
determining a number of pipeline clock periods required for testing the corresponding branch conditions;
issuing and executing the likely conditional branch instructions including the step of transferring a branch-to-address to the program counter during said number of pipeline clock periods irrespective of a successful meeting of the corresponding branch conditions;
issuing into the instruction pipeline following the likely conditional branch instructions a number of original instructions sufficient to issue within said number of pipeline clock periods, wherein the number of original instructions is at least two; and
canceling a conditional branch instruction and returning to an instruction which would have followed the conditional branch instruction if the corresponding branch is not taken, wherein no gap occurs in the instruction stream if the corresponding branch is successfully taken.

### Claim 2 (depends on 1)

The method of claim 1 further comprising the step of:
issuing a target instruction cache load instruction corresponding to one of the likely conditional branch instructions during said number of pipeline clock periods following the issuing of the likely conditional branch instructions.