Package at.dms.kjc.flatgraph

FlatNode basics

See:
Description

Interface Summary

FlatVisitor	Visitor interface to a graph of FlatNodes.
FlatWeight	Interface for a private class used in FlatWeights.
StreamGraphVisitor	Visitor interface for static stream sub-graphs of a stream graph.

Class Summary

DataFlowTraversal	This class calculates a traversal of the graph where that guarantees that for each node n in the traversal, we have visited every node upstream of n.
DumpGraph	Dump a representation of the flat graph to a dot file to be used with dot (or dotty).
DumpSymbolicGraph	Dumps a symbolic representation of the flatgraph for interfacing to French collaborators for linear-programming scheduling algorithm.
FlatGraphToSIR	This class will convert the FlatGraph back to an SIR representation.
FlatNode	This class represents a node in the flattened graph.
FlatWeights	Need ability to itereate over FlatGraph edges that correspond with non-zero weight edges for splittes and joiners.
GraphFlattener	This class will create a graph of FlatNode that represents the underlying SIR graph of the application.
ScheduledStaticStreamGraph	A StaticStreamGraph represents a subgraph of the application's StreamGraph where communication within the SSG is over static rate channels.
ScheduledStreamGraph
SSGEdge	This class represents inter-SSG edges.
StaticStreamGraph	A representation of a portion of a FlatGraph where all comunication is static rate.
StreamGraph	A representation of a FlatGraph as a collection of StaticStreamGraph.
WorkSorted

Package at.dms.kjc.flatgraph Description

FlatNode basics

The flatgraph package contains classes to create and represent the SIR graph in a flat format with no containers (thus no hierarchy or structure). The flat graph is intimately tied to the SIR graph through the FlatNode.contents and / or FlatNode.oldContents fields. The constructed graph of FlatNodes, the "flat graph", will have one node for each SIRFilter, SIRSplitter, and SIRJoiner in the SIR graph (except when --sync is enabled), but there will exist no containers, FlatNodes directly connect to/from their downstream/upstream nodes.

We create a graph of FlatNodes that represents the underlying SIR graph of the application using GraphFlattener

Each SIROperator will be converted to a FlatNode by GraphFlattener: SIRFilter into a FlatNode with at most one input/one output, SIRSplitter into a multiple output/one input, SIRJoiner into multiple input/one output.

If --sync is enabled, it will attempt to coalesce multiple splitters or joiners into a single FlatNode.

Warning: In the presence of 0-weight edges in splitters or joiners, there will not be a 1-1 correspondence between offsets in the weights arrays of the splitters and joiners and the nodes vector in a FlatNode. Use the FlatWeights to iterate if you need weight information from a splitter / joiner and corresponding edge from a FlatNode.

Static-Rate Stream Sub-Graphs

The Stream Graph is a graph of static-rate stream subgraphs, "SSG"s. Each SSG is a single-input, single-output graph represented internally as a graph of FlatNode s. The Stream Graph is a graph of SSG's. Any original dynamic-rate edges in the original SIR graph are removed from the SSGs: They are remembered as SSGEdges. A dynamic rate edge is expected to occur only between filters, but there is as yet no graph transformation to ensure that this is the case. Filters connecting to a dynamic edge are given I/O rates of 0 for that edge, and a input / output type of Void for that edge. If there is more than one input (resp. output) filter with a disconnected from a dynamic edge, then the single input / single output property of the SSG is maintained by introducing a splitter (resp. joiner) with 0-weight edges.

Create a StreamGraph as

        StreamGraph streamGraph = new StreamGraph((new GraphFlattener(str)).top);
        streamGraph.createStaticStreamGraphs();

After using SSGs, you can recreate the SIR graph, or continue to use a FlatNode representation:

        str = streamGraph.recreateSIR();
        FlatNode strTop = streamGraph.getTopLevel().getTopLevel();

There is a visitor interface defined to visit SSGs: StreamGraph. There is a ScheduledStaticStreamGraph subclass of SSGs that will provide a map from FlatNode to Integer for a single-appearance schedule. (It turns out that SIROperator to Integer would have been better since the setTopLevelSIR operation a SSG re-creates all the FlatNodes and thus invalidates any previous scheduling information.)

The advantage of SSGs is that scheduling and partitioning do not need to be enhanced to deal with dynamic-rate edges. The disadvantage is in determining the quirks, and maintaining the SSG representation: it should eventually be discontinued in favor of enhancing the scheduler and partitioners to deal with dynamic-rate edges.