Package at.dms.kjc.sir.linear

Provides analysis and optimization of linear portions of the stream graph.

See:
Description

Class Summary

ComplexNumber	This class represents a complex number in the Linear filter extraction framework.
FilterMatrix	A FilterMatrix represents a matrix for use in the linear filter analysis of StreamIt.
FilterVector	A FilterVector is, at its most basic level, a simple, one dimensional row vector.
LinearAnalyzer	The LinearAnalyzer visits all of the filters and structures in a StreamIt program.
LinearAtlasReplacer	This replacer works by calling the matrix multiply routines in the ATLAS package, which it assumes are installed in $ATLAS_HOME. $Id: LinearAtlasReplacer.java,v 1.7 2006/09/25 13:54:42 dimock Exp $
LinearComputationTuple	A LinearComputationTuple represents tuples of (input position, coefficent) (eg the terms that are calculated to produce linear output.) The input position is defined as follows: input position 0 is the input generated by peek(0); input position 1 is the input generated by peek(1) and so on.
LinearCost	This class represents the cost (variously defined) of computing the value of a linear filter representation.
LinearDiagonalReplacer	This replacer works well when the non-zero elements of the matrix form a strip or diagonal -- more specifically, when some contiguous elements in each column are non-zero.
LinearDirectReplacer	A LinearDirectReplacer replaces the contents of the work functions for linear filters (as determined by the linear filter analyzer) with an appripriate direct implementation (eg a bunch of push statements with the specified combination of input values.
LinearDot	This class extends the main StreamIt dot (graph) printer to annotate the dot graphs with linear analysis information.
LinearDotSimple	This is like LinearDot except that the node labels are only the names and not the IO rates.
LinearFilterRepresentation	A LinearFilterRepresentation represents the computations performed by a filter on its input values as a matrix and a vector.
LinearForm	A LinearForm is the representation of a variable inside the linear dataflow analysis.
LinearIndirectReplacer	A LinearIndirectReplacer replaces the contents of the work functions for linear filters (as determined by the linear filter analyzer) with a sparse matrix multiply, using indirection through an array (see makeLinearWork for example).
LinearPrinter	Control point for printing messages generated by the LinearAnalysis pass.
LinearRedundancy	A LinearRedundancy contains information about redundant computations that occur across filter invocations.
LinearRedundancyAnalyzer	The LinearRedundancyAnalyzer tries to determine redundant computations across the firings of filters.
LinearRedundancyReplacer	Generates replacement filter code using the information within a LinearRedundancyAnalyzer to generate filters with less computational requirements.
LinearReplacer	A LinearReplacer is the base class that all replacers that make use of linear information inherit from. $Id: LinearReplacer.java,v 1.23 2006/09/25 13:54:42 dimock Exp $

Exception Summary

NonLinearException

This exception is thrown when a filter is determined to be non-linear.

Package at.dms.kjc.sir.linear Description

Provides analysis and optimization of linear portions of the stream graph. A filter is linear if each of its outputs is a known affine combination of its inputs. This package automatically detects such filters by analyzing the code in their work functions. Linear filters can be optimized in two ways: first, by algebraically collapsing adjacent filters, and second, by converting filters to the frequency domain. Both of these transformations can remove a significant number of FLOPs from the overall computation. For the details of linear analysis, see this PLDI'03 paper or Andrew Lamb's M.Eng. thesis.

The main classes involved in the detection of linear filters are LinearAnalyzer (which operates at the stream level) and LinearFilterVisitor (which operates inside each work function). The linear representation itself is encapsulated by LinearFilterRepresentation, which uses FilterMatrix and FilterVector.

Once linear filters are detected, adjacent filters can be combined and simplified. The implementation of algebraic combination is contained in a sub-package: LinearTransformPipeline and LinearTransformSplitJoin.

The classes ending with "Replacer" generate code for the linear components. There are several different code generation strategies for the direct implementation of linear filters (as a matrix-vector multiply); those implementations are contained in this directory. One can also implement linear filters in the frequency domain; this code generation is done in the frequency sub-package.

Note that the best driver for linear optimizations is the LinearPartitioner, which applies a dynamic programming algorithm to determine which optimizations should be applied to various filters.

See Also:

at.dms.kjc.sir.lowering.partition.linear, at.dms.kjc.sir.linear.transform, at.dms.kjc.sir.linear.frequency, at.dms.kjc.sir.statespace