Browse Prior Art Database

Temporal and Spatial Considerate Reorder Algorithm for Trace Directed Program Restructuring

IP.com Disclosure Number: IPCOM000113180D
Original Publication Date: 1994-Jul-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 2 page(s) / 79K

Publishing Venue

IBM

Related People

Heisch, RR: AUTHOR [+4]

Abstract

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 and improved performance). 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 instruction paths are executed most often.

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

Temporal and Spatial Considerate Reorder Algorithm for Trace Directed
Program Restructuring

      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 and improved performance).  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 instruction
paths are executed 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.

      However, analyzing the address trace to determine optimal
reordering is a difficult problem.  A typical approach used for the
address trace analysis is to build a Directed Flow Graph (DFG) from
the address trace and then analyze the DFG to determine the "hot
paths" through the code and then generate the reorder list from this
hot path list.  This approach, while easy to implement, has the
disadvantage of discarding all temporal information contained in the
address trace and results in a less optimal reorder list.

      The idea presented here is to build multiple DFGs throughout
the execution of the program which represent the behavior of the
program at different intervals during execution and to then process
the DFG's to determine the optimal inst...