at.dms.kjc.sir.lowering.partition
Class ManualPartition

java.lang.Object
  at.dms.kjc.sir.lowering.partition.ManualPartition

public class ManualPartition
extends Object

Represents an interface to the StreamIt compiler that allows the programmer to specify how the partitioning / load balancing is done. To use the interface, follow these steps: ------------------ 1. Run the StreamIt compiler once on the input file: strc MyInput.str This will produce a "numbered.dot" file which assigns a unique number to each filter and stream container in the graph. (You can view dot with "dotty numbered.dot" or by converting to postscript, "dot -Tps numbered.dot -o numbered.ps.) ------------------ 2. Start writing your own class that implements the following function: public static void manualPartition(SIRStream str) { ... } Let's say you wrote this in "MyPartitioner.java". ------------------ 3. Use the API in ManualPartition, given below, to implement your manualPartition function. The basic idea is that you can lookup any stream based on its number (which you get from the graph). This will give you back an SIRStream object. With these objects, you can do the following operations: - fusion - collapse a whole stream container into 1 - collapse only certain children of a given container - fission: split a filter into a splitjoin - refactoring - create / eliminate hierarchical pipelines or splitjoins - create / eliminate synchronization points in symmetrical splitjoins - partitioning - you can run our own greedy or dynamic-programming partitioner on a hierarchical unit, asking it to automatically fuse or fiss to a given number of tiles There is also a function "printGraph" for printing a new numbered graph, in case you want to check that your transformations are working as expected. This also lets you see the numbers assigned to newly-created streams. ------------------ 4. Run your manual partitioning with the following command line: strc -r4 -manual MyPartitioner MyFile.str This will call your MyPartitioner.manualPartition function using reflection. It will not do any automatic partitioning for the given stream. [This command line also targets a 4x4 Raw machine; you could target other configurations, too.] ------------------ EXAMPLES. We have implemented two examples in for our Beamformer benchmark, which is in the following directory of CVS: streams/apps/benchmarks/beamformer/streamit The files are called: MyPartition1.java MyPartition2.java The first one implements a simple partitioning in which each pipeline is fused, and then the width of a splitjoin is decreased from 4 to 2. The second one is more sophisticated: it adds a synchronization point, collapsing the top of the splitjoin from 12 to 1 and the bottom from 12 to 6.

Constructor Summary

ManualPartition()

Method Summary

static SIRPipeline	addHierarchicalChild(SIRPipeline pipe, int first, int last) Returns a new pipeline that is like 'pipe' but replaces children at indices first...last with a pipeline that contains those children.
static SIRPipeline	addHierarchicalChildren(SIRPipeline pipe, PartitionGroup partitions) Given a pipeline 'pipe' and a partitioning 'partition' of its children, returns a new pipeline that has all the elements of each partition factored into their own pipelines.
static SIRSplitJoin	addHierarchicalChildren(SIRSplitJoin sj, PartitionGroup partition) Given a splitjoin 'sj' and a partitioning 'partition' of its children, returns a new splitjoin with each partition factored into its own child splitjoin.
static SIRPipeline	addSyncPoints(SIRSplitJoin sj, PartitionGroup partitions) Given that all of the children of 'sj' are pipelines and that 'partition' describes a partitioning for such a pipeline, re-arrange 'sj' into a pipeline of several splitjoins, each of which has children corresponding to a segment of 'partition': | | .
static SIRStream	convertToPipeline(SIRSplitJoin sj) Tries to convert 'sj' into a pipeline.
static void	destroyArrays(SIRStream str) Attempts to break down arrays in all children of 'str' into local variables, and to remove array declarations that are unneeded.
static SIRStream	doit(SIRStream str) Invokes the "manualPartition" method in class specified by KjcOptions.manual.
static SIRSplitJoin	fission(SIRFilter filter, int reps) Splits 'filter' into a 'reps'-way splitjoin.
static SIRSplitJoin	fission(SIRFilter filter, int reps, int[] workRatio) Splits 'filter' into a 'reps'-way splitjoin, and divides work among the resulting filters according to 'workRatio'.
static SIRStream	fuse(SIRPipeline pipeline, PartitionGroup partitions) Fuses some components of a pipeline together.
static SIRStream	fuse(SIRSplitJoin splitjoin, PartitionGroup partitions) Fuses some components of a splitjoin together.
static SIRStream	fuse(SIRStream str) Fuses all of 'str' into a single filter.
static SIRStream	fusePipelinesOfFilters(SIRStream str) Fuses all adjacent filters whos parent is a pipeline.
static SIRStream	fusePipelinesOfStatelessFilters(SIRStream str) Fuses any two adjacent FILTERS in 'str' so long as: - the shared parent of the filter is a pipeline - the result of fusion will be stateless If a complete pipeline is fused, then it is treated as a single filter in considering fusion within the pipeline's parent.
static SIRStream	fusePipelinesOfStatelessStreams(SIRStream str) Fuses any two adjacent STREAMS in 'str' so long as: - the shared parent of the filter is a pipeline - the result of fusion will be stateless If a complete pipeline is fused, then it is treated as a single filter in considering fusion within the pipeline's parent.
static SIRStream	getStream(SIRStream str, int num) Returns stream contained within 'str' that has unique id number 'num'.
static SIRStream	getStream(SIRStream str, String name) Returns stream by given that is deep child of 'str'.
static SIRStream[]	getStreams(SIRStream str, String prefix) Returns set of all child streams of 'str' (including 'str', possibly) that have a name beginning with a given prefix.
static SIRStream[]	getStreamsContaining(SIRStream str, String subStr) Returns set of all child streams of 'str' (including 'str', possibly) that have a name that contains 'subStr'.
static boolean	isFissable(SIRFilter filter) Returns whether or not 'filter' is fissable by the StreamIt compiler.
static SIRStream	partition(SIRStream str, int targetTiles) Runs dynamic programming partitioner on 'str', aiming to reduce the number of tiles needed to 'targetTiles'.
static SIRStream	partitionGreedy(SIRStream str, int targetTiles) Runs greedy partitioner on 'str', aiming to reduce the number of tiles needed to 'targetTiles'.
static void	printGraph(SIRStream str, String filename) Outputs numbered dot graph for 'str', by name of 'filename'.dot.
static boolean	raiseSJChildren(SIRSplitJoin sj) Raises as many children of 'sj' as it can into 'sj'.
static boolean	removeMatchingSyncPoints(SIRPipeline pipe) Does the opposite transformation of 'addSyncPoints' above.
static boolean	removeSyncPoints(SIRPipeline pipe) Removes all synchronization points between child splitjoins in 'pipe'.
static void	unroll(SIRStream str, int limit) Performs loop unrolling up to 'limit' in all methods of all deep children within 'str'.

Methods inherited from class java.lang.Object

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

Constructor Detail

ManualPartition

public ManualPartition()

Method Detail

doit

public static SIRStream doit(SIRStream str)

Invokes the "manualPartition" method in class specified by KjcOptions.manual. To be called only by the compiler.

printGraph

public static void printGraph(SIRStream str,
                              String filename)

Outputs numbered dot graph for 'str', by name of 'filename'.dot.

getStream

public static SIRStream getStream(SIRStream str,
                                  int num)

Returns stream contained within 'str' that has unique id number 'num'. This is the ID number that appears in numbered graphs.

getStreams

public static SIRStream[] getStreams(SIRStream str,
                                     String prefix)

Returns set of all child streams of 'str' (including 'str', possibly) that have a name beginning with a given prefix.

getStreamsContaining

public static SIRStream[] getStreamsContaining(SIRStream str,
                                               String subStr)

Returns set of all child streams of 'str' (including 'str', possibly) that have a name that contains 'subStr'.

getStream

public static SIRStream getStream(SIRStream str,
                                  String name)

Returns stream by given that is deep child of 'str'. Returns null if no such stream exists.

partition

public static SIRStream partition(SIRStream str,
                                  int targetTiles)

Runs dynamic programming partitioner on 'str', aiming to reduce the number of tiles needed to 'targetTiles'.

partitionGreedy

public static SIRStream partitionGreedy(SIRStream str,
                                        int targetTiles)

Runs greedy partitioner on 'str', aiming to reduce the number of tiles needed to 'targetTiles'.

fuse

public static SIRStream fuse(SIRStream str)

Fuses all of 'str' into a single filter.

fuse

public static SIRStream fuse(SIRPipeline pipeline,
                             PartitionGroup partitions)

Fuses some components of a pipeline together. The components are specified according to a PartitionGroup, 'partitions'.

fuse

public static SIRStream fuse(SIRSplitJoin splitjoin,
                             PartitionGroup partitions)

Fuses some components of a splitjoin together. The components are specified according to a PartitionGroup, 'partitions'.

fusePipelinesOfStatelessFilters

public static SIRStream fusePipelinesOfStatelessFilters(SIRStream str)

Fuses any two adjacent FILTERS in 'str' so long as: - the shared parent of the filter is a pipeline - the result of fusion will be stateless If a complete pipeline is fused, then it is treated as a single filter in considering fusion within the pipeline's parent.

fusePipelinesOfStatelessStreams

public static SIRStream fusePipelinesOfStatelessStreams(SIRStream str)

Fuses any two adjacent STREAMS in 'str' so long as: - the shared parent of the filter is a pipeline - the result of fusion will be stateless If a complete pipeline is fused, then it is treated as a single filter in considering fusion within the pipeline's parent.

fusePipelinesOfFilters

public static SIRStream fusePipelinesOfFilters(SIRStream str)

Fuses all adjacent filters whos parent is a pipeline. If a complete pipeline is fused, then it is treated as a single filter in considering fusion within the pipeline's parent.

isFissable

public static boolean isFissable(SIRFilter filter)

Returns whether or not 'filter' is fissable by the StreamIt compiler. Currently, we can fiss only "stateless" filters that have no internal fields.

fission

public static SIRSplitJoin fission(SIRFilter filter,
                                   int reps)

Splits 'filter' into a 'reps'-way splitjoin. This is essentially converting 'filter' to operate in a data-parallel form. Requires that isFissable('filter') is true.

fission

public static SIRSplitJoin fission(SIRFilter filter,
                                   int reps,
                                   int[] workRatio)

Splits 'filter' into a 'reps'-way splitjoin, and divides work among the resulting filters according to 'workRatio'. For example, if workRatio = {1, 2}, then the second fission product will do twice as much work as the first fission product. Requires that isFissable('filter') is true.

addHierarchicalChild

public static SIRPipeline addHierarchicalChild(SIRPipeline pipe,
                                               int first,
                                               int last)

Returns a new pipeline that is like 'pipe' but replaces children at indices first...last with a pipeline that contains those children.

addHierarchicalChildren

public static SIRPipeline addHierarchicalChildren(SIRPipeline pipe,
                                                  PartitionGroup partitions)

Given a pipeline 'pipe' and a partitioning 'partition' of its children, returns a new pipeline that has all the elements of each partition factored into their own pipelines.

addHierarchicalChildren

public static SIRSplitJoin addHierarchicalChildren(SIRSplitJoin sj,
                                                   PartitionGroup partition)

Given a splitjoin 'sj' and a partitioning 'partition' of its children, returns a new splitjoin with each partition factored into its own child splitjoin.

addSyncPoints

public static SIRPipeline addSyncPoints(SIRSplitJoin sj,
                                        PartitionGroup partitions)

Given that all of the children of 'sj' are pipelines and that 'partition' describes a partitioning for such a pipeline, re-arrange 'sj' into a pipeline of several splitjoins, each of which has children corresponding to a segment of 'partition': | | . . / | \ / | \ | | | | | | | | | ===> \ | / | | | . \ | / / | \ . | | | | \ | / | .

removeSyncPoints

public static boolean removeSyncPoints(SIRPipeline pipe)

Removes all synchronization points between child splitjoins in 'pipe'. Note that this might INCREASE the tile count because more joiners are introduced into the graph. If this is not desired, use only removeMatchingSyncPoints (below). Note that this method MUTATES its argument.

removeMatchingSyncPoints

public static boolean removeMatchingSyncPoints(SIRPipeline pipe)

Does the opposite transformation of 'addSyncPoints' above. If any two adjacent children in 'pipe' are splitjoins where the weights of the upstream joiner exactly match the weights of the downstream joiner, then the splitjoins can be combined into a single splitjoin. If this is the case, then 'pipe' is mutated. This is intended only as a reverse routine for the above sync. addition. In particular, it doesn't deal with duplicate splitters or 1-way splitters, and it doesn't attempt to "duplicate" or "unroll" whole streams in order for synchronization to match up. This guarantees that the tile count is not increased by the procedure. Returns whether or not any change was made. Note that this method MUTATES its argument.

raiseSJChildren

public static boolean raiseSJChildren(SIRSplitJoin sj)

Raises as many children of 'sj' as it can into 'sj'. That is, if 'sj' contains some children that are also splitjoins, tries to promote the children's children into direct children of 'sj'. Attempts both duplicate splitters and roundrobin splitters. Note that this method MUTATES its argument.

convertToPipeline

public static SIRStream convertToPipeline(SIRSplitJoin sj)

Tries to convert 'sj' into a pipeline. If the operation is successful, mutates the parent of 'sj' (if any) in the stream graph to contain the pipeline and returns the new pipeline. Otherwise, does not change anything and returns the original splitjoin.

unroll

public static void unroll(SIRStream str,
                          int limit)

Performs loop unrolling up to 'limit' in all methods of all deep children within 'str'.

destroyArrays

public static void destroyArrays(SIRStream str)

Attempts to break down arrays in all children of 'str' into local variables, and to remove array declarations that are unneeded.