mapss.dif.csdf.sdf.mem
Class IntegratedFramework

java.lang.Object
  mapss.dif.csdf.sdf.mem.IntegratedFramework

public class IntegratedFramework
extends java.lang.Object

Integrated algorithm framework for data memory management. The management considers optimization problems of both capacity requirement and parallel data accesses. The processor architecture of dual homogeneous on-chip memory banks is considered here instead of arbitrary number of banks.

Caution: To get any optimal results, #runOptimization(int) MUST be called first.

Version:

$Id: IntegratedFramework.java 406 2007-05-10 14:27:07Z plishker $

Author:

Mingyung Ko

Field Summary

protected mocgraph.mapping.ToIntMapMapping	_bufferSizes SDF buffer sizes.
protected int[]	_capacities Optimal capacity requirement in every iteration.
protected int	_capacity With multiple schedules being examined, the best capacity requirement is saved to this variable in the invocation of _share().
protected ConflictGraph	_conflictGraph The conflict graph.
protected java.util.Map	_intersections Lifetime intersections of buffers.
protected java.util.List	_lexicalOrder The lexical order required in DPPO scheduling technique.
protected java.util.Collection	_newConflicts New (sharing) conflicts to add in the conflict graph.
protected int	_optimalIteration Iteration of the optimal results (bank capacity requirement).
protected boolean[]	_optimalParallelism Check whether the partitioning results in optimal parallelism.
protected int[]	_optimalSchedulers Optimal scheduling algorithms in every iteration.
protected mocgraph.sched.Schedule[]	_optimalSchedules Optimal schedules in every iteration.
protected java.lang.String[]	_partitionStrings Optimal bank assignments in every iteration.
protected int	_presentIteration The present iteration.
protected mocgraph.sched.Schedule	_schedule The optimal schedule leads to minimal capacity requirement.
protected java.util.List	_schedules Multiple schedules can be generated in the scheduling phase.
protected SDFGraph	_sdfGraph The SDF graph.
protected java.util.Collection	_sEdges0 Partitions of SDF edges associated with the conflict graph.
protected java.util.Collection	_sEdges1 Partitions of SDF edges associated with the conflict graph.
protected int	_stateVariableCost0 State variable cost according to the present bank assignment.
protected int	_stateVariableCost1 State variable cost according to the present bank assignment.

Constructor Summary

IntegratedFramework(ConflictGraph conflictGraph)
A constructor with a conflict graph.

Method Summary

protected void	_allocateArrays(int iterations) Allocate arrays for caching iterative results.
protected void	_cachePartitionResults() Cache some useful local partitioning results that will be referenced frequently.
protected java.util.Collection	_collectSharingConflicts() Collect sharing conflicts to add in the conflict graph.
protected void	_incorporateSharingConflicts(java.util.Collection conflicts) Incorporate sharing conflicts to the conflict graph.
void	_iterativeFramework(int iterations, int updateOption) The body of the iterative algorithm framework.
protected void	_partition() The data partitioning phase.
protected void	_schedule() The SDF scheduling phase.
protected void	_share() The physical memory space sharing phase for SDF buffers.
protected java.util.List	_shareResults(mocgraph.sched.Schedule schedule) Sharing results with the given schedule.
protected void	_wrapUpIteration(int updateOption) Wrap up the results got in the present iteration and prepare feedback to the next iteration.
int	optimalBankCapacity() The optimal (minimal) bank capacity requirement after running the given number of iterations.
java.lang.String	optimalPartitionString() The optimal partitioning (bank assignment) results after running the given number of iterations.
mocgraph.sched.Schedule	optimalSchedule() The optimal scheduling result (schedule) after running the given number of iterations.
void	runOptimization(int iterations, int updateOption) Run the optimization for the given number of iterations and the desired way to update information across iterations.
java.lang.String	toString() A complete description of the results.
java.lang.String	unOptimizedResults() Display of any un-optimized results.

Methods inherited from class java.lang.Object

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

Field Detail

_sdfGraph

protected SDFGraph _sdfGraph

The SDF graph.

_lexicalOrder

protected java.util.List _lexicalOrder

The lexical order required in DPPO scheduling technique.

_presentIteration

protected int _presentIteration

The present iteration.

_conflictGraph

protected ConflictGraph _conflictGraph

The conflict graph.

_schedule

protected mocgraph.sched.Schedule _schedule

The optimal schedule leads to minimal capacity requirement. It is updated in the invocation of _share().

_schedules

protected java.util.List _schedules

Multiple schedules can be generated in the scheduling phase.

_bufferSizes

protected mocgraph.mapping.ToIntMapMapping _bufferSizes

SDF buffer sizes.

_intersections

protected java.util.Map _intersections

Lifetime intersections of buffers.

_sEdges0

protected java.util.Collection _sEdges0

Partitions of SDF edges associated with the conflict graph.

_sEdges1

protected java.util.Collection _sEdges1

Partitions of SDF edges associated with the conflict graph.

_capacity

protected int _capacity

With multiple schedules being examined, the best capacity requirement is saved to this variable in the invocation of _share().

_stateVariableCost0

protected int _stateVariableCost0

State variable cost according to the present bank assignment.

_stateVariableCost1

protected int _stateVariableCost1

State variable cost according to the present bank assignment.

_newConflicts

protected java.util.Collection _newConflicts

New (sharing) conflicts to add in the conflict graph.

_optimalIteration

protected int _optimalIteration

Iteration of the optimal results (bank capacity requirement).

_capacities

protected int[] _capacities

Optimal capacity requirement in every iteration.

_partitionStrings

protected java.lang.String[] _partitionStrings

Optimal bank assignments in every iteration.

_optimalSchedules

protected mocgraph.sched.Schedule[] _optimalSchedules

Optimal schedules in every iteration.

_optimalSchedulers

protected int[] _optimalSchedulers

Optimal scheduling algorithms in every iteration.

_optimalParallelism

protected boolean[] _optimalParallelism

Check whether the partitioning results in optimal parallelism.

Constructor Detail

IntegratedFramework

public IntegratedFramework(ConflictGraph conflictGraph)

A constructor with a conflict graph.

Parameters:

conflictGraph - The conflict graph.

Method Detail

runOptimization

public void runOptimization(int iterations,
                            int updateOption)

Run the optimization for the given number of iterations and the desired way to update information across iterations. This method must be called before any other public methods.

Parameters:

iterations - The number of iterations.

updateOption - The iterative update option. The available options are: 0, no update; 1, add sharing conflicts; 2, consolidate shared buffers into single nodes.

optimalBankCapacity

public int optimalBankCapacity()

The optimal (minimal) bank capacity requirement after running the given number of iterations. Please call #runOptimization(int) first.

Returns:

The optimal bank capacity requirement.

optimalPartitionString

public java.lang.String optimalPartitionString()

The optimal partitioning (bank assignment) results after running the given number of iterations. Please call #runOptimization(int) first.

Returns:

The optimal partitioning results.

optimalSchedule

public mocgraph.sched.Schedule optimalSchedule()

The optimal scheduling result (schedule) after running the given number of iterations. Please call #runOptimization(int) first.

Returns:

The optimal schedule.

toString

public java.lang.String toString()

A complete description of the results.

Overrides:

toString in class java.lang.Object

Returns:

The results in String.

unOptimizedResults

public java.lang.String unOptimizedResults()

Display of any un-optimized results. This is useful in debugging.

Returns:

Un-optimized results expressed in text.

_iterativeFramework

public void _iterativeFramework(int iterations,
                                int updateOption)

The body of the iterative algorithm framework.

Parameters:

iterations - The number of iterations to run the optimization.

updateOption - The iterative update option. The available options are: 0, no update; 1, add sharing conflicts; 2, consolidate shared buffers into single nodes.

_partition

protected void _partition()

The data partitioning phase. Determine bank assignment for variables. Both the input and output are stored in _conflictGraph.

_schedule

protected void _schedule()

The SDF scheduling phase. Determine SDF buffer sizes via scheduling techniques. Multiple schedulers are employed to get best results. The input data includes _sdfGraph, _lexicalOrder, and probably a few partitioning results like _sEdges0 and _sEdges1. The output result is in _schedules.

Parameters:

presentIteration - The present iteration number.

_share

protected void _share()

The physical memory space sharing phase for SDF buffers. The input data includes _sdfGraph, _schedules, and _sEdges0, _sEdges1 (which can be induced from _conflictGraph). Output results are saved in _bufferSizes, _intersections, #_capacity0, and #_capacity1. Optimal results in the present iteration are also saved simultaneously. They are _capacities, , and _partitionStrings.

_cachePartitionResults

protected void _cachePartitionResults()

Cache some useful local partitioning results that will be referenced frequently. Examples are #cPart0, #cPart1, _sEdges0, _sEdges1, #_capacity0, and #_capacity1.

_shareResults

protected java.util.List _shareResults(mocgraph.sched.Schedule schedule)

Sharing results with the given schedule. The input data includes _sdfGraph and _sEdges0, _sEdges1 (which can be induced from _conflictGraph). Output results are saved in a List of bank capacity requirement (in Integer), SDF buffer sizes (in ToIntMapMapping), and SDF buffer lifetime intersections (in Map).

Parameters:

schedule - The schedule for lifetime analysis.

Returns:

The bank capacity requirement, SDF buffer sizes, and SDF buffer lifetime intersections.

_collectSharingConflicts

protected java.util.Collection _collectSharingConflicts()

Collect sharing conflicts to add in the conflict graph. This method requires _intersections as input.

Returns:

The sharing conflicts (in Collection) to add.

_allocateArrays

protected void _allocateArrays(int iterations)

Allocate arrays for caching iterative results.

Parameters:

iterations - The number of iterations.

_incorporateSharingConflicts

protected void _incorporateSharingConflicts(java.util.Collection conflicts)

Incorporate sharing conflicts to the conflict graph.

Parameters:

conflicts - The sharing conflicts in Collection.

_wrapUpIteration

protected void _wrapUpIteration(int updateOption)

Wrap up the results got in the present iteration and prepare feedback to the next iteration. The actions include: updating SDF buffer cost to the conflict graph, record the optimal capacity/schedule/partitions got in the present iteration, and the way to pass updated information to the next iteration.

Parameters:

updateOption - The iterative update option. The available options are: 0, no update; 1, add sharing conflicts; 2, consolidate shared buffers into single nodes.