Package at.dms.kjc.sir.statespace

Provides analysis and optimization of linear statespace 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.
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.
LinearDirectReplacer	A LinearDirectReplacer replaces the contents of the work functions for linear filters (as determined by the linear filter analyzer) with an appropriate 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 four matrices.
LinearForm	A LinearForm is the representation of a variable inside the linear dataflow analysis.
LinearOptimizer
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.
LinearReplacer	A LinearReplacer is the base class that all replacers that make use of linear information inherit from. $Id: LinearReplacer.java,v 1.5 2006/09/25 13:54:46 dimock Exp $

Exception Summary

NonLinearException

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

Package at.dms.kjc.sir.statespace Description

Provides analysis and optimization of linear statespace portions of the stream graph. A linear statespace filter is just like a linear filter, except that it may also contain a number of internal states. On each execution step, the filter outputs a linear combination of its inputs and the states; furthermore, the states are updated to be a linear combination of the inputs and the previous states.

This package automatically detects linear statespace filters (or statespace filters for short) by analyzing the code in their work functions. Statespace filters can be optimized in three ways: first, by algebraically collapsing adjacent filters; second, by minimizing the number of states; and third, by reducing the number of system parameters. All of these transformations can reduce the number of FLOPs in the overall computation. For the details of statespace analysis, see this CASES'05 paper or Sitij Agrawal's M.Eng. thesis.

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

The implementation of algebraic combination is contained in a sub-package: LinearTransformPipeline, LinearTransformSplitJoin, and LinearTransformFeedback. The state minimization and parameter reduction optimizations are implemented in LinearOptimizer, while the LinearDirectReplacer class provides the only code generation mechanism for statespace filters.

Unlike with plain linear optimizations, there does not yet exist a partitioner that automatically determines which statespace optimizations are the most profitable to apply to a given stream graph.

Note that some files in this package may be complete vestigial artifacts from copying over the linear package. For example, the LinearRedundancyAnalyzer and LinearRedundancy classes should be ignored (they could be removed, if incidental dependences from other files were taken care of).

See Also:

at.dms.kjc.sir.linear, at.dms.kjc.sir.statespace.transform