Package at.dms.kjc.sir.lowering.partition.linear

Applies linear optimizations to the stream graph, using a dynamic programming algorithm to calculate the most profitable set of transformations.

See:
Description

Class Summary

LinearPartitioner

Package at.dms.kjc.sir.lowering.partition.linear Description

Applies linear optimizations to the stream graph, using a dynamic programming algorithm to calculate the most profitable set of transformations. The transformations considered are algebraic combination of linear nodes and translation of linear nodes to the frequency domain. A partitioning algorithm is needed because these transformations are not always profitable; furthermore, non-neighboring filters may need to be considered at once to gauge profitability.

The linear partitioning algorithm is described in Section 6.2 of this PLDI'03 paper.

The general strategy behind the algorithm is to calculate, for each hierarchical stream, the estimated runtime if that stream was algebraically collapsed, translated to the frequency domain, or left alone. If this information is available for a set of sub-streams, then a parent stream can recursively calculate these estimates as a composition of the child estimates.

The dynamic programming partitioner uses rectangles as a uniform representation of streams. An n-element pipeline is a rectangle that has a width of 1 and a height of n, while a splitjoin of n filters is a rectangle with a width of n and a height of 1. Splitjoins containing pipelines are represented as a single rectangle. Using this representation, the partitioning algorithm can perform a linear optimization on any sub-rectangle, and implement the transformation using a hierarchical refactoring of the splitjoin.

To support the rectangle abstraction, all filters and streams are wrapped in configurations. The basic configuration is LDPConfig, and there is a subclass for each stream type. The standard dynamic programming methods of get() (to calculate the partitioning costs for a sub-stream) and traceback() (to reconstruct the minimal-cost partitioning) are implemented by each type of configuration. The heart of the algorithm is in LDPConfigContainer, which implements these two functions for arbitrary rectangles.

The high-level interface for the package is LinearPartitioner, which contains constants and configuration-building code.

See Also:

at.dms.kjc.sir.linear