sdf/generate/generate.cc File Reference

#include "base/base.h"
#include "generate.h"
#include "../base/algo/cycle.h"
#include "../base/algo/graph.h"
#include "../analysis/analysis.h"
#include "../transform/hsdf/hsdf.h"
#include "../transform/model/buffersize.h"
#include "../transform/model/autoconc.h"

Include dependency graph for sdf/generate/generate.cc:

Functions
void	relabelSDFgraph (SDFgraph *g, CId *actorIdMap=NULL, CId *channelIdMap=NULL)
SDFportsIter	randomPort (SDFportsIter begin, uint size)
SDFactorsIter	randomActor (SDFactorsIter begin, uint size)
SDFchannelsIter	randomChannel (SDFchannelsIter begin, uint size)
SDFport *	createPort (SDFactor *a, const SDFport::SDFportType type, const double avgRate, const double varRate, const double minRate, const double maxRate)
TimedSDFactor *	createActor (TimedSDFgraph *g)
TimedSDFchannel *	createChannel (TimedSDFgraph *g, SDFport *pi, SDFport *po)
TimedSDFgraph *	createGraph (const uint nrActors, const double avgInDegree, const double varInDegree, const double minInDegree, const double maxInDegree, const double avgOutDegree, const double varOutDegree, const double minOutDegree, const double maxOutDegree, const double avgRate, const double varRate, const double minRate, const double maxRate)
TimedSDFgraph *	createAcyclicGraph (const uint nrActors, const double avgInDegree, const double varInDegree, const double minInDegree, const double maxInDegree, const double avgOutDegree, const double varOutDegree, const double minOutDegree, const double maxOutDegree, const double avgRate, const double varRate, const double minRate, const double maxRate)
void	makeConsistentConnectedActors (CFractions &fractions, SDFactor *a)
void	makeConsistent (SDFgraph *g)
void	makeStronglyConnected (SDFgraph *g)
static void	fireActor (SDFactor *a)
bool	isActorReady (SDFactor *a)
void	updateActorReadyList (SDFactors &readyList, SDFactor *a)
SDFactor *	getRandomActorFromActorReadyList (SDFactors &readyList)
bool	execSDFgraph (SDFgraph *g, uint n)
void	distributeInitialTokensInComponent (TimedSDFgraph *g, SDFgraphComponent &component, const double initialTokenProp)
void	distributeInitialTokens (TimedSDFgraph *g, const double initialTokenProp)
void	assignConsistentRates (SDFgraph *g, const uint repVecSum)
void	makeSimpleGraph (SDFgraph *g)
TimedSDFgraph *	generateSDFgraph (const uint nrActors, const double avgInDegree, const double varInDegree, const double minInDegree, const double maxInDegree, const double avgOutDegree, const double varOutDegree, const double minOutDegree, const double maxOutDegree, const double avgRate, const double varRate, const double minRate, const double maxRate, const bool acyclic, const bool stronglyConnected, const double initialTokenProp, const uint repetitionVectorSum, const bool multigraph)
SDFtime	randomActorExecTime (const double avgExecTime, const double varExecTime, const double minExecTime, const double maxExecTime)
CSize	randomActorStateSize (const double avgStateSize, const double varStateSize, const double minStateSize, const double maxStateSize)
void	randomChannelTokenSize (TimedSDFchannel *c, const double avgTokenSize, const double varTokenSize, const double minTokenSize, const double maxTokenSize)
void	randomChannelBufferSizes (TimedSDFgraph *g)
void	randomBandwidthRequirement (TimedSDFchannel *c, const double avgBandwidth, const double varBandwidth, double minBandwidth, double maxBandwidth)
void	randomLatencyRequirement (TimedSDFchannel *c, const double avgLatency, const double varLatency, double minLatency, double maxLatency)
void	randomThroughputConstraint (TimedSDFgraph *g, const bool bufferSize, const uint autoConcurrencyDegree, const double throughputScaleFactor)
void	generateSDFgraphProperties (TimedSDFgraph *g, const bool execTime, const uint nrProcTypes, const double mapChance, const double avgExecTime, const double varExecTime, const double minExecTime, const double maxExecTime, const bool stateSize, const double avgStateSize, const double varStateSize, const double minStateSize, const double maxStateSize, const bool tokenSize, const double avgTokenSize, const double varTokenSize, const double minTokenSize, const double maxTokenSize, const bool throughputConstraint, const uint autoConcurrencyDegree, const double throughputScaleFactor, const bool bandwidthRequirement, const double avgBandwidth, const double varBandwidth, const double minBandwidth, const double maxBandwidth, const bool bufferSize, const bool latencyRequirement, const double avgLatency, const double varLatency, const double minLatency, const double maxLatency, const bool integerMCM)
Variables
static MTRand	mtRand

---

Function Documentation

void assignConsistentRates	(	SDFgraph *	g,
		const uint	repVecSum
	)

assignConsistentRates () The function attaches rates to all ports of the SDF graph that enforce that the sum of the repetition vector entries is equal to the repVecSum.

References c, SDFgraph::channelsBegin(), SDFgraph::channelsEnd(), gcd(), SDFchannel::getDstActor(), SDFchannel::getDstPort(), SDFcomponent::getId(), SDFchannel::getSrcActor(), SDFchannel::getSrcPort(), SDFgraph::nrActors(), MTRand::randInt(), and SDFport::setRate().

Referenced by generateSDFgraph().

Here is the call graph for this function:

TimedSDFactor* createActor

(

TimedSDFgraph *

g

)

createActor () Create an actor in the SDF graph.

References a, component, TimedSDFgraph::createActor(), TimedSDFactor::_Processor::execTime, SDFcomponent::getId(), SDFgraph::nrActors(), and SDFcomponent::setName().

Referenced by createAcyclicGraph(), and createGraph().

Here is the call graph for this function:

TimedSDFgraph* createAcyclicGraph	(	const uint	nrActors,
		const double	avgInDegree,
		const double	varInDegree,
		const double	minInDegree,
		const double	maxInDegree,
		const double	avgOutDegree,
		const double	varOutDegree,
		const double	minOutDegree,
		const double	maxOutDegree,
		const double	avgRate,
		const double	varRate,
		const double	minRate,
		const double	maxRate
	)

createAcyclicGraph () Create a random, connected, acyclic SDF graph.

References a, component, createActor(), createChannel(), createPort(), g, SDFport::getActor(), SDFcomponent::getName(), SDFport::In, SDFgraph::nrActors(), SDFactor::nrPorts(), SDFport::Out, pi, MTRand::randNorm(), randomPort(), SDFactor::removePort(), SDFcomponent::setName(), and SDFgraph::setType().

Referenced by generateSDFgraph().

Here is the call graph for this function:

TimedSDFchannel* createChannel	(	TimedSDFgraph *	g,
		SDFport *	pi,
		SDFport *	po
	)

createChannel () Create a channel in the SDF graph from pi to po.

References c, component, TimedSDFgraph::createChannel(), SDFcomponent::getId(), SDFgraph::nrChannels(), and SDFcomponent::setName().

Referenced by createAcyclicGraph(), and createGraph().

Here is the call graph for this function:

TimedSDFgraph* createGraph	(	const uint	nrActors,
		const double	avgInDegree,
		const double	varInDegree,
		const double	minInDegree,
		const double	maxInDegree,
		const double	avgOutDegree,
		const double	varOutDegree,
		const double	minOutDegree,
		const double	maxOutDegree,
		const double	avgRate,
		const double	varRate,
		const double	minRate,
		const double	maxRate
	)

createGraph () Create a random, connected SDF graph.

References a, component, createActor(), createChannel(), createPort(), g, SDFport::getActor(), SDFcomponent::getName(), SDFport::In, SDFgraph::nrActors(), SDFactor::nrPorts(), SDFport::Out, pi, MTRand::rand(), MTRand::randNorm(), randomPort(), SDFactor::removePort(), SDFcomponent::setName(), and SDFgraph::setType().

Referenced by generateSDFgraph().

Here is the call graph for this function:

SDFport* createPort	(	SDFactor *	a,
		const SDFport::SDFportType	type,
		const double	avgRate,
		const double	varRate,
		const double	minRate,
		const double	maxRate
	)

createPort () Create a port with random rate on the actor.

References SDFactor::createPort(), SDFcomponent::getId(), MTRand::randNorm(), and SDFcomponent::setName().

Referenced by createAcyclicGraph(), and createGraph().

Here is the call graph for this function:

void distributeInitialTokens	(	TimedSDFgraph *	g,
		const double	initialTokenProp
	)

distributeInitialTokens () Add initial tokens to the strongly connected components in the SDF to guarantee a deadlock-free SDF graph.

References c, SDFgraph::channelsBegin(), distributeInitialTokensInComponent(), SDFchannel::getInitialTokens(), SDFgraph::nrChannels(), MTRand::rand(), randomChannel(), SDFchannel::setInitialTokens(), and stronglyConnectedComponents().

Referenced by generateSDFgraph().

Here is the call graph for this function:

void distributeInitialTokensInComponent	(	TimedSDFgraph *	g,
		SDFgraphComponent &	component,
		const double	initialTokenProp
	)

distributeInitialTokensInComponent () Add initial tokens to the strongly connected component to guarantee a deadlock-free execution of the SDF component

References a, c, SDFgraph::channelsBegin(), SDFgraph::channelsEnd(), componentToSDFgraph(), FSMSADF::computeRepetitionVector(), execSDFgraph(), findSimpleCycle(), SDFport::getActor(), SDFgraph::getChannel(), SDFport::getChannel(), SDFcomponent::getId(), SDFchannel::getInitialTokens(), SDFcomponent::getName(), SDFport::getRate(), SDFport::getType(), SDFgraph::nrActors(), SDFgraph::nrChannels(), SDFchannel::oppositePort(), SDFactor::portsBegin(), SDFactor::portsEnd(), MTRand::randInt(), relabelSDFgraph(), SDFgraph::removeChannel(), SDFactor::removePort(), and SDFchannel::setInitialTokens().

Referenced by distributeInitialTokens().

Here is the call graph for this function:

bool execSDFgraph	(	SDFgraph *	g,
		uint	n
	)

execSDFgraph () Fire the actors in the SDF graph. The number of firings is n (or less in case of deadlock).

References a, SDFgraph::actorsBegin(), SDFgraph::actorsEnd(), ASSERT, fireActor(), getRandomActorFromActorReadyList(), isActorReady(), and updateActorReadyList().

Referenced by distributeInitialTokensInComponent().

Here is the call graph for this function:

static void fireActor

(

SDFactor *

a

)

[static]

fireActor () The function removes the number of tokens required for a firing of the actor from all input ports and it produces tokens on all output ports.

References c, SDFport::getChannel(), SDFcomponent::getId(), SDFchannel::getInitialTokens(), SDFport::getRate(), SDFport::getType(), SDFactor::portsBegin(), SDFactor::portsEnd(), and SDFchannel::setInitialTokens().

Referenced by execSDFgraph().

Here is the call graph for this function:

TimedSDFgraph* generateSDFgraph	(	const uint	nrActors,
		const double	avgInDegree,
		const double	varInDegree,
		const double	minInDegree,
		const double	maxInDegree,
		const double	avgOutDegree,
		const double	varOutDegree,
		const double	minOutDegree,
		const double	maxOutDegree,
		const double	avgRate,
		const double	varRate,
		const double	minRate,
		const double	maxRate,
		const bool	acyclic,
		const bool	stronglyConnected,
		const double	initialTokenProp,
		const uint	repetitionVectorSum,
		const bool	multigraph
	)

generateSDFgraph () Generate a random SDF graph.

References assignConsistentRates(), createAcyclicGraph(), createGraph(), distributeInitialTokens(), g, makeConsistent(), makeSimpleGraph(), and makeStronglyConnected().

Referenced by generateCSDFgraph(), and generateRandomSDFG().

Here is the call graph for this function:

void generateSDFgraphProperties	(	TimedSDFgraph *	g,
		const bool	execTime,
		const uint	nrProcTypes,
		const double	mapChance,
		const double	avgExecTime,
		const double	varExecTime,
		const double	minExecTime,
		const double	maxExecTime,
		const bool	stateSize,
		const double	avgStateSize,
		const double	varStateSize,
		const double	minStateSize,
		const double	maxStateSize,
		const bool	tokenSize,
		const double	avgTokenSize,
		const double	varTokenSize,
		const double	minTokenSize,
		const double	maxTokenSize,
		const bool	throughputConstraint,
		const uint	autoConcurrencyDegree,
		const double	throughputScaleFactor,
		const bool	bandwidthRequirement,
		const double	avgBandwidth,
		const double	varBandwidth,
		const double	minBandwidth,
		const double	maxBandwidth,
		const bool	bufferSize,
		const bool	latencyRequirement,
		const double	avgLatency,
		const double	varLatency,
		const double	minLatency,
		const double	maxLatency,
		const bool	integerMCM
	)

generateSDFgraphProperties () Generate properties for a random SDF graph.

References a, SDFgraph::actorsBegin(), SDFgraph::actorsEnd(), TimedSDFactor::addProcessor(), SDFstateSpaceThroughputAnalysis::analyze(), ASSERT, c, SDFgraph::channelsBegin(), SDFgraph::channelsEnd(), TimedSDFactor::_Processor::execTime, TimedSDFactor::processorsBegin(), TimedSDFactor::processorsEnd(), MTRand::rand(), randomActorExecTime(), randomActorStateSize(), randomBandwidthRequirement(), randomChannelBufferSizes(), randomChannelTokenSize(), randomLatencyRequirement(), randomThroughputConstraint(), TimedSDFactor::removeProcessor(), TimedSDFactor::setDefaultProcessor(), TimedSDFactor::_Processor::stateSize, and TimedSDFactor::_Processor::type.

Referenced by generateCSDFgraph(), and generateRandomSDFG().

Here is the call graph for this function:

SDFactor* getRandomActorFromActorReadyList

(

SDFactors &

readyList

)

getRandomActorFromActorReadyList () The function returns a random actor from the list.

References MTRand::randInt().

Referenced by execSDFgraph().

Here is the call graph for this function:

bool isActorReady

(

SDFactor *

a

)

isActorReady () The function checks wether there are enough tokens on the input ports to fire the actor.

References c, SDFport::getChannel(), SDFchannel::getInitialTokens(), SDFport::getRate(), SDFport::getType(), SDFactor::portsBegin(), and SDFactor::portsEnd().

Referenced by execSDFgraph(), and updateActorReadyList().

Here is the call graph for this function:

void makeConsistent

(

SDFgraph *

g

)

makeConsistent () The rates on the ports are adjuested to create a consistent SDF graph.

References a, SDFgraph::actorsBegin(), SDFgraph::actorsEnd(), SDFcomponent::getId(), makeConsistentConnectedActors(), and SDFgraph::nrActors().

Referenced by generateSDFgraph().

Here is the call graph for this function:

void makeConsistentConnectedActors	(	CFractions &	fractions,
		SDFactor *	a
	)

makeConsistentConnectedActors () The function calculates firing rates (as fractions) of all actors connected to actor 'a' based on its firing rate. In case of an inconsistent graph, the inconsistency is fixed by adjusting the rate of a port.

References c, SDFport::getActor(), SDFport::getChannel(), SDFchannel::getDstPort(), SDFcomponent::getId(), SDFport::getRate(), SDFchannel::getSrcPort(), SDFactor::portsBegin(), SDFactor::portsEnd(), and SDFport::setRate().

Referenced by makeConsistent().

Here is the call graph for this function:

void makeSimpleGraph

(

SDFgraph *

g

)

makeSimpleGraph () The function transforms the multigraph g to a graph in which there is at most one channel from a node to another node. When multiple channels are found, all except the channel that was found first are removed.

References a, SDFgraph::actorsBegin(), SDFgraph::actorsEnd(), c, SDFport::getActor(), SDFport::getChannel(), SDFcomponent::getId(), SDFcomponent::getName(), SDFgraph::nrActors(), SDFchannel::oppositePort(), SDFactor::portsBegin(), SDFactor::portsEnd(), relabelSDFgraph(), SDFgraph::removeChannel(), and SDFactor::removePort().

Referenced by generateSDFgraph().

Here is the call graph for this function:

void makeStronglyConnected

(

SDFgraph *

g

)

makeStronglyConnected () The function changes the SDF graph into a strongly connected SDF graph by selecting the largest strongly connected component in the graph and removing actors and channels which do not belong to this component from the graph.

References actorInComponent(), SDFgraph::actorsBegin(), SDFgraph::actorsEnd(), c, SDFgraph::channelsBegin(), SDFgraph::channelsEnd(), SDFchannel::getDstActor(), SDFchannel::getDstPort(), SDFcomponent::getName(), SDFchannel::getSrcActor(), SDFchannel::getSrcPort(), isStronglyConnectedGraph(), SDFgraph::nrChannels(), relabelSDFgraph(), SDFgraph::removeActor(), SDFgraph::removeChannel(), SDFactor::removePort(), stronglyConnectedComponents(), and v.

Referenced by generateSDFgraph().

Here is the call graph for this function:

SDFactorsIter randomActor	(	SDFactorsIter	begin,
		uint	size
	)

randomActor () The function returns an iterator to a random actor in the list.

References ASSERT, and MTRand::randInt().

Here is the call graph for this function:

SDFtime randomActorExecTime	(	const double	avgExecTime,
		const double	varExecTime,
		const double	minExecTime,
		const double	maxExecTime
	)

randomActorExecTime () The function assigns a random execution time to the actor.

References MTRand::randNorm().

Referenced by generateSDFgraphProperties().

Here is the call graph for this function:

CSize randomActorStateSize	(	const double	avgStateSize,
		const double	varStateSize,
		const double	minStateSize,
		const double	maxStateSize
	)

randomActorStateSize () The function assigns a random state size to the actor.

References MTRand::randNorm().

Referenced by generateSDFgraphProperties().

Here is the call graph for this function:

void randomBandwidthRequirement	(	TimedSDFchannel *	c,
		const double	avgBandwidth,
		const double	varBandwidth,
		double	minBandwidth,
		double	maxBandwidth
	)

randomBandwidthRequirement () The function assigns a random bandwidth requirement to the channel.

References MTRand::randNorm(), and TimedSDFchannel::setMinBandwidth().

Referenced by generateSDFgraphProperties().

Here is the call graph for this function:

SDFchannelsIter randomChannel	(	SDFchannelsIter	begin,
		uint	size
	)

randomChannel () The function returns an iterator to a random channel in the list.

References ASSERT, and MTRand::randInt().

Referenced by distributeInitialTokens().

Here is the call graph for this function:

void randomChannelBufferSizes

(

TimedSDFgraph *

g

)

randomChannelBufferSizes () Assign a random buffer sizes to all channels. The function guarantees that the buffers are large enough to realize a positive (non-zero) throughput.

References SDFstateSpaceBufferAnalysis::analyze(), c, SDFgraph::channelsBegin(), SDFgraph::channelsEnd(), FSMSADF::computeRepetitionVector(), _StorageDistributionSet::distributions, TimedSDFchannel::_BufferSize::dst, TimedSDFchannel::getBufferSize(), SDFchannel::getDstActor(), SDFchannel::getDstPort(), SDFcomponent::getId(), SDFchannel::getInitialTokens(), SDFport::getRate(), SDFchannel::getSrcActor(), SDFchannel::getSrcPort(), TimedSDFchannel::_BufferSize::mem, minSz, _StorageDistributionSet::next, MTRand::randInt(), TimedSDFchannel::setBufferSize(), _StorageDistribution::sp, TimedSDFchannel::_BufferSize::src, TimedSDFchannel::_BufferSize::sz, and _StorageDistributionSet::thr.

Referenced by generateSDFgraphProperties().

Here is the call graph for this function:

void randomChannelTokenSize	(	TimedSDFchannel *	c,
		const double	avgTokenSize,
		const double	varTokenSize,
		const double	minTokenSize,
		const double	maxTokenSize
	)

randomChannelTokenSize () The function assigns a random token size to the tokens in the channel.

References MTRand::randNorm(), and TimedSDFchannel::setTokenSize().

Referenced by generateSDFgraphProperties().

Here is the call graph for this function:

void randomLatencyRequirement	(	TimedSDFchannel *	c,
		const double	avgLatency,
		const double	varLatency,
		double	minLatency,
		double	maxLatency
	)

randomLatencyRequirement () The function assigns a random latency requirement to the channel.

References MTRand::randNorm(), and TimedSDFchannel::setMinLatency().

Referenced by generateSDFgraphProperties().

Here is the call graph for this function:

SDFportsIter randomPort	(	SDFportsIter	begin,
		uint	size
	)

randomPort () The function returns an iterator to a random port in the list.

References ASSERT, and MTRand::randInt().

Referenced by createAcyclicGraph(), and createGraph().

Here is the call graph for this function:

void randomThroughputConstraint	(	TimedSDFgraph *	g,
		const bool	bufferSize,
		const uint	autoConcurrencyDegree,
		const double	throughputScaleFactor
	)

randomThroughputConstraint () Set a random throughput constraint on the graph.

References SDFstateSpaceThroughputAnalysis::analyze(), TimedSDFgraph::clone(), component, SDFcomponent::getId(), SDFcomponent::getName(), SDFcomponent::getParent(), modelAutoConcurrencyInSDFgraph(), modelBufferSizeInSDFgraph(), MTRand::rand(), and TimedSDFgraph::setThroughputConstraint().

Referenced by generateSDFgraphProperties().

Here is the call graph for this function:

void relabelSDFgraph	(	SDFgraph *	g,
		CId *	actorIdMap = NULL,
		CId *	channelIdMap = NULL
	)

relabelSDFgraph () Set new id's on all actors and channels starting from 0 and change their names accordingly (actor<id> or ch<id>).

References SDFgraph::actorsBegin(), SDFgraph::actorsEnd(), c, SDFgraph::channelsBegin(), SDFgraph::channelsEnd(), SDFcomponent::getId(), SDFcomponent::setId(), and SDFcomponent::setName().

Referenced by distributeInitialTokensInComponent(), makeSimpleGraph(), and makeStronglyConnected().

Here is the call graph for this function:

void updateActorReadyList	(	SDFactors &	readyList,
		SDFactor *	a
	)

updateActorReadyList () The function updates the list of ready actors after the firing of actor a.

References SDFport::getChannel(), SDFchannel::getDstActor(), SDFcomponent::getId(), SDFport::getType(), isActorReady(), SDFactor::portsBegin(), and SDFactor::portsEnd().

Referenced by execSDFgraph().

Here is the call graph for this function:

---

Variable Documentation

MTRand mtRand [static]