at.dms.kjc.flatgraph
Class FlatNode

java.lang.Object
  at.dms.kjc.flatgraph.FlatNode

public final class FlatNode
extends Object

This class represents a node in the flattened graph. It has incoming edges with associated weights and outgoing edges with associated weights. The edges point to other FlatNodes. A FlatNode is unlike a StreamIt filter; each node can have multiple input and output. However, this feature is current not utilized because GraphFlattener just converts each filter/splitter/joiner into a FlatNode, so that filter FlatNodes are single input/single output, splitter FlatNodes are single input/multiple output. The spacedynamic backend and the raw backend rely on this translation of the StreamIt Graph. For nodes with multiple output, duplicate round-robins have 1 as the output weight for all of their output arcs. One must use the type of the splitter in contents to see what type of splitter is used. @see #contents The same goes for the types of joiners although there are only round-robin joiners supported in StreamIt currently.

Author:

mgordon

Field Summary

SIROperator	contents The operator this node contains (either a splitter, joiner, or filter)
int	currentEdge the current outgoing edge we are connecting, all edges before this are connected, used during construction
int	currentIncoming the current inedges we are connecting, all edges before this are connected, used during construction
FlatNode[]	incoming The incoming edges of this FlatNode
int[]	incomingWeights The round robin weights of each incoming arc
int	inputs The number of inputs (number of input arcs
SIROperator	oldContents Used by synch removal to remember the old sir Operator
int	schedDivider Used by synch removal to calcuate the new multiplicity of this node
int	schedMult Used by synch removal to calcuate the new multiplicity of this node
int	ways The number of outputs (number of output arcs
int[]	weights The weights of each outgoing arc

Constructor Summary

FlatNode(SIROperator op)
Create a new FlatNode with op as the underlying SIROperator.

Method Summary

void	accept(FlatVisitor v, HashSet<FlatNode> set, boolean reset) Accept a FlatVisitor v, that will visit this node.
void	addEdges(FlatNode to) Add a outgoing edge from this node to to.
static void	addEdges(FlatNode from, FlatNode to) Add an edge between from to to.
void	addEdgeTo(FlatNode to) Add an edge at this FlatNode to to.
void	addIncomingFrom(FlatNode from) Add an incoming edge at this node from from.
FlatNode[]	getEdges()
SIRFilter	getFilter() If underlying SIROperator is an SIRFilter, return the SIRFilter, otherwise throw an exception.
int	getIncomingWay(FlatNode prev) Return the index into the incoming weights and edges structures that holds the edge with source prev.
int	getIncomingWeight(FlatNode prev) return The incoming weight that is associated with the incoming edge that connects from prev.
static int	getItemsPushed(FlatNode from, FlatNode to) Return the number of items pushed from *from* to *to* on each iteration of *from*.
String	getName() Return the name of the underlying SIROperator with the FlatNode's unique ID appended.
int	getPartialIncomingSum(int i) Get the partial sum of incoming weight 0 thru i - 1.
int	getPartialOutgoingSum(int i) Get partial sum of outgoing weights 0 thru i - 1.
int	getTotalIncomingWeights() Return the sum of the weights on the incoming edges.
int	getTotalOutgoingWeights() Return the sum of the weights of the outgoing edges.
int	getWay(FlatNode to) Return the index into the outgoing weights and edges structures that holds the edge to to.
int	getWeight(FlatNode to) Return the outgoing weight that is associated with the outgoing edge that points to to.
int	hashCode() Now uses uin to implement deterministic hashcode system.
boolean	isDuplicateSplitter() Return True if the underlying SIROperator is an SIRSplitter that is a duplicate splitter.
boolean	isFeedbackIncomingEdge(int i) Return True if the underlying SIROperator is a joiner and that joiner is directly contained in an SIRFeedbackLoop and the incoming edge at i is the feed-back path.
boolean	isFeedbackJoiner() Return True if the underlying SIROperator is a joiner and that joiner is directly contained in an SIRFeedbackLoop.
boolean	isFilter() Return True if the the underlying SIROperator is a SIRFilter.
boolean	isJoiner() Return True if the underlying SIROperator is an SIRJoiner
boolean	isNullJoiner()
boolean	isNullSplitter() Return true if this flat node is a null splitter.
boolean	isSplitter() Return True if the underlying SIROperator is an SIRSplitter
boolean	isTopFilter() Return True if the the underlying SIROperator is a SIRFilter and could be at the top of a program
double	joiningRatio(FlatNode in) Return the ratio items that gets joined from the node in.
void	removeBackEdge(FlatNode from) Remove the incoming edge to this Flatnode from from.
void	removeEdges() Remove all downstream edges this node.
void	removeForwardEdge(FlatNode to) Remove the outgoing edge to the Flatnode to.
void	removeIncoming() Remove all incoming edges at this node, but this does not remove the associated edges from the source nodes.
void	setEdge(int offset, FlatNode newEdge) Set an edge in the outgoing edges.
void	setEdges(FlatNode[] edges) Replace all of the outgoing edges.
double	splittingRatio(FlatNode out) Return the ratio of itms that gets split to the node out.
void	swapSplitterEdges() This function is called by GraphFlattener after GraphFlattener.createGraph(at.dms.kjc.sir.SIROperator) is called.
String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

contents

public SIROperator contents

The operator this node contains (either a splitter, joiner, or filter)

incoming

public FlatNode[] incoming

The incoming edges of this FlatNode

incomingWeights

public int[] incomingWeights

The round robin weights of each incoming arc

weights

public int[] weights

The weights of each outgoing arc

inputs

public int inputs

The number of inputs (number of input arcs

ways

public int ways

The number of outputs (number of output arcs

currentEdge

public int currentEdge

the current outgoing edge we are connecting, all edges before this are connected, used during construction

currentIncoming

public int currentIncoming

the current inedges we are connecting, all edges before this are connected, used during construction

schedMult

public int schedMult

Used by synch removal to calcuate the new multiplicity of this node

schedDivider

public int schedDivider

Used by synch removal to calcuate the new multiplicity of this node

oldContents

public SIROperator oldContents

Used by synch removal to remember the old sir Operator

Constructor Detail

FlatNode

public FlatNode(SIROperator op)

Create a new FlatNode with op as the underlying SIROperator. The incoming and outgoing edge structures are empty for splitters and joiners they are declared to be the correct size the weights arrays (for incoming and outgoing edges) are set from the underlying splitter or joiner. The connections between nodes must be explicitedly set. For filters everything is of size 0.

Parameters:

op - The SIROperator that this FlatNode represents.

Method Detail

removeEdges

public void removeEdges()

Remove all downstream edges this node.

removeIncoming

public void removeIncoming()

Remove all incoming edges at this node, but this does not remove the associated edges from the source nodes.

removeForwardEdge

public void removeForwardEdge(FlatNode to)

Remove the outgoing edge to the Flatnode to. This removes both the edge and its associated weight.

Parameters:

to - The FlatNode whose edge we want to remove.

splittingRatio

public double splittingRatio(FlatNode out)

Return the ratio of itms that gets split to the node out.

Parameters:

out - An outgoing node.

Returns:

The ratio.

joiningRatio

public double joiningRatio(FlatNode in)

Return the ratio items that gets joined from the node in.

Parameters:

in - An incoming node.

Returns:

The ratio.

removeBackEdge

public void removeBackEdge(FlatNode from)

Remove the incoming edge to this Flatnode from from. This removes both the edge and its associated weight.

Parameters:

from - The FlatNode whose edge we want to remove.

addEdges

public void addEdges(FlatNode to)

Add a outgoing edge from this node to to. Note: you must add to nodes in the order specified by the underlying SIROperator.

Parameters:

to - The node to connect to.

addEdges

public static void addEdges(FlatNode from,
                            FlatNode to)

Add an edge between from to to. So we add an edge at from to to, and at to that is from from. Note: you must add to nodes in the order specified by the underlying SIROperator.

Parameters:

from - The source node

to - The dest node

addEdgeTo

public void addEdgeTo(FlatNode to)

Add an edge at this FlatNode to to. Note: you must add to nodes in the order specified by the underlying SIROperator.

Parameters:

to - The new edge's destination.

addIncomingFrom

public void addIncomingFrom(FlatNode from)

Add an incoming edge at this node from from. Note: you must add to nodes in the order specified by the underlying SIROperator.

Parameters:

from - The source of the new edge.

swapSplitterEdges

public void swapSplitterEdges()

This function is called by GraphFlattener after GraphFlattener.createGraph(at.dms.kjc.sir.SIROperator) is called. It is called for each splitter of a feedback loop. GraphFlattener.createGraph(at.dms.kjc.sir.SIROperator) connects the outgoing edges of the splitter of a feedback in the reverse order and this swaps them.

accept

public void accept(FlatVisitor v,
                   HashSet<FlatNode> set,
                   boolean reset)

Accept a FlatVisitor v, that will visit this node. To visit, we call v's visitNode() method, and then we call the visitor on each of our downstream (outgoing) edges. Since this graph can have loops, we have to keep track of what we visited already. We keep the nodes that we have already visited in set and we will not visit a node of set.

Parameters:

v - The FlatVisitor to call.

set - The FlatNodes we have already visited.

reset - If true, reset set to be empty.

hashCode

public int hashCode()

Now uses uin to implement deterministic hashcode system. It has the added benefit that a FlatNode's identity isn't tied to it's inputs, ways, etc not changing ie now hashcode is synched with equals() and equality doesn't change just because ones ways, etc changes

Overrides:

hashCode in class Object

getName

public String getName()

Return the name of the underlying SIROperator with the FlatNode's unique ID appended.

Returns:

The name of the underlying SIROperator with the FlatNode's unique ID appended.

isFilter

public boolean isFilter()

Return True if the the underlying SIROperator is a SIRFilter.

Returns:

True if the the underlying SIROperator is a SIRFilter.

isTopFilter

public boolean isTopFilter()

Return True if the the underlying SIROperator is a SIRFilter and could be at the top of a program

Returns:

True if the the underlying SIROperator is a SIRFilter and the filter neither peeks nor pops.

isJoiner

public boolean isJoiner()

Return True if the underlying SIROperator is an SIRJoiner

Returns:

True if the underlying SIROperator is an SIRJoiner

isSplitter

public boolean isSplitter()

Return True if the underlying SIROperator is an SIRSplitter

Returns:

True if the underlying SIROperator is an SIRSplitter

isDuplicateSplitter

public boolean isDuplicateSplitter()

Return True if the underlying SIROperator is an SIRSplitter that is a duplicate splitter.

Returns:

True if the underlying SIROperator is an SIRSplitter that is a duplicate splitter.

isNullSplitter

public boolean isNullSplitter()

Return true if this flat node is a null splitter.

Returns:

true if this flat node is a null splitter.

isNullJoiner

public boolean isNullJoiner()

isFeedbackJoiner

public boolean isFeedbackJoiner()

Return True if the underlying SIROperator is a joiner and that joiner is directly contained in an SIRFeedbackLoop.

Returns:

True if the underlying SIROperator is a joiner and that joiner is directly contained in an SIRFeedbackLoop.

isFeedbackIncomingEdge

public boolean isFeedbackIncomingEdge(int i)

Return True if the underlying SIROperator is a joiner and that joiner is directly contained in an SIRFeedbackLoop and the incoming edge at i is the feed-back path.

Parameters:

int - i: the edge number.

Returns:

True if the underlying SIROperator is a joiner and that joiner is directly contained in an SIRFeedbackLoop and the incoming edge at i is the feed-back path.

toString

public String toString()

Overrides:

toString in class Object

See Also:

getName()

getTotalIncomingWeights

public int getTotalIncomingWeights()

Return the sum of the weights on the incoming edges.

Returns:

The sum of the weights on the incoming edges.

getTotalOutgoingWeights

public int getTotalOutgoingWeights()

Return the sum of the weights of the outgoing edges.

Returns:

The sum of the weights of the outgoing edges.

getPartialOutgoingSum

public int getPartialOutgoingSum(int i)

Get partial sum of outgoing weights 0 thru i - 1.

Returns:

partial sum of outgoing weights 0 thru i - 1.

getPartialIncomingSum

public int getPartialIncomingSum(int i)

Get the partial sum of incoming weight 0 thru i - 1.

Returns:

the partial sum of incoming weight 0 thru i - 1.

getIncomingWeight

public int getIncomingWeight(FlatNode prev)

return The incoming weight that is associated with the incoming edge that connects from prev.

Parameters:

prev - The source we are interested it.

Returns:

The incoming weight that is associated with the incoming edge that connects from prev.

getWeight

public int getWeight(FlatNode to)

Return the outgoing weight that is associated with the outgoing edge that points to to.

Parameters:

to -

Returns:

The outgoing weight that is associated with the outgoing edge that points to to.

getWay

public int getWay(FlatNode to)

Return the index into the outgoing weights and edges structures that holds the edge to to.

Parameters:

to - The dest of the edge.

Returns:

the index into the outgoing weights and edges structure that holds the edge to to.

getIncomingWay

public int getIncomingWay(FlatNode prev)

Return the index into the incoming weights and edges structures that holds the edge with source prev.

Parameters:

prev - The source of the edge.

Returns:

the index into the incoming weights and edges structures that holds the edge with source prev.

getFilter

public SIRFilter getFilter()

If underlying SIROperator is an SIRFilter, return the SIRFilter, otherwise throw an exception.

Returns:

The underlying SIRFilter.

getItemsPushed

public static int getItemsPushed(FlatNode from,
                                 FlatNode to)

Return the number of items pushed from *from* to *to* on each iteration of *from*. If *from* is a splitter take this into account.

Parameters:

from - : the node pushing the items

to - : the node receiving the pushed items

Returns:

the number of items pushed.

setEdges

public void setEdges(FlatNode[] edges)

Replace all of the outgoing edges.

Parameters:

the - array the edges to set.

setEdge

public void setEdge(int offset,
                    FlatNode newEdge)

Set an edge in the outgoing edges.

Parameters:

offset - edge number (0 based)

newEdge - edge to replace existing edge at the offset.

getEdges

public FlatNode[] getEdges()

Returns:

the outgoing edges.