at.dms.kjc.slicegraph
Class Partitioner

java.lang.Object
  at.dms.kjc.slicegraph.Partitioner

Direct Known Subclasses:

AdaptivePartitioner, FlattenAndPartition, SimplePartitioner

public abstract class Partitioner
extends Object

An abstract class that a slice parititoner will subclass from: It holds the partitioned stream graph. Partitioning maps filters to slices. This is normally not useful since most back ends will assume one filter per slice, but is sometimes used in at.dms.kjc.spacetime. Partitioning also converts a SIR graph to a slice graph.

Author:

mgordon

Field Summary

protected HashMap<Slice,FilterSliceNode>	bottleNeckFilter This hashmap maps a Slice to the FilterSliceNode that has the most work;
protected HashMap[]	exeCounts
protected HashMap<FilterSliceNode,Integer>	filterOccupancy This hashmap store the filters work plus any blocking that is caused by the pipeline imbalance of the slice.
protected HashMap<FilterSliceNode,Integer>	filterStartupCost The startup cost of a filter when starting a slice
protected HashMap<SIRFilter,Integer>	genIdWorks
Slice[]	io
protected LinearAnalyzer	lfa
protected int	maxPartitions
protected HashMap<SIRFilter,FilterContent>	sirToContent
protected HashMap<Slice,Integer>	sliceBNWork
protected Slice[]	sliceGraph
protected int	steadyMult
protected UnflatFilter[]	topFilters
protected Slice[]	topSlices
protected WorkEstimate	work
protected HashMap<FilterContent,Integer>	workEstimation

Constructor Summary

Partitioner(UnflatFilter[] topFilters, HashMap[] exeCounts, LinearAnalyzer lfa, WorkEstimate work, int maxPartitions)
Create a Partitioner.

Method Summary

void	addFilterToSlice(FilterSliceNode node, Slice slice) Update all the necesary state to add node to slice.
void	calculateWorkStats()
boolean	containsSlice(Slice slice) Does the the slice graph contain slice (perform a simple linear search).
void	createPredefinedContent() Force creation of kopi methods and fields for predefined filters.
void	dumpGraph(String filename)
void	ensureSimpleSlices() Make sure that all the Slices are SimpleSlices.
FilterContent	getContent(SIRFilter f)
protected FilterContent	getFilterContent(UnflatFilter f)
int	getFilterOccupancy(FilterSliceNode filter) This hashmap store the filters work plus any blocking that is caused by the pipeline imbalance of the slice.
int	getFilterStartupCost(FilterSliceNode node)
int	getFilterWork(FilterSliceNode node)
int	getFilterWorkSteadyMult(FilterSliceNode node)
protected Slice[]	getNext(Slice slice)
FilterSliceNode	getSliceBNFilter(Slice slice)
int	getSliceBNWork(Slice slice)
Slice[]	getSliceGraph() Get all slices
Slice[]	getTopSlices() Get just top level slices in the slice graph.
protected int	getWorkEstimate(FilterContent fc)
int	getWorkEstOneFiring(FilterSliceNode node) The cost of 1 firing of the filter, to be run after the steady multiplier has been accounted for in the steady multiplicity of each filter content.
boolean	isIO(Slice slice) Check for I/O in slice
abstract Slice[]	partition() Partition the stream graph into slices (slices) and return the slices.
void	setSliceGraphNewIds(Slice[] slices) Set the slice graph to slices, where the only difference between the previous slice graph and the new slice graph is the addition of identity slices (meaning slices with only an identities filter).
protected String	sliceName(Slice slice)

Methods inherited from class java.lang.Object

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

Field Detail

sliceBNWork

protected HashMap<Slice,Integer> sliceBNWork

filterStartupCost

protected HashMap<FilterSliceNode,Integer> filterStartupCost

The startup cost of a filter when starting a slice

sliceGraph

protected Slice[] sliceGraph

maxPartitions

protected int maxPartitions

topFilters

protected UnflatFilter[] topFilters

exeCounts

protected HashMap[] exeCounts

lfa

protected LinearAnalyzer lfa

work

protected WorkEstimate work

topSlices

protected Slice[] topSlices

genIdWorks

protected HashMap<SIRFilter,Integer> genIdWorks

bottleNeckFilter

protected HashMap<Slice,FilterSliceNode> bottleNeckFilter

This hashmap maps a Slice to the FilterSliceNode that has the most work;

filterOccupancy

protected HashMap<FilterSliceNode,Integer> filterOccupancy

This hashmap store the filters work plus any blocking that is caused by the pipeline imbalance of the slice.

io

public Slice[] io

workEstimation

protected HashMap<FilterContent,Integer> workEstimation

steadyMult

protected int steadyMult

sirToContent

protected HashMap<SIRFilter,FilterContent> sirToContent

Constructor Detail

Partitioner

public Partitioner(UnflatFilter[] topFilters,
                   HashMap[] exeCounts,
                   LinearAnalyzer lfa,
                   WorkEstimate work,
                   int maxPartitions)

Create a Partitioner. The number of partitions may be limited by maxPartitions, but some implementations ignore maxPartitions.

Parameters:

topFilters - from FlattenGraph

exeCounts - a schedule

lfa - a linearAnalyzer to convert filters to linear form if appropriate.

work - a work estimate, see at.dms.kjc.sir.lowering.partition, updeted if filters are added to a slice.

maxPartitions - if non-zero, a maximum number of partitions to create

Method Detail

partition

public abstract Slice[] partition()

Partition the stream graph into slices (slices) and return the slices.

Returns:

The slices (slices) of the partitioned graph.

isIO

public boolean isIO(Slice slice)

Check for I/O in slice

Parameters:

slice -

Returns:

Return true if this slice is an IO slice (file reader/writer).

getSliceGraph

public Slice[] getSliceGraph()

Get all slices

Returns:

All the slices of the slice graph.

getTopSlices

public Slice[] getTopSlices()

Get just top level slices in the slice graph.

Returns:

top level slices

containsSlice

public boolean containsSlice(Slice slice)

Does the the slice graph contain slice (perform a simple linear search).

Parameters:

slice - The slice to query.

Returns:

True if the slice graph contains slice.

addFilterToSlice

public void addFilterToSlice(FilterSliceNode node,
                             Slice slice)

Update all the necesary state to add node to slice.

Parameters:

node - The node to add.

slice - The slice to add the node to.

setSliceGraphNewIds

public void setSliceGraphNewIds(Slice[] slices)

Set the slice graph to slices, where the only difference between the previous slice graph and the new slice graph is the addition of identity slices (meaning slices with only an identities filter).

Parameters:

slices - The new slice graph.

getFilterWork

public int getFilterWork(FilterSliceNode node)

Parameters:

node - The Filter

Returns:

The work estimation for the filter slice node for one steady-state mult of the filter.

getFilterWorkSteadyMult

public int getFilterWorkSteadyMult(FilterSliceNode node)

Parameters:

node -

Returns:

The work estimation for the filter for one steady-state multiplied by the steady-state multiplier

getSliceBNWork

public int getSliceBNWork(Slice slice)

Parameters:

slice -

Returns:

The work estimation for the slice (the estimation for the filter that does the most work for one steady-state mult of the filter multipled by the steady state multiplier.

getFilterOccupancy

public int getFilterOccupancy(FilterSliceNode filter)

This hashmap store the filters work plus any blocking that is caused by the pipeline imbalance of the slice.

getSliceBNFilter

public FilterSliceNode getSliceBNFilter(Slice slice)

Parameters:

slice -

Returns:

Return the filter of slice that does the most work.

calculateWorkStats

public void calculateWorkStats()

dumpGraph

public void dumpGraph(String filename)

getNext

protected Slice[] getNext(Slice slice)

getFilterContent

protected FilterContent getFilterContent(UnflatFilter f)

getContent

public FilterContent getContent(SIRFilter f)

sliceName

protected String sliceName(Slice slice)

getWorkEstimate

protected int getWorkEstimate(FilterContent fc)

getWorkEstOneFiring

public int getWorkEstOneFiring(FilterSliceNode node)

The cost of 1 firing of the filter, to be run after the steady multiplier has been accounted for in the steady multiplicity of each filter content.

Parameters:

node -

Returns:

getFilterStartupCost

public int getFilterStartupCost(FilterSliceNode node)

Parameters:

node -

Returns:

The startup cost for

node

ensureSimpleSlices

public void ensureSimpleSlices()

Make sure that all the Slices are SimpleSlices.

createPredefinedContent

public void createPredefinedContent()

Force creation of kopi methods and fields for predefined filters.