Package at.dms.kjc.slicegraph

This package aims to supersede the SIR and flatgraph representations of the stream graph with a single representation that maintains all relevant information as well as slice information.

See:
Description

Class Summary

AdaptivePartitioner	Test for ASPLOS paper, no longer used.
DataFlowOrder	This class generates a data flow schedule of the slice graph (but does not handle feedbackloops).
Edge	An Edge connects two SliceNodes.
EdgeArrayList	Linked list of UnflatEdge[] used in transforming to Slice Graph representation.
EdgeList	Linked list of UnflatEdge used in transforming to Slice Graph representation.
FileInputContent	Predefined FilterContent for file input, expands to implement a FileReader.
FileOutputContent	Predefined FilterContent for file output, expands to implement a FileWriter.
FilterContent	Intended to reflect all the content of a filter needed by a backend.
FilterSliceNode	A SliceNode that references a FilterContent.
FlattenAndPartition	Convert SIR graph to Slice without synch removal.
FlattenGraph	Flatten graph with new synch removal.
InputContent	Predefined FilterContent for input.
InputSliceNode	Each Slice is started by an InputSlice Node that is either a joiner connecting several other slices, or a connection to a single other slice.
InterSliceEdge	This class represents an edge in the partitioned stream graph between slices.
IntList	Linked list of int.
OutputContent	Predefined FilterContent for output.
OutputSliceNode	Each slice is terminated by an OutputSliceNode that has single input (the last filter) and multiple outputs (to downstream slices through edges).
Partitioner	An abstract class that a slice parititoner will subclass from: It holds the partitioned stream graph.
PeekPopPushInHelper	This class will search for all communication expressions outside of the work function of a filter and return true if they exist.
PredefinedContent	Predefined FilterContent.
ProcElement	A processing element in the most general sense: CPU tile, GPU, I/O device, switch network.
SimplePartitioner	Partition the stream graph into slices where each slice is a pipeline of filters with an inputslicenode and an outputslicenode (each filter is represented as a filterslicenode).
SimpleSlice	A SimpleSlice is a Slice with exactly one FilterSliceNode.
Slice	Slice class models a slice (joiner, sequence of filters, splitter).
SliceNode	SliceNode's are a doubly-linked list with a parent pointer to a Slice.
SynchRemover	The new synch remover to replace Jasp's old synch remover in converting a SIR graph to a slice graph (not yet integrated and tested).
UnflatEdge	Intermediate file used in (super) synch removal.
UnflatFilter	Intermediate file used in (super) synch removal.
Util	A class with useful functions that span classes.

Package at.dms.kjc.slicegraph Description

This package aims to supersede the SIR and flatgraph representations of the stream graph with a single representation that maintains all relevant information as well as slice information. The package contains the slice data structures, but omits manipulation of the data structures in ways that are not general: in particular, software pipelining algorithms from ASPLOS'06 are not in this package,

Class notes for my edification:

• Slice defines a collection of SliceNodes, started with an InputSliceNode. For people used to the SIR representation, a slice can be thought of as a joiner (InputSliceNode), followed by a pipeline of filters (FilterSliceNode), followed by a splitter (OutputSliceNode).
• SliceNode abstract class with previous and next SliceNode's (internal connections within a slice) and with a parent Slice.
  • InputSliceNode manages an array of Edge's: "sources"
  • OutputSliceNode manages an array of arrays of Edge's: "dests"
  • FilterSliceNode contains FilterContent.
• Edge class gives connection between slices (actually between an InputSliceNode and an OutputSliceNode), and may be queried for type, number of items sent on edge at init, at priming, and steady state times. SliceNode's within a slice are connected as a simple doubly-linked list. (Note that the priming information for an edge is not calculated in the slicegraph package).
• FilterContent keeps information about a filter, including init and steady scheduling multiplicities, and information about linear (but not linear statespace) filters. You can construct a FilterContent from a SIRPhasedFilter, from a UnflatFilter (including a linear one), or by shallow copy from another FilterContent. The subclass PredefinedContent seems to exist only for "instanceof"
  • InputContent has a single subclass FileInputContent which remembers a file name, can be constructed from a SIRFileReader.
  • OutputContent has a single subclass FileOutputContent which remembers a file name, can be constructed from a SIRFileWriter, and allows a value to be set for expected number of outputs.
• FlattenGraph takes a SIRStream, a linear analyzer, and what appears to be init and steady state execution counts. It performs the linear analysis and synchronization removal. It can be queried to get top level UnflatFilters.
  • I have been told that FlattenGraph is soon to be obsoleted in favor of SynchRemover
• SynchRemover is not currently called from anywhere. Should be soon.
• Partitioner is an abstract class defining the partitioning of a graph to be an array of Slice's. It requires UnflatFilter's from FlattenGraph, a schedule, linear analyzer, work estimate, and a bound on the number of partitions to be created (which may be ignored by any particular implementation). A Partitioner can be queried for an array of at.dms.kjc.spacetime.Slice nodes.
  • FlattenAndPartition is used by spacetime for KjcOptions.nopartition. It uses old {at.dms.kjc.flatgraph.GraphFlattener} to flatten the graph, does not attempt synch removal, and partitions as one filter per slice.
  • AdaptivePartitioner is used by spacetime for KjcOptions.autoparams. It is undocumented, but apparently only works for 16-tile raw. Mike says: probably obsolete after being used for some testing for the ASPLOS'06 paper.
  • SimplePartitioner is used by spacetime as the default partitioner. Each slice should be a pipeline of FilterSliceNode's stared with one InputSliceNode and ending with one OutputSliceNode.
• EdgeList and EdgeArray, deal with structures of UnflatEdge which, along with UnflatFilter are used by FlattenGraph. The UnflatFilter contains a SIRFilter, which is presumably why it is "Unflat"
• PeekPopPushInHelper determines whether any functions other than the work function access the tape. It operates on both FilterContent and on SIRFilter.
• DataFlowOrder produces a list of Slices (Slices) in reverse depth-first order. It is referred to from a number of places in spacetime, but not from elsewhere in slicegraph. However, slicegraph is a good place for this general utility on slices.
• IntList primitive list implementation used in FlattenGraph.
• Util contains utility routines for the slice graph.

TODO: update when SynchRemover in place!