Browse Prior Art Database

Address Reorder List Generation for Trace-Directed Program Restructuring

IP.com Disclosure Number: IPCOM000111353D
Original Publication Date: 1994-Feb-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 2 page(s) / 91K

Publishing Venue

IBM

Related People

Heisch, RR: AUTHOR

Abstract

This disclosure presents an improved algorithm for generating the address reorder list used for Trace-Directed Program Restructuring (TDPR). TDPR is a well-known method for reorganizing the instructions in a program, based on an address trace of the actual execution of that program, so as to improve the utilization of the instruction cache (which typically results in improved performance) and the utilization of real memory (which typically results in a reduction in real memory requirements). The TDPR process is summarized as follows. First, an instruction address trace is captured for the program to be restructured while running a typical workload or set of workloads representing typical program usage.

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

Address Reorder List Generation for Trace-Directed Program Restructuring

      This disclosure presents an improved algorithm for generating
the address reorder list used for Trace-Directed Program
Restructuring (TDPR).  TDPR is a well-known method for reorganizing
the instructions in a program, based on an address trace of the
actual execution of that program, so as to improve the utilization of
the instruction cache (which typically results in improved
performance) and the utilization of real memory (which typically
results in a reduction in real memory requirements).  The TDPR
process is summarized as follows.  First, an instruction address
trace is captured for the program to be restructured while running a
typical workload or set of workloads representing typical program
usage.  Next, the address trace is analyzed to determine which
instructions are executed most often and where control is transferred
next most often.  Ultimately, this analysis provides the optimal
instruction ordering for that program which will yield the maximum
performance improvement and/or memory requirements reduction.  The
program is then restructured by rearranging the instructions to match
this optimal ordering.  The final result is a faster program that
uses less memory when run on the same or similar workloads.

      The algorithm presented here has been implemented on the
RS/6000* and has produced speedups of up to 73% for the AIX* Kernel
and up to 19% for the Oracle database, and real memory requirements
have been decreased by up to 61% (representing more than 1/2MB) for
Oracle.

The algorithm is as follows:

1.  Build a Directed Flow Graph (DFG) from the address trace data
    that represents how often each basic block was executed and how
    often and where control was transferred from each basic block.

2.  Provide the following 3 user-selectable alternate methods for
    traversing the DFG to produce the address reorder list:

    a.  Starting with the most highly executed basic block, follow
        the most executed paths until a cycle is detected (i.e., a
        previously visited basic block).  As each basic block is
        visited in the DFG, append the bas...