mapss.dif.csdf.sdf.mem
Class BufferSharing

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

public class BufferSharing
extends java.lang.Object

Communication buffers can share physical memory spaces if their lifetimes do not overlap. The purpose of sharing is to reduce the total space cost.

This class implements the algorithm proposed in Shared Buffer Implementations of Signal Processing Systems Using Lifetime Analysis Techniques by Praveen K. Murthy and Shuvra S. Bhattcharyya. In their algorithm, lifetime analysis is derived from an SDF schedule. The periodical behavior presented in SDF schedule enables efficient analysis on lifetimes. After that, the actual storage allocation is done by dynamic storage allocation (DSA) algorithms, e.g., first-fit.

CAUTION: The buffer lifetime analysis in the above algorithm assumes the input graph to be ACYCLIC. If not, an exception will be thrown.

Version:

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

Author:

Mingyung Ko

Field Summary

protected SDFGraph

_graph The associated SDF graph.

Constructor Summary

BufferSharing(SDFGraph graph, mocgraph.sched.Schedule schedule)
Constructor for given graph.

Method Summary

protected int	_bufferRepetition(mocgraph.Edge edge) Get repetition counts for the given buffer.
protected int	_computeBufferSharing() Evaluate buffer sharing and compute total buffer size needed.
int	bufferCount() Get the total number of buffers.
java.util.Map	bufferIntersections() Compute buffer intersections.
java.util.List	enumerateBuffersByDuration() Configure the internal buffer enumeration by durations.
java.util.List	enumerateBuffersByStart() Configure the internal buffer enumeration by start times (default enumeration).
static int	firstFit(java.util.List enumeration, java.util.Map intersections, java.util.Map sizeMap) First-fit algorithm for Dynamic Storage Allocation (DSA).
static java.util.Map	getBufferAddresses() Get buffer start addresses after calling firstFit to allocate buffers.
int	sharingCost() The space allocated to buffer sharing.

Methods inherited from class java.lang.Object

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

Field Detail

_graph

protected SDFGraph _graph

The associated SDF graph.

Constructor Detail

BufferSharing

public BufferSharing(SDFGraph graph,
                     mocgraph.sched.Schedule schedule)

Constructor for given graph.

Parameters:

graph - The given SDF graph

Method Detail

bufferCount

public int bufferCount()

Get the total number of buffers.

Returns:

Total number of buffers.

bufferIntersections

public java.util.Map bufferIntersections()

Compute buffer intersections. The result is returned as a map from edges to their intersecting edges (in Set).

Returns:

A map from edges to the set of edges intersecting with them.

enumerateBuffersByDuration

public java.util.List enumerateBuffersByDuration()

Configure the internal buffer enumeration by durations. The result enumeration is also returned.

Returns:

The result enumeration.

enumerateBuffersByStart

public java.util.List enumerateBuffersByStart()

Configure the internal buffer enumeration by start times (default enumeration). The result enumeration is also returned.

Returns:

The result enumeration.

firstFit

public static int firstFit(java.util.List enumeration,
                           java.util.Map intersections,
                           java.util.Map sizeMap)

First-fit algorithm for Dynamic Storage Allocation (DSA). The capacity needed to allocate all shared storage is returned. Though the method is used in this class for SDF graph buffer sharing, it's designed for general purpose.

Parameters:

enumeration - Enumeration over storages.

intersection - Storage intersections/lifetime overlaps.

sizeMap - A map from storage to Integer objects with integer valued storage size.

Returns:

Capacity needed for first-fit.

getBufferAddresses

public static java.util.Map getBufferAddresses()

Get buffer start addresses after calling firstFit to allocate buffers. End address of edge e = start address e + size e -1.

Returns:

An int[] stores the start address of every edge. The index of int[] is the index to access the edge from the graph.

sharingCost

public int sharingCost()

The space allocated to buffer sharing. It's the also the cost of dynamic storage allocation(DSA).

Returns:

Buffer sharing cost.

_bufferRepetition

protected int _bufferRepetition(mocgraph.Edge edge)

Get repetition counts for the given buffer.

Parameters:

edge - The given buffer's associated edge.

Returns:

The repetition counts.

_computeBufferSharing

protected int _computeBufferSharing()

Evaluate buffer sharing and compute total buffer size needed. This is the computation method that should be overrided by descendant classes.

Returns:

An Integer object with value of buffer size.