Browse Prior Art Database

Simple Algorithm for Locking Short Loops in an Instruction Buffer

IP.com Disclosure Number: IPCOM000049463D
Original Publication Date: 1982-Jun-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Agerwala, TKM: AUTHOR

Abstract

The proposed algorithm will capture most short loops with minimal hardware. Once a loop is captured, subsequent instructions are fetched from the I-buffer. This reduces the absolute branch time and interference with operand accesses.

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

Page 1 of 2

Simple Algorithm for Locking Short Loops in an Instruction Buffer

The proposed algorithm will capture most short loops with minimal hardware. Once a loop is captured, subsequent instructions are fetched from the I-buffer. This reduces the absolute branch time and interference with operand accesses.

The key concept set forth is that to capture short backward loops, a general branch backward into I-buffer capability is not required. A simple bit by bit compare with the address at the logical top of the I-buffer is sufficient to obtain most of the benefit of look behind. More details are given below and a specific implementation is described.

Hardware INSTRUCTION BUFFER

This is an 8-double word (DW) buffer. There is a one to one correspondence between instruction double word (DW) addresses and buffer location: the 3 lower order bits of the DW address specify the I-buffer location. A bit B(1) is associated with each buffer location. REGISTERS

Lower Bound (LB) and Upper Bound (UB) indicate the limits of DW addresses of instructions currently in the I-buffer. (These are needed, anyway, to detect a store into I-stream). Let 1b and ub indicate the corresponding buffer positions at any instant of time.

A decode pointer (DP) indicates the position of the instruction currently being decoded. COMPARATOR

This can test the equality between a branch target address and LB (a simple bit by bit compare). Instruction Fetch into the I-Buffer

When a new branch group is fetched into the buffer, the following events take place: B(1) is set to 0 for all buffer locations.

LB and UB are set to the first instruction DW address.

DP is set to 1b.

As each DW arrives, B(1) is set to 1 and UB is incremented. Decoding starts with the arrival of the first double word. (When all instructions in a DW are decoded, DP is incremented by 1 (mod 8). DP is not allowed to get ahead of UB.

Prefetching takes place as follows: Let X denote the low order bits of the instruction DW to be fetched. If IBUF(X) has B(1)=0

Then prefetch X

Else if (X - DP) mod 8 is less than (see original)*

and LM=0

Then (Subsequently, cancel the update of

1b or any succeeding location if loop mode is

1

Page 2 of 2

detected). prefetch X

I...