Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Data Specialization

Todd B. Knoblock and Erik Ruf

Abstract

Given a repeated computation, part of whose input context remains invariant across all repetitions, program staging improves performance by separating the computation into two phases. An early phase executes only once, performing computations depending only on invariant inputs, while a late phase repeatedly performs the remainder of the work given the varying inputs and the results of the early computations. Common staging techniques based on dynamic compilation statically construct an early phase that dynamically generates object code customized for a particular input context. In effect, the results of the invariant computations are encoded as the compiled code for the late phase. This paper describes an alternative approach in which the results of early computations are encoded as a data structure, allowing both the early and late phases to be generated statically. By avoiding dynamic code manipulation, we give up some optimization opportunities in exchange for significantly lower dynamic space/time overhead and reduced implementation complexity.

Details

Publication typeInproceedings
URLhttp://www.acm.org/
Pages11
NumberMSR-TR-96-04
InstitutionMicrosoft Research
PublisherAssociation for Computing Machinery, Inc.
> Publications > Data Specialization