next up previous
Next: Predicting Execution Frequencies Up: Optimizer Design Previous: Optimizer Design

Knapsack Model

For the following discussion, we define a generic type definition language. The language contains a set of scalar types such as integer or real types, and the following set of type constructors: (1) A structure defines a linear sequence of fields of usually different types. (2) A union defines alternatives between fields of usually different type. (3) An array defines a sequence of fields of the same type.

The generation of optimized presentation conversion routines starts from an intermediate representation of the interface definition. We define the syntax graph of an interface specification as a tuple {V, E} where V is the set of nodes in the syntax graph for which an optimization decision is required and E is a set of arcs representing the sequence in which the nodes occur in the interface specification.

A syntax graph contains two different classes of nodes: type definition nodes and field nodes. Each definition of a constructed type in the interface specification is mapped to a type definition node in the syntax graph. A type definition node is labeled by the type constructor of the type definition.

A field in a constructed type is mapped to a field node in the syntax graph. There are three different kinds of field nodes, which can be distinguished by a label. A field node can be a constructed type ( embedded type constructor label), a reference to a pre-defined scalar type (scalar reference label) or a reference to another type definition ( type reference label).

For formalizing the optimization problem, we define the following variables: tex2html_wrap387 is the total size of presentation conversion code before optimization, tex2html_wrap388 is the total size of presentation conversion code after optimization, tex2html_wrap389 is the total execution time of presentation conversion code before optimization for a given workload and tex2html_wrap390 is the total execution time of presentation conversion code after optimization for a given workload.

The objective of optimization is then to generate presentation conversion routines in a way that minimizes tex2html_wrap390 under the constraint that tex2html_wrap388 does not exceed a given maximal code size. We define:

With this, we have:


The size/speed trade-off occurring when generating optimized presentation conversion code can be expressed as a 0-1 Knapsack problem (Martello & Toth, 1990). For this, each type definition node i in the syntax graph is assigned a profit tex2html_wrap_inline449 and a weight tex2html_wrap_inline451 as follows:


Substituting these equations into the general definition of a Knapsack problem results in the following optimization problem:



subject to:


It can be assumed that both the profit and the weight are positive numbers. A negative profit value corresponds to an optimization that increases the execution time, which is impossible by definition. A negative weight corresponds to an optimization that does not increase the code size. This case occurs for example when very small functions are written inline, since the number of instructions required for function linkage is higher than the number of instructions in the function body.The author of a stub compiler should avoid this by using macros definitions rather than function definitions.

For solving the 0-1 Knapsack problem, we use an approximate algorithm. The advantage over exact algorithms is that it is easy to implement. Moreover, investing much effort into making the Knapsack solution found by the algorithm accurate seems inappropriate, given that the values for weights and profits are also only approximations (see below).

First, items are sorted by their profit/weight ratio or profit per unit weight, i.e. so that


Then, items are consecutively inserted into the Knapsack in the order of this list, until the first item s is encountered that does not fit.

We use a heuristic for improving this solution which is to continue going through the list items following the critical item and including each item that fits into the residual Knapsack capacity. This algorithm is known as Greedy algorithm for finding a solution to the Knapsack problem (Martello & Toth, 1990).

For solving the Knapsack problem, the stub compiler must have information on tex2html_wrap393 , tex2html_wrap394 , tex2html_wrap395 , tex2html_wrap396 and tex2html_wrap397 . All of these values can generally only be estimated. One reason for this is that the stub compiler generates code in an application programming language. Therefore, the tex2html_wrap393 , tex2html_wrap394 , tex2html_wrap395 , tex2html_wrap396 depend on the machine code generated by the application language compiler. Moreover, tex2html_wrap397 depends on the actual workload. Only estimates of this workload are available at the time the presentation conversion code is generated. The following two sections discuss how these parameters are estimated in our implementation.

next up previous
Next: Predicting Execution Frequencies Up: Optimizer Design Previous: Optimizer Design

Philipp Hoschka
Sun Oct 26 21:35:40 MET 1997