Browse Prior Art Database

Decode Branch History Table

IP.com Disclosure Number: IPCOM000050346D
Original Publication Date: 1982-Oct-01
Included in the Prior Art Database: 2005-Feb-10
Document File: 2 page(s) / 15K

Publishing Venue

IBM

Related People

Hughes, JF: AUTHOR [+5]

Abstract

A high performance computer, such as described in U.S. Patent 4,200,927, prefetches and predecodes instructions for sequential presentation to an execution unit. At least three separately gated and sequenced multi-instruction buffers for prefetched instructions permit continued sequential predecoding and buffering of instructions from three independent instruction streams identified by multiple branch instructions, some of which may be conditionally executed. Various branch instructions are predicted to be successful or unsuccessful.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Decode Branch History Table

A high performance computer, such as described in U.S. Patent 4,200,927, prefetches and predecodes instructions for sequential presentation to an execution unit. At least three separately gated and sequenced multi-instruction buffers for prefetched instructions permit continued sequential predecoding and buffering of instructions from three independent instruction streams identified by multiple branch instructions, some of which may be conditionally executed. Various branch instructions are predicted to be successful or unsuccessful. Result signals from the instruction execution unit, in response to execution of conditional branch instructions, will control the setting of various pointers and busy triggers associated with each instruction buffer, causing the next sequential instruction transferred to the instruction execution unit to be from the proper instruction stream based on the result of the branch on condition instruction.

A Decode History Table (DHT), to be described, improves the accuracy of predicting results of conditional branches by using history as the base for the guess. The DHT has the following characteristics:
The table has 1024 entries, each one bit wide.

The table is accessed with bits 21 to 29 of the address of The branch instruction.

The table is used only for the conditional BC (Branch Conditional and BCR (Branch on Condition Register) instructions (MASK different from 0 or 15 and R2 field for BCR not 0).

The entry is 1 (0) if the last conditional branch with this 10 bit address was taken (fell through).

The table is accessed during the decode cycle: if a conditional branch is being decoded, the entry read from the table is the branch guess.

The table is updated immediately after the branch is resolved by the E-unit only if the guess was incorrect.

Instruction fetching priority as between the three instruction buffers is changed to reflect the much better accuracy of the branch guessing.

One of the difficulties of implementing the DHT is that the system of the cited patent does not carry the address of the instruction being decoded. The solution adopted in the DHT design is to get instruction address bit 27, 28, 29 and 30 from the instruction buffer outpointers. For address bits 21 to 26, three 6 bit wide counters are provided, one for each instruction buffer. The counters are reset whenever the corresponding I-buffer is restarted. The reset addresses are bits 21 to 26 of the corresponding instruction address register. The counters are incremented whenever the outpointer of the corresponding I-buffer overflows. A 3-way multiplexer allows choosing the outpointer and counter corresponding to the I-buffer where the instruction currently being decoded is obtained from. This way, the selected counter and outpointer give address bits 21 to 30 of the instruction in the decoder.

The DHT table is physically organized as a 128-row, 9-...