Browse Prior Art Database

Priority Scheduling of Branches within Multisequencing in a Single Instruction Stream

IP.com Disclosure Number: IPCOM000106737D
Original Publication Date: 1993-Dec-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 2 page(s) / 84K

Publishing Venue

IBM

Related People

Ekanadham, K: AUTHOR [+3]

Abstract

Within Multisequencing in a Single InstructionStream (MSIS) a means of scheduling instructions during the sequential pass is to use the Occupancy Assignment Algorithm (OAA).

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

Priority Scheduling of Branches within Multisequencing in a Single Instruction Stream

      Within Multisequencing in a Single InstructionStream (MSIS) a
means of scheduling instructions during the sequential pass is to use
the Occupancy Assignment Algorithm (OAA).

Occupancy Assignment Algorithm

1.  Each time-slot within a window of length delta is associated with
    the number of instructions that have been assigned to that
    time-slot, the so-called OCCUPANCY of the time-slot.

2.  The time-slot of an instruction is computed based on the
    time-slot of the conceptually earlier instructions which set the
    inputs to that instruction.  This time-slot is called the
    SELECTED time-slot.

3.  If the OCCUPANCY of the SELECTED time-slot is less than lambda,
    the number of PE's, then the instruction is assigned to that
    time-slot and the OCCUPANCY is incremented by one.

4.  If the OCCUPANCY of the SELECTED time-slot is lambda then the
    instruction is assigned to the first later time-slot whose
    OCCUPANCY is less than lambda  and said OCCUPANCY is incremented
    by one.

5.  The instruction which has the largest time-slot extant at any
    given time determines the bottom of the time-slot window.

The decoder slot assigned to a given instruction depends on the
timing of the instructions that set its inputs and is rarely the DDI
of the instruction.

Determining the DDI

      The DAG can be used to determine the dependency depth (DDI) of
each instruction.  The DDI corresponds to the cycle of decode of an
instruction when there are more PE's than instructions and
corresponds to the row index of the matrix that represents the
schedule in such a circumstance.  The simplest way to compute the DDI
of an instruction is to retain the DDI of the instruction which last
set each of the registers.  The DDI is then computed recursively
using these values that relate to the registers required as input.
Registers in MSIS are a generalized concept involving those aspects
through which the execution of an instruction depends on the
execution of an earlier instruction.  Suitable adjustment is made for
AGEN DEPENDENCY or EXECUTION DEPENDENCY in computing the resultant
DDI.

      The reason for the disparity is that other, conceptually
...