Browse Prior Art Database

Address Generate Interlock Avoidance for Branch Instructions in a Branch History Table Processor

IP.com Disclosure Number: IPCOM000052473D
Original Publication Date: 1981-Jun-01
Included in the Prior Art Database: 2005-Feb-11
Document File: 5 page(s) / 129K

Publishing Venue

IBM

Related People

Driscoll, GC: AUTHOR [+4]

Abstract

High performance processors typically have separate decoding and execution units which operate concurrently in a pipelined configuration. The decoder contains an address adder for operand address and branch-target address calculations, while the execution unit contains the necessary logic for updating the contents of the general-purpose registers (GPRs).

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 46% of the total text.

Page 1 of 5

Address Generate Interlock Avoidance for Branch Instructions in a Branch History Table Processor

High performance processors typically have separate decoding and execution units which operate concurrently in a pipelined configuration. The decoder contains an address adder for operand address and branch-target address calculations, while the execution unit contains the necessary logic for updating the contents of the general-purpose registers (GPRs).

An address generation interlock (AGI) is a logical dependency between the address calculation function in the decoder and the GPR update function in the execution unit. AGIs cause pipeline delays which result in degraded processor performance. This article describes a system which can override AGI delays when the interlocked instruction is a branch instruction. The system improves processor performance because branch-type instructions are frequently the interlocked instructions when AGI delays occur.

The existence of a branch history table is assumed, and the system exploits the branch history table in a new and productive way.

The following section provides background by illustrating an address generation interlock and by describing the normal operation of a branch history table. The system is disclosed in a subsequent section.

Fig. 1 illustrates an address generation interlock (ACI) where a branch instruction is the interlocked instruction. In Fig. 1, the load instruction L updates GPR1 with the contents of a specified memory location. The conditional branch instruction (BC) uses the updated value of GPR1 as a base in the calculation of its target address. Because of this AGI, the address calculation for the BC cannot proceed until the L has been executed. In the example in Fig. 1, this AGI causes the BC to be delayed for three cycles in the decoder until the interlock on the branch instruction is removed by the execution of the L. Pipeline delays due to AGIs result in less pipeline throughput and lower overall processor performance.

Branch delays are another way in which pipeline throughput can be disrupted. In a simple case, the decoder is inhibited following the decoding of a branch until that branch is resolved in the E-unit.

The decoder then resumes decoding, following the resolved branch direction. This loss of decoder cycles can be minimized by using a branch history table.

A branch history table is a mechanism which predicts the branch outcome before the branch is actually processed. In the simplified schematic in Figs. 3A and 3B, the branch history table is assumed to provide a predicted branch direction (PBD) and (if the prediction is "branch taken" a predicted branch target address (PBTA).

During the decoding of the branch, the actual branch target address (ABTA) is generated via a GPR look-up for RR instructions (Fig. 3A). If a PBTA was

1

Page 2 of 5

provided by the branch history table, it is compared for equality to the ABTA. The result of the address comparison CA is r...