Package at.dms.kjc.sir.lowering.partition

Provides algorithms for adjusting the granularity of the stream graph to improve load balancing or optimization potential.

See:
Description

Class Summary

FissionTransform	Represents a fission of a filter in a stream graph.
FreqReplaceTransform	FreqReplace transform on a stream graph.
FusionTransform	Represents a fusion of children in a stream graph.
GreedierPartitioner	Greedier partitioner that can switch back and forth between fissing and fusing depending on what's more appropriate.
GreedyPartitioner
HorizontalCutTransform	Horizontal cut transform on a stream graph.
IdempotentTransform	Idempotent transform on a stream graph.
IdentityTransform	Identity transform on a stream graph.
ILPPartitioner
LinearReplaceTransform	LinearReplace transform on a stream graph.
ListPartitioner	This is a partitioner that keeps a canonical list of underlying nodes to help with partitioning.
ManualPartition	Represents an interface to the StreamIt compiler that allows the programmer to specify how the partitioning / load balancing is done.
PartitionDot	This class extends the main streamit dot printer to annotate the dot graphs with partitioning information.
Partitioner
PartitionGroup	This represents a partitioning of the children of a single SIR Container.
PartitionRecord	This is just a structure for recording what has been assigned to a given partition.
PartitionUtil
RecordingStreamVisitor	Records all filters, splitters, and joiners in a given stream into a partition record.
RefactorPipeline	This class is for refactoring pipelines.
RefactorSplitJoin
RemoveSyncTransform	Removes *matching* synchronization in this pipeline.
SJToPipe
StreamTransform	This represents a symbolic transformation on a stream graph.
VerticalCutTransform	Vertical cut transform on a stream graph.
WorkEstimate	Provides a means for estimating the amount of work in a stream graph.
WorkList	A wrapper for a linked list to save ourself a lot of casting with work entries.

Package at.dms.kjc.sir.lowering.partition Description

Provides algorithms for adjusting the granularity of the stream graph to improve load balancing or optimization potential. Also provides estimation of the work requirements of filters, as well as refactoring routines that adjust the synchronization points in a stream graph. The high-level partitioners can be broadly categorized as those that improve load balancing and those that optimize other metrics.

The partitioners oriented towards load balancing include:

• DynamicProgPartitioner. This partitioner (currently the default used by strc) uses a dynamic programming algorithm to calculate the most load-balanced refactoring and fusion/fission of filters. It is described in a yet-unpublished draft (contact thies@alum.mit.edu) and is similar to the dynamic programming partitioner described in this PLDI'03 paper (see Section 6.2).

• GreedyPartitioner. One of the first and still most robust partitioners, it iteratively identifies the stream container containing the least amount of work, and collapses that container into a single filter.

• GreedierPartitioner. This partitioner is faster and more fair than the greedy partitioner. Rather than collapsing the container with the smallest amount of work, it iteratively collapses the pair of adjacent filters that have the smallest amount of work.

• ILPPartitioner. This partitioner is obsolete. It translated the load balancing problem into a linear program, but proved too slow to be practical.

Partitioners that have other optimization metrics include:

• LinearPartitioner. As part of linear analysis and optimization, this partitioner decides which filters should be algebraically combined or translated to the frequency domain. As it also utilizes a dynamic programming algorithm, it can be considered a "dynamic programming partitioner". For details, see Section 6.2 of this PLDI'03 paper.

• CachePartitioner. This partitioner greedily fuses filters based on cache constraints (instruction size and data size). It implements the "cache aware fusion" algorithm described in Section 4.2 of this LCTES'05 paper.

• ManualPartition. This partitioner provides an interface for programmers to manually drive the partitioning process. It can apply both to load balancing, and other transformations.

Several of these inherit from ListPartitioner to reuse some common code.

The other files in this package fall under a few categories:

• All files ending with Transform (inheriting from StreamTransform) represent a symbolic transformation to be applied to a stream graph. These are generated as output from any partitioner based on dynamic programming, because it is simpler (and easier to debug) than mutating the stream graph in place.

• The WorkEstimate class (and helper files Work*) provides an estimation of the number of cycles needed to execute a filter.

• The RefactorPipeline, RefactorSplitJoin, and SJToPipe classes perform refactoring of hierarchical stream graphs. As the fusion passes generally operate on a single stream container at a time, the location of container boundaries often needs to adjusted to perform various partitionings. Refactoring is done by the dynamic programming partitioners.

See Also:

at.dms.kjc.sir.lowering.partition.dynamicprog, at.dms.kjc.sir.lowering.partition.cache, at.dms.kjc.sir.lowering.partition.linear