Browse Prior Art Database

Method for Prioritizing Waiting Arithmetic Instructions

IP.com Disclosure Number: IPCOM000044322D
Original Publication Date: 1984-Dec-01
Included in the Prior Art Database: 2005-Feb-05
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

DeGroot, RD: AUTHOR

Abstract

A method for increasing the throughput of a highly concurrent arithmetic unit with multiple arithmetic pipelines is described. Throughout the following discussion, an arithmetic unit similar to the IBM System/360 Model 91 floating point arithmetic unit is assumed. In such a unit, arithmetic instructions are decoded and added to a waiting station (reservation station) for eventual processing by the arithmetic pipeline associated with the waiting station. There may be several pipelines and several waiting stations. Even though an instruction gets decoded, it may not get executed immediately. It may, in fact, exit the decode station, enter a waiting station, and wait many cycles. While it is waiting, later instructions may be decoded and entered into the wait station.

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

Page 1 of 2

Method for Prioritizing Waiting Arithmetic Instructions

A method for increasing the throughput of a highly concurrent arithmetic unit with multiple arithmetic pipelines is described. Throughout the following discussion, an arithmetic unit similar to the IBM System/360 Model 91 floating point arithmetic unit is assumed. In such a unit, arithmetic instructions are decoded and added to a waiting station (reservation station) for eventual processing by the arithmetic pipeline associated with the waiting station. There may be several pipelines and several waiting stations. Even though an instruction gets decoded, it may not get executed immediately. It may, in fact, exit the decode station, enter a waiting station, and wait many cycles. While it is waiting, later instructions may be decoded and entered into the wait station. Waiting instructions become eligible to be executed when all their operands become available. Because operands may become available in an order different than required for strict sequential execution of arithmetic instructions, the waiting station scheme allows instructions to execute out of order. The decoder can continue decoding new instructions as long as no interlocks prevent it from doing so, and as long as additional waiting stations are available for any newly decoded instructions. If all waiting stations are full, the decoder must block. This article describes a method for ensuring that the number of free waiting stations available is maximized. By so doing, the decoder blocks less often, and increased throughput of the arithmetic unit may be achieved. When two or more instructions in waiting stations become available for a single arithmetic pipeline, one must be chosen to start. Which one is chosen depends on the priority of each station. Several methods of prioritizing the waiting instructions exist, including fixed priority, first-come-first-served, etc. A prioritizing scheme is introduced here which selects instructions in a way that each instruction fired has an increased chance of causing others to be fired.

First, it is assumed that all arithmetic instructions are of the form FLOP Ra,Rb- >Rt. When such an instruction gets decoded, it joins a wait station. If the current values of Ra and Rb are available (are not in the process of being produced by some instruction already in execution), those values are gated out of the register file and entered into the wait station along with the instruction. If they are not available, the instruction is added to a wait station anyway, but special "not ready" bits are turned on to indicate which values were not available. Then, as instructions exit an ar...