at.dms.kjc.sir.statespace
Class LinearRedundancy

java.lang.Object
  at.dms.kjc.sir.statespace.LinearRedundancy

public class LinearRedundancy
extends Object

A LinearRedundancy contains information about redundant computations that occur across filter invocations. LinearRedundancy is probably a misnomer as this class merely contains information that lets us identify redundant computation. Specifically, we keep a mapping between a computation tuple (eg [input,coefficient]) and "uses." A use of a computation tuple is definied as the number subsequenct work function after the current one that the tuple is re used.
More information might be gleaned from: http://cag.lcs.mit.edu/commit/papers/03/aalamb-meng-thesis.pdf
$Id: LinearRedundancy.java,v 1.4 2006/09/25 13:54:46 dimock Exp $

Constructor Summary

LinearRedundancy(LinearFilterRepresentation lfr)
Creates a new linear redundancy from the linear filter rep that is passed in (which has a matrix and a vector to describe computation.

Method Summary

void	addUse(LinearComputationTuple tuple, int use) add an entry for the specified execution use to this tuple
at.dms.kjc.sir.statespace.LinearRedundancy.RedundancyStatistics	calculateRedundancyStatistics() Calculate redundancy statistics.
String	calculateRedundancyString() Returns a number between zero and one that represents the amount of redundant computation that this LinearRedundancy does.
static int	divCeiling(int a, int b) Gets the ceiling of the division of two integers.
HashMap<LinearComputationTuple,LinkedList>	getTuplesToUses() Accessor into the internal tuples to uses map.
String	getTupleString() Returns a string version of the tuple -> list mapping.
String	makeShortRedundancyString() Generates a string of the form: totalOriginalTuples:reusedTuples|crossFiringTuples reused pct:subsequent reused pct)
String	toString() Make a nice human readable string for this LinearRedundancy.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

LinearRedundancy

public LinearRedundancy(LinearFilterRepresentation lfr)

Creates a new linear redundancy from the linear filter rep that is passed in (which has a matrix and a vector to describe computation. By creating a LinearRedundancy, we run the actual redundancy analysis.
The overall plan for calculating all of the mappings that we need is to realize that any tuple can only be used in up to ceil(peek/pop) filter firings. Therefore, we iterate that many times, adding all of the necessary tuples.

Method Detail

addUse

public void addUse(LinearComputationTuple tuple,
                   int use)

add an entry for the specified execution use to this tuple

getTuplesToUses

public HashMap<LinearComputationTuple,LinkedList> getTuplesToUses()

Accessor into the internal tuples to uses map. Sure this violates encapsulation, but what are you going to do? tuplesToUses maps LinearComputationTuples to lists of Integers, which represent the execution of the work function after the current one that the tuple is used in.

toString

public String toString()

Make a nice human readable string for this LinearRedundancy.

Overrides:

toString in class Object

calculateRedundancyStatistics

public at.dms.kjc.sir.statespace.LinearRedundancy.RedundancyStatistics calculateRedundancyStatistics()

Calculate redundancy statistics.

makeShortRedundancyString

public String makeShortRedundancyString()

Generates a string of the form: totalOriginalTuples:reusedTuples|crossFiringTuples reused pct:subsequent reused pct)

calculateRedundancyString

public String calculateRedundancyString()

Returns a number between zero and one that represents the amount of redundant computation that this LinearRedundancy does. For now, we define the linear redundancy to be the number of tuples that are reused in subsequent firings over the total tuples used in the first iteration (eg size of the filter matrix minus the number of zero entries

getTupleString

public String getTupleString()

Returns a string version of the tuple -> list mapping. This is used for debugging.

divCeiling

public static int divCeiling(int a,
                             int b)

Gets the ceiling of the division of two integers. Eg divCeil(5,3) = ceil(5/3) = 2. This is the same code as is in sir.linear.transform.LinearTransform. Copied here so as to not induce a dependence between packages.