at.dms.kjc.spacetime
Class DuplicateBottleneck

java.lang.Object
  at.dms.kjc.spacetime.DuplicateBottleneck

public class DuplicateBottleneck
extends Object

This class holds various methods for extracting data parallelism from the stream graph. There are many experimental methods and there are not many comments.

Author:

mgordon

Constructor Summary

DuplicateBottleneck()

Method Summary

boolean	duplicateBottleneck(SIRStream str)
void	duplicateFilters(SIRStream str, int reps) Duplicate all the filters in the stream graph reps times.
static void	duplicateHeavyFilters(SIRStream str) An experimental method for exploiting data-parallelism.
void	percentStateless(SIRStream str) Print the percentage of work that is contained in stateless filters compared to the total work of the application.
SIRStream	smartDuplication(SIRStream str, int numCores) An experimental method for data-parallelization.
void	smarterDuplicate(SIRStream str, int tiles) Use the cousins algorithm specifying the number of tiles.
SIRStream	smarterDuplicateStreamline(SIRStream str, int numCores) Experimental method for extracting data-parallelism.

Methods inherited from class java.lang.Object

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

Constructor Detail

DuplicateBottleneck

public DuplicateBottleneck()

Method Detail

smarterDuplicateStreamline

public SIRStream smarterDuplicateStreamline(SIRStream str,
                                            int numCores)

Experimental method for extracting data-parallelism. It attempts to create load-balanced bins.

Parameters:

str - The stream graph

numCores - The number of processors we are targeting

Returns:

The modified str graph

duplicateFilters

public void duplicateFilters(SIRStream str,
                             int reps)

Duplicate all the filters in the stream graph reps times.

Parameters:

str - The original stream graph that we are going to munge.

reps - The number to times to duplicate.

smarterDuplicate

public void smarterDuplicate(SIRStream str,
                             int tiles)

Use the cousins algorithm specifying the number of tiles. Duplicate each data parallel (stateless) filter a number of times taking the task parallel work into account. See ASPLOS 06 paper for an explanation.

Parameters:

str - The stream graph

tiles - The number of cores of the target machine

percentStateless

public void percentStateless(SIRStream str)

Print the percentage of work that is contained in stateless filters compared to the total work of the application. Use the static work estimation to calculate the estimate.

Parameters:

str - The stream graph

smartDuplication

public SIRStream smartDuplication(SIRStream str,
                                  int numCores)

An experimental method for data-parallelization.

Parameters:

str - The stream graph

numCores - The number pf processors

Returns:

The modified stream graph.

duplicateHeavyFilters

public static void duplicateHeavyFilters(SIRStream str)

An experimental method for exploiting data-parallelism. Keep parallelizing the filter with the most work until we get close to the ideal work distribution for the target or the bottleneck is not data-parallel.

Parameters:

str - The stream graph.

duplicateBottleneck

public boolean duplicateBottleneck(SIRStream str)