Browse Prior Art Database

Time Atributed Dependence Graph Scheme for Prediction of Execution Time for a Block of Assignment Statements with Looping

IP.com Disclosure Number: IPCOM000105891D
Original Publication Date: 1993-Sep-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 2 page(s) / 93K

Publishing Venue

IBM

Related People

Bose, P: AUTHOR

Abstract

Disclosed is a methodology, wholly implemented in software, which can be used to predict the execution time (in machine cycles) for a given block of assignment statements with looping (BASL) by static (compile-time) analysis alone. The method has been specifically tailored to work for super-scalar RISC machines implementing concurrent, pipelined execution modes under a parametrized organization and architecture model.

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

Time Atributed Dependence Graph Scheme for Prediction of Execution Time for a Block of Assignment Statements with Looping

      Disclosed is a methodology, wholly implemented in software,
which can be used to predict the execution time (in machine cycles)
for a given block of assignment statements with looping (BASL) by
static (compile-time) analysis alone.  The method has been
specifically tailored to work for super-scalar RISC machines
implementing concurrent, pipelined execution modes under a
parametrized organization and architecture model.

      The major difference between this approach and prior/current
practice is that the execution time for a specified target machine
can be predicted without resorting to low-level, detailed
trace-driven simulation.  The method is source-driven, i.e.  it takes
a high-level language program loop as input.  The estimation accuracy
is comparable to detailed timer runs for corresponding derived traces
(infinite cache model).  The estimation time, on the other hand, is a
tiny fraction of simulation time taken up by trace-driven timer runs.
The method is especially suitable for early estimation of CPU
performance for candidate organizations; also, the method has been
used in a compiler environment for execution cost estimation.

      As shown in Figure 1, the main inputs to the method are:  (a) a
source program loop (BASL), e.g. in FORTRAN; (b) CPU/memory
organization parameters (design point) within a given super scalar
model; (c) other (optional) dynamic program statistics, e.g., branch
or cache miss statistics.  The elements (or steps) comprising the
present invention are listed below:

1.  Parsing and translating the source program segment (loop) into a
    dependence graph.

2.  Augmenting the graph into a time-attributed dependence graph
    (TDG), by labeling the nodes and arcs with time delay (latency)
    attributes gleaned from the specified machine organization (and
    optional dynamic) parameters.

3.  Applying a novel graph-walk algorithm to traverse the TDG to
    perform a hierarchical (recursive) cost estimation for the graph.

         ------------          ---------------           -----------
 BASL--->|Translator|--> DG --->Augmentor    |-->TDG---->Evaluator |
         ------------          -A----------A--           -----------
                                |          |                 |
                                |          |                 |
                     CPU,MEM params   other dyn stats        V
                                                        perf.
estimate

        Figure 1.  Functional block diagram: BASL early timer

TDG Generation (step 2 above)

      Each n...