Browse Prior Art Database

New Algorithm for Performing Renaming in Super-Scalar Microprocessors

IP.com Disclosure Number: IPCOM000113813D
Original Publication Date: 1994-Oct-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 129K

Publishing Venue

IBM

Related People

Golla, RT: AUTHOR

Abstract

Rename assignment is the process of mapping General-Purpose Registers (GPRs) to the proper rename resource tags. The problem is characterized by determing which GPRs should be mapped to which rename resources. Previous algorithms solved this problem by performing a serial search through the GPR requests followed by a search through the available rename resources. The problem with this approach is that it requires too many logic levels to implement and can often impact the cycle time of processors that employ it. The new algorithm presented here requires half the number of logic levels of the previous algorithms to solve the same tag assignment problem.

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

New Algorithm for Performing Renaming in Super-Scalar Microprocessors

      Rename assignment is the process of mapping General-Purpose
Registers (GPRs) to the proper rename resource tags.  The problem is
characterized by determing which GPRs should be mapped to which
rename resources.  Previous algorithms solved this problem by
performing a serial search through the GPR requests followed by a
search through the available rename resources.  The problem with this
approach is that it requires too many logic levels to implement and
can often impact the cycle time of processors that employ it.  The
new algorithm presented here requires half the number of logic levels
of the previous algorithms to solve the same tag assignment problem.

      Renaming of GPRs is a common technique in improving the overall
performance of microprocessors.  Renaming seeks to elminate
back-to-back write hazards by eliminating contention from competing
instructions for the same target register.  For example, renaming can
be employed to remove the target register dependency of the following
code fragment:
        load Rt <- Ra
    add  Rt <- Ra, Rb

      Renaming solves the dependency problem in the above example by
remapping each of the Rt registers to different rename resources.  A
tag is often associated with each rename resource in order to
identify it.  Tag assignment is the process of mapping target GPRs to
the proper rename resource tags.

      In a super-scalar microprocessor, multiple instructions can be
dispatched in a given cycle.  Each of the instructions issued can
write to one or more GPRs requiring a tag assignment to be performed.
The tag assignment is performed by determining the number of GPR
write requests to be dispatched in a cycle and comparing it to the
number of rename resources currently available for allocation.  If
the number of GPR write re...