Generating Optimal Contiguous Evaluations for Expression DAGs
Christoph W. Keßler, Thomas Rauber
Computer Languages 21(2), 1995.
Abstract:
We consider the NP-complete problem of generating contiguous
evaluations for expression DAGs with a minimal number of registers.
We present two algorithms
that generate optimal contiguous evaluation for a given DAG.
The first is a modification of a complete search algorithm
that omits the generation of redundant evaluations.
The second algorithm
generates only the most promising
evaluations by splitting the DAG into trees with import and
export nodes and evaluating the trees with a modified labeling scheme.
Experiments with randomly generated DAGs and large DAGs from real
application programs confirm that the new algorithms generate optimal
contiguous evaluations quite fast.
Comments:
This article presents an algorithm that computes a space-optimal contiguous
schedule for basic blocks with DAG-structured data dependences.
The goal is to mimimize the number of registers used
(minimum register instruction scheduling problem, MRIS),
subject to the constraint that the schedules taken into consideration
must be generatable by postorder traversals of the dependence graph.
BibTeX:
@article{ Kessler_j1,
author = {Christoph W. Ke{\ss}ler and Thomas Rauber},
title = {Generating Optimal Contiguous Evaluations for Expression {DAG}s},
journal = {Computer Languages},
volume = {21}, number = {2},
pages = {113--127},
year = {1995}
}
Download:
Copyright notice:
This section contains links to material covered by copyright;
copyright may be held by the author and/or the publisher.
You may browse them at your convenience
(in the same spirit as you may read a journal or a proceedings article in a public library).
Retrieving, copying, or distributing these files, however, may violate
the copyright protection law. We recommend that the user obey international law
in accessing this directory.
Note also that the material made accessible below may be based
on a submitted version and thus differ in minor details from the published version.
Christoph Kessler