at.dms.kjc.spacetime
Class AnnealedLayout

java.lang.Object
  at.dms.kjc.common.SimulatedAnnealing
      at.dms.kjc.spacetime.AnnealedLayout

All Implemented Interfaces:

Layout<RawTile>

public class AnnealedLayout
extends SimulatedAnnealing
implements Layout<RawTile>

This class calculates the assignment of filters of slices to tiles of the Raw chip by using simulated annealing. At each annealing step, it selects a random slice and finds a new random tile assignment for the filters of the slice. The cost function is still in development and is changing frequently. See the asplos submission for more details.

Author:

mgordon

Field Summary

Fields inherited from class at.dms.kjc.common.SimulatedAnnealing

ANNEALITERATIONS, assignment, MAXTEMPITERATIONS, MINTEMPITERATIONS, TFACTR

Constructor Summary

AnnealedLayout(SpaceTimeSchedule spaceTime)
Create a new Annealed layout object that will assign filters of the slices of the slice graph of spaceTime to tiles of the Raw Chip.

Method Summary

void	dumpLayout()
RawTile	getComputeNode(SliceNode filter) Get the raw tile that was assigned to filter in the layout.
void	initialize() This method initalizes the simulated annealing algorithm.
void	initialPlacement() Create the initial assignment of filters of slices to tiles.
protected boolean	keepNewEqualMin() Decide if we should keep a configuration that has a cost that is EQUAL to the current minimum of the search.
boolean	otherSplitFiltersMapped(FilterSliceNode node, ComputeNode tile) Return true if other filters that this filter's upstream slice splits to are mapped to tile.
double	placementCost(boolean debug) Return the cost function evaluated on the current assignment.
void	printLayoutStats() Print some statistics to the screen for the layout.
void	run() Calculate the assignment of filters of slices to tiles.
void	setAssignment(HashMap newAssignment) Set the underlying assigment of FilterSliceNode's -> RawTiles to the newAssignment HashMap.
void	setComputeNode(SliceNode node, RawTile tile) Set the assignment of node to tile in the layout.
static double	standardDeviation(int[] vals) Calculate the standard deviation of the values in vals.
void	swapAssignment() This function will perturb the configuration by moving something around.
void	swapAssignmentLegal() perturb the configuration by finding a new layout for a single slice.

Methods inherited from class at.dms.kjc.common.SimulatedAnnealing

getRandom, setConstants, simAnnealAssign

Methods inherited from class java.lang.Object

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

Constructor Detail

AnnealedLayout

public AnnealedLayout(SpaceTimeSchedule spaceTime)

Create a new Annealed layout object that will assign filters of the slices of the slice graph of spaceTime to tiles of the Raw Chip.

Parameters:

spaceTime - The spaceTime compilation up till now.

Method Detail

run

public void run()

Calculate the assignment of filters of slices to tiles.

Specified by:

run in interface Layout<RawTile>

getComputeNode

public RawTile getComputeNode(SliceNode filter)

Get the raw tile that was assigned to filter in the layout. Must call run() first.

Specified by:

getComputeNode in interface Layout<RawTile>

Parameters:

filter - : the SliceNode to look up.

Returns:

the ComputeNode that should execute the SliceNode.

setAssignment

public void setAssignment(HashMap newAssignment)

Set the underlying assigment of FilterSliceNode's -> RawTiles to the newAssignment HashMap.

Specified by:

setAssignment in class SimulatedAnnealing

Parameters:

newAssignment - The assignment to use.

dumpLayout

public void dumpLayout()

printLayoutStats

public void printLayoutStats()

Print some statistics to the screen for the layout.

Overrides:

printLayoutStats in class SimulatedAnnealing

swapAssignment

public void swapAssignment()

This function will perturb the configuration by moving something around.

Specified by:

swapAssignment in class SimulatedAnnealing

swapAssignmentLegal

public void swapAssignmentLegal()

perturb the configuration by finding a new layout for a single slice.

initialPlacement

public void initialPlacement()

Create the initial assignment of filters of slices to tiles.

Specified by:

initialPlacement in class SimulatedAnnealing

setComputeNode

public void setComputeNode(SliceNode node,
                           RawTile tile)

Set the assignment of node to tile in the layout.

Specified by:

setComputeNode in interface Layout<RawTile>

Parameters:

node - The node that will be assigned to tile.

tile - The tile to assign node to.

keepNewEqualMin

protected boolean keepNewEqualMin()

Description copied from class: SimulatedAnnealing

Decide if we should keep a configuration that has a cost that is EQUAL to the current minimum of the search. By default, don't keep it. Override if you want other behavior.

Specified by:

keepNewEqualMin in class SimulatedAnnealing

Returns:

Should we set the min config to this config (they have the same cost).

placementCost

public double placementCost(boolean debug)

Return the cost function evaluated on the current assignment.

Specified by:

placementCost in class SimulatedAnnealing

Parameters:

debug - Might want to do some debugging...

Returns:

the cost function evaluated on the current assignment.

initialize

public void initialize()

This method initalizes the simulated annealing algorithm. It will setup the file reading and writing structures and determine which filters need to be assigned to tiles.

Specified by:

initialize in class SimulatedAnnealing

standardDeviation

public static double standardDeviation(int[] vals)

Calculate the standard deviation of the values in vals.

Parameters:

vals - An array of ints.

Returns:

The standard deviation of the values in

vals

.

otherSplitFiltersMapped

public boolean otherSplitFiltersMapped(FilterSliceNode node,
                                       ComputeNode tile)

Return true if other filters that this filter's upstream slice splits to are mapped to tile. Return false if it is ok to put this node on this tile because no other filters that share the split stream are mapped to this tile.

Parameters:

node -

tile -

Returns:

See method description.