Browse Prior Art Database

Efficient Scheduling and Operand Renaming of Groups of Instructions

IP.com Disclosure Number: IPCOM000123782D
Original Publication Date: 1999-Apr-01
Included in the Prior Art Database: 2005-Apr-05
Document File: 7 page(s) / 289K

Publishing Venue

IBM

Related People

Gschwind, MK: AUTHOR

Abstract

Problem solved by this invention: Scheduling of computer instructions is concerned with generating a sequence of instructions to minimize the execution time of the overall program. Scheduling of operations can either be performed at compile or at run time. Examples of systems performing scheduling at run time are dynamic binary translation {1} {2} (3} {4} and dynamic instruction formatting systems {5}. Since the time consumed to schedule an operation directly affects overall program execution time, it has to be maintained low to achieve good system performance.

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

Efficient Scheduling and Operand Renaming of Groups of Instructions

   Problem solved by this invention

   Scheduling of computer instructions is concerned with
generating a sequence of instructions to minimize the execution time
of the overall program.  Scheduling of operations can either be
performed at compile or at run time.  Examples of systems performing
scheduling at run time are dynamic binary translation {1} {2} (3} {4}
and dynamic instruction formatting systems {5}.  Since the time
consumed to schedule an operation directly affects overall program
execution time, it has to be maintained low to achieve good system
performance.

   The present document presents a greedy scheduling method
including speculative execution and register renaming on single
entry, multiple exit blocks in linear time.  The invention is based
on the use of resource availability vectors, which are combined to
summarize resource usage and identify the earliest slot in the
schedule which meets constraints for a given instruction.  These
scheduling constraints include such factors as availability of
operands, function units, and rename registers.

   State of the art

   While scheduling and register assignment are NP-complete,
a number of heuristics have been proposed previously.  These
heuristics usually involve scanning through a list of instructions
which have been previously scheduled to determine operand
availability and an appropriate issue slot.  This results in
quadratic execution time as a function of the number of instructions
to be scheduled in a group.  Additional operations are necessary to
rename registers to resolve output dependencies which would otherwise
limit the achievable instruction level parallelism by serializing
operations.

   Description of operation

   The present invention is optimized for achieving high
scheduling speed while maintaining a high schedule quality.  To
successfully schedule an operation in a given issue slot, a number of
conditions have to be met.  These conditions typically are the
presence of a number of resources:
  o  an issue slot
  o  input operands
  o  function unit(s): an instruction can require one or more
     function units to execute on, which must be available for
     one or more cycles at a given time after the instruction
     has been issued.
  o  rename register: if renaming is necessary, a rename register
     must be available.

   Availability information for these resources can be
summarized with an availability vector for each of these resources,
with each bit referring to a cycle in the schedule.  By intersecting
the availability vectors for all resources needed by a particular
operation, all possible issue slots can be identified.

   Consider the scheduling of an instruction 'add r4=r2, r3',
which requires an issue slot, the values from source registers r2
and r3, and an ALU.  Figure 1 shows an example of the availability
vectors required to sche...