mapss.dif.csdf.sdf.mem
Class BufferUtilities

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

public class BufferUtilities
extends java.lang.Object

Utilities for buffer related computation. This class is just a collection of static methods and should not be allocated as objects.

Version:

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

Author:

Mingyung Ko

Method Summary

static int	bufferCost(java.util.Collection edgeCollection, SDFGraph graph, mocgraph.sched.Schedule schedule) Compute buffer cost for the SDF edge collection and the schedule.
static int	bufferCost(SDFGraph graph, mocgraph.sched.Schedule schedule) Compute total buffer cost for an SDF graph and a schedule.
static java.util.Map	bufferIntersections(SDFGraph graph, mocgraph.sched.Schedule schedule) Build buffer intersections (lifetime overlaps).
static java.lang.String	bufferIntersectionsToString(SDFGraph graph, java.util.Map intersectionsMap) Display buffer lifetime overlaps in text.
static java.lang.String	bufferIntersectionsToString(SDFGraph graph, mocgraph.sched.Schedule schedule) Display buffer lifetime overlaps in text.
static int	bufferSharingLowerBound(SDFGraph graph, mocgraph.sched.Schedule schedule) Get the lower bound for buffer sharing cost.
static int[]	bufferSize(SDFGraph graph, mocgraph.sched.Schedule schedule) Compute buffer size for a given SDF graph and schedule.
static java.util.Map	bufferSizeMap(SDFGraph graph, mocgraph.sched.Schedule schedule) Compute buffer size for a given SDF graph and schedule.
static mocgraph.mapping.ToIntMapMapping	bufferSizeMapping(SDFGraph graph, mocgraph.sched.Schedule schedule) Compute buffer size for a given SDF graph and schedule.
static boolean	verifyBufferIntersections(SDFGraph graph, mocgraph.sched.Schedule schedule, java.util.Map intersectionsMap) Verify the correctness of the given buffer intersections.

Methods inherited from class java.lang.Object

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

Method Detail

bufferCost

public static int bufferCost(SDFGraph graph,
                             mocgraph.sched.Schedule schedule)

Compute total buffer cost for an SDF graph and a schedule. This is a universal, though naive, implementation. Users may wish to override this with an efficient one.

Parameters:

graph - The given SDF graph.

schedule - The given schedule.

Returns:

Total buffer cost.

bufferCost

public static int bufferCost(java.util.Collection edgeCollection,
                             SDFGraph graph,
                             mocgraph.sched.Schedule schedule)

Compute buffer cost for the SDF edge collection and the schedule. This is a universal, though naive, implementation. Users may wish to override this with an efficient one.

Parameters:

edgeCollection - The collection of edges.

graph - The given SDF graph.

schedule - The given schedule.

Returns:

Buffer cost for the edge collection.

bufferIntersectionsToString

public static java.lang.String bufferIntersectionsToString(SDFGraph graph,
                                                           java.util.Map intersectionsMap)

Display buffer lifetime overlaps in text. The method is primary for debugging purpose.

Parameters:

graph - The given SDF graph.

intersectionsMap - The given buffer intersections.

Returns:

The buffer lifetime overlaps in text.

bufferIntersectionsToString

public static java.lang.String bufferIntersectionsToString(SDFGraph graph,
                                                           mocgraph.sched.Schedule schedule)

Display buffer lifetime overlaps in text. The method is primary for debugging purpose.

Parameters:

graph - The given SDF graph.

schedule - The given schedule.

Returns:

The buffer lifetime overlaps in text.

bufferIntersections

public static java.util.Map bufferIntersections(SDFGraph graph,
                                                mocgraph.sched.Schedule schedule)

Build buffer intersections (lifetime overlaps). Buffer intersections are used in buffer sharing. The intersections are saved in the form of Map of Sets. Each map entry is an edge to a set of edges (excluding itself) intersecting with it. The code here is naive but universal for intersection calculation. Users may wish to override this with an efficient one.

Parameters:

graph - The given SDF graph.

schedule - The given schedule.

Returns:

The buffer intersections in the form of Map of Sets.

bufferSharingLowerBound

public static int bufferSharingLowerBound(SDFGraph graph,
                                          mocgraph.sched.Schedule schedule)

Get the lower bound for buffer sharing cost. Sharing cost means the total memory space needed for shared buffers. This is a universal, though naive, implementation. Users may wish to override this with an efficient one.

Parameters:

graph - The given SDF graph.

schedule - The given schedule.

Returns:

The lower bound for buffer sharing cost.

bufferSize

public static int[] bufferSize(SDFGraph graph,
                               mocgraph.sched.Schedule schedule)

Compute buffer size for a given SDF graph and schedule. This is a universal, though naive, implementation. Users may wish to override this with an efficient one.

Parameters:

graph - The given SDF graph.

schedule - The given schedule.

Returns:

An array of buffer size.

bufferSizeMap

public static java.util.Map bufferSizeMap(SDFGraph graph,
                                          mocgraph.sched.Schedule schedule)

Compute buffer size for a given SDF graph and schedule. This is a universal, though naive, implementation. Users may wish to override this with an efficient one.

Parameters:

graph - The given SDF graph.

schedule - The given schedule.

Returns:

A map from edges to buffer sizes.

bufferSizeMapping

public static mocgraph.mapping.ToIntMapMapping bufferSizeMapping(SDFGraph graph,
                                                                 mocgraph.sched.Schedule schedule)

Compute buffer size for a given SDF graph and schedule. This is a universal, though naive, implementation. Users may wish to override this with an efficient one.

Parameters:

graph - The given SDF graph.

schedule - The given schedule.

Returns:

The buffer sizes in ToIntMapMapping.

verifyBufferIntersections

public static boolean verifyBufferIntersections(SDFGraph graph,
                                                mocgraph.sched.Schedule schedule,
                                                java.util.Map intersectionsMap)

Verify the correctness of the given buffer intersections. The given intersections are compared to those computed by bufferIntersections(SDFGraph, Schedule), where the results are computed in an exhausted and brute force way. This method is primary for debugging purpose.

Parameters:

graph - The given SDF graph.

schedule - The given schedule.

intersectionsMap - The buffer intersections to verify.

Returns:

True if the intersections are correct; false otherwise.