Browse Prior Art Database

Using Re-Association to Improve Instruction Scheduling

IP.com Disclosure Number: IPCOM000118367D
Original Publication Date: 1997-Jan-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 4 page(s) / 138K

Publishing Venue

IBM

Related People

Blainey, BJ: AUTHOR [+3]

Abstract

Disclosed is a method for improving execution performance of code generated by an optimizing compiler for pipelined processors. The compiler's instruction scheduler is enhanced to re-associate calculations to reduce stalls in the instruction stream.

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

Using Re-Association to Improve Instruction Scheduling

      Disclosed is a method for improving execution performance of
code generated by an optimizing compiler for pipelined processors.
The compiler's instruction scheduler is enhanced to re-associate
calculations to reduce stalls in the instruction stream.

      Even after instruction scheduling, some instruction streams
still cause stalls or idle cycles in the resources of pipelined
processors.  In many compilers, an instruction scheduler is applied
to a stream of instructions that has been created to implement the
computations called for in the source code for the function being
compiled.  It is the scheduler's job then to reorder the instructions
in the given stream into a semantically equivalent stream that makes
efficient use of the computational resources (pipeline stages,
functional units, etc.) of the target CPU.  While the scheduler is
capable of changing the order of the instructions, it does not change
the way in which the computations are implemented in the
instructions.  That is, if four operands are to be added together to
produce a sum a+b+c+d, and  this sum is computed in a given
instruction set by first computing the  sum a+b and then successively
adding in c and then d to compute the final sum, then the instruction
scheduler will be unable to reorder these instructions because each
one depends on the result of the previous.  Even if the
implementation has been to first compute a+b, then  compute c+d and
then add the two results together the scheduler will be  able to
reorder the first two instructions but must wait until their
operands become ready.  If, for example, operands b and c became
ready first, the scheduler would still be unable to schedule an
instruction, because one instruction needs both a and b, while the
other needs both  c and d.  When the processor executes such an
instruction stream, it will stall waiting for an operand to be ready.
Thus, the instruction scheduler is restricted in its schedule by the
particular partitioning  of operands across instructions dictated by
whatever mechanism within the compiler has generated the original
instruction stream.

      The proposed solution is to enhance the scheduler to make it
capable of "re-associating" calculations such as the above-mentioned
a+b+c+d so that, for instance, the sum b+c could be calculated first
if those were the first two operands to become available, regardless
of how operands had originally been grouped on the initial
instruction stream.  This operation can only be applied validly to
operators that are algebraically associative such as addition,
multiplication, bitwise  conjunction and the bitwise disjunctions.

      In this scheme, the input instruction stream to the scheduler
remains unchanged.  The scheduler would be enhanced to perform
additional processing when it sees a stall being generated in the
output instruction  stream (i.e., when it has instruc...