MRRGProcedures.cpp File Reference

#include <CGRA/MRRGProcedures.h>
#include <CGRA/GraphAlgorithms.h>
#include <queue>

Go to the source code of this file.

Classes
class	MRRGProcedureCache
struct	MRRGProcedureCache::Paths

Functions
std::ostream &	operator<< (std::ostream &os, const FunctionalUnitNeighbours &fu_neighbours)
std::ostream &	operator<< (std::ostream &os, const InterMRRGMap &imm)
MRRGNodeClassListsByCycle	computeNodeClassListsByCycle (const MRRG &mrrg)
MRRGNodeClassLists	computeNodeClassLists (const MRRG &mrrg)
FunctionalUnitNeighbours::NodeInfoList	findNeighbourFUs (const MRRG &mrrg, MRRG::NodeDescriptor source, int min_neighbours_to_find)
std::unordered_map< OpGraph::OpDescriptor, std::vector< MRRG::NodeDescriptor > >	findAllCompatibleFUs (const OpGraph &opgraph, const MRRG &base_mrrg)
std::vector< std::vector< MRRG::NodeDescriptor > >	findNRoutingPathsBetween (int num_paths, const MRRG &mrrg, MRRG::NodeDescriptor source, MRRG::NodeDescriptor sink, std::pair< int, int > cycle_trip_count_min_max, const OperandTag &operand_tag, MRRGProcedureCacheHandle *cache_handle)
std::vector< std::vector< MRRG::NodeDescriptor > >	mergeMRRGWalks (const MRRG &mrrg, const std::vector< MrrgNodeSpan > &walks)
int	tripCountOfWalk (const MRRG &mrrg, const std::vector< MRRG::NodeDescriptor > &walk)
bool	nodeIsCompatibleWithOperand (const MRRG &mrrg, MRRG::NodeDescriptor node, const OperandTag &operand_tag)
bool	walkIsCompatibleWithOperand (const MRRG &mrrg, const std::vector< MRRG::NodeDescriptor > &walk, const OperandTag &operand_tag)
static void	recordNodeMerge (const MRRG &src_mrrg, MRRGTransformationResult &transformation_result, MRRG::NodeDescriptor into_ndesc, MRRG::NodeDescriptor from_ndesc)
MRRGTransformationResult	reduceLosslessly (const MRRG &src_mrrg, const MRRGTransformFlags &flags)
MRRGTransformationResult	muxExNodeInsertion (const MRRG &src_mrrg)
bool	isNodeFanoutOf (const MRRG &mrrg, MRRG::NodeDescriptor driver_ndesc, MRRG::NodeDescriptor test_ndesc)
bool	isNodeFaninOf (const MRRG &mrrg, MRRG::NodeDescriptor driven_ndesc, MRRG::NodeDescriptor test_ndesc)
void	assertNodeIsFanoutOf (const MRRG &mrrg, MRRG::NodeDescriptor driver_ndesc, MRRG::NodeDescriptor test_ndesc, const char *action_name)
void	assertNodeIsFaninOf (const MRRG &mrrg, MRRG::NodeDescriptor driven_ndesc, MRRG::NodeDescriptor test_ndesc, const char *action_name)
void	assertNodeIsExcusiveFanout (const MRRG &mrrg, MRRG::NodeDescriptor driver_ndesc, MRRG::NodeDescriptor test_ndesc, const char *action_name)
void	assertNodeIsExcusiveFanin (const MRRG &mrrg, MRRG::NodeDescriptor driven_ndesc, MRRG::NodeDescriptor test_ndesc, const char *action_name)
void	assertHasNoOps (const MRRGNode &n, const char *action_name)
void	assertHasSingleFanout (const MRRGNode &n, const char *action_name)
void	mergeNodeConnections (MRRG &mrrg, MRRG::NodeDescriptor into_ndesc, MRRG::NodeDescriptor from_ndesc)
void	mergeNodePropertiesOfExclusiveFanoutToExclusiveFanin (MRRG &mrrg, MRRG::NodeDescriptor into_ndesc, MRRG::NodeDescriptor from_ndesc)
Mapping	transformToOriginalMRRG (const Mapping &map, const MRRGTransformationResult &transformation)

Function Documentation

assertHasNoOps()

void assertHasNoOps	(	const MRRGNode &	n,
		const char *	action_name
	)

Definition at line 555 of file MRRGProcedures.cpp.

assertHasSingleFanout()

void assertHasSingleFanout	(	const MRRGNode &	n,
		const char *	action_name
	)

Definition at line 561 of file MRRGProcedures.cpp.

assertNodeIsExcusiveFanin()

void assertNodeIsExcusiveFanin	(	const MRRG &	mrrg,
		MRRG::NodeDescriptor	driven_ndesc,
		MRRG::NodeDescriptor	test_ndesc,
		const char *	action_name
	)

Definition at line 547 of file MRRGProcedures.cpp.

assertNodeIsExcusiveFanout()

void assertNodeIsExcusiveFanout	(	const MRRG &	mrrg,
		MRRG::NodeDescriptor	driver_ndesc,
		MRRG::NodeDescriptor	test_ndesc,
		const char *	action_name
	)

Definition at line 539 of file MRRGProcedures.cpp.

assertNodeIsFaninOf()

void assertNodeIsFaninOf	(	const MRRG &	mrrg,
		MRRG::NodeDescriptor	driven_ndesc,
		MRRG::NodeDescriptor	test_ndesc,
		const char *	action_name
	)

Definition at line 533 of file MRRGProcedures.cpp.

assertNodeIsFanoutOf()

void assertNodeIsFanoutOf	(	const MRRG &	mrrg,
		MRRG::NodeDescriptor	driver_ndesc,
		MRRG::NodeDescriptor	test_ndesc,
		const char *	action_name
	)

Definition at line 527 of file MRRGProcedures.cpp.

computeNodeClassLists()

MRRGNodeClassLists computeNodeClassLists

(

const MRRG &

mrrg

)

Finds certain useful node classes, puts them in lists

Definition at line 169 of file MRRGProcedures.cpp.

computeNodeClassListsByCycle()

MRRGNodeClassListsByCycle computeNodeClassListsByCycle

(

const MRRG &

mrrg

)

Finds certain useful node classes, puts them in lists

Definition at line 138 of file MRRGProcedures.cpp.

findAllCompatibleFUs()

std::unordered_map<OpGraph::OpDescriptor, std::vector<MRRG::NodeDescriptor> > findAllCompatibleFUs	(	const OpGraph &	opgraph,
		const MRRG &	base_mrrg
	)

Examines the nodes in mrrg to find compatible nodes for each op in opgraph

Definition at line 230 of file MRRGProcedures.cpp.

findNeighbourFUs()

FunctionalUnitNeighbours::NodeInfoList findNeighbourFUs	(	const MRRG &	mrrg,
		MRRG::NodeDescriptor	source,
		int	min_neighbours_to_find
	)

Finds functional units that are reachable from the given node source. An breath-first fanout search of mrrg is performed (starting at the fanout of source) that does not pass through any FU nodes. Give a non-negative number for min_neighbours_to_find to limit number of FUs found - after finding at least this many FUs, the search will stop. This is a minimum because this function will return all FUs in mrrg that are at most as far as the farthest FU returned. Distance is measured as the number of vertices on the shortest path starting from source

Definition at line 194 of file MRRGProcedures.cpp.

findNRoutingPathsBetween()

std::vector<std::vector<MRRG::NodeDescriptor> > findNRoutingPathsBetween	(	int	num_paths,
		const MRRG &	mrrg,
		MRRG::NodeDescriptor	source,
		MRRG::NodeDescriptor	sink,
		std::pair< int, int >	cycle_trip_count_min_max,
		const OperandTag &	operand_tag,
		MRRGProcedureCacheHandle *	cache_handle
	)

Search mrrg for up to N paths between source and sink that do not include any FU nodes other than source or sink, and are compatible with operand_tag . A negative number will result in all paths being found. sink == source is allowed, and it will return only paths that include a fanout of source, ie. the length of the paths will always be at least 2. Also, for sink == source, paths returned will have a trip count in the closed interval cycle_trip_count_min_max . All returned paths will satisfy .front() == source and .back() == sink, and be at least 2 nodes.

Definition at line 248 of file MRRGProcedures.cpp.

isNodeFaninOf()

bool isNodeFaninOf	(	const MRRG &	mrrg,
		MRRG::NodeDescriptor	driven_ndesc,
		MRRG::NodeDescriptor	test_ndesc
	)

Definition at line 511 of file MRRGProcedures.cpp.

isNodeFanoutOf()

bool isNodeFanoutOf	(	const MRRG &	mrrg,
		MRRG::NodeDescriptor	driver_ndesc,
		MRRG::NodeDescriptor	test_ndesc
	)

Definition at line 495 of file MRRGProcedures.cpp.

mergeMRRGWalks()

std::vector<std::vector<MRRG::NodeDescriptor> > mergeMRRGWalks	(	const MRRG &	mrrg,
		const std::vector< MrrgNodeSpan > &	walks
	)

Automatic merging of paths through an MRRG. Usual use case is resolving the results of routing the destinations of a val independently. Note that this function ignores latency, so, for the merged result to be functionally equivalent to the input, all re-convergences should have matching iteration latency.

Takes a list of edge sequences ("walks", as a lists of vertices), and from the superset of all edges in the walks,produces a list of edge lists (as lists of of vertices) that do not overlap, other than at their terminal nodes (ie. all edges are unique). Additionally, if the returned edge lists are merged, they form a polytree – a directed acyclic graph that if converted to an undirected graph, would be a tree (or forest). That is, in addition to there being no cycles, there are also no re-convergences.

Definition at line 296 of file MRRGProcedures.cpp.

mergeNodeConnections()

void mergeNodeConnections	(	MRRG &	mrrg,
		MRRG::NodeDescriptor	into_ndesc,
		MRRG::NodeDescriptor	from_ndesc
	)

Add the fanin and fanout of from_ndesc to into_ndesc

Definition at line 567 of file MRRGProcedures.cpp.

mergeNodePropertiesOfExclusiveFanoutToExclusiveFanin()

void mergeNodePropertiesOfExclusiveFanoutToExclusiveFanin	(	MRRG &	mrrg,
		MRRG::NodeDescriptor	into_ndesc,
		MRRG::NodeDescriptor	from_ndesc
	)

Given a node from_ndesc that is the only fanout of into_ndesc, and where into_ndesc is the only fanin of from_ndesc, add the properties of from_ndesc into into_ndesc

Definition at line 583 of file MRRGProcedures.cpp.

muxExNodeInsertion()

MRRGTransformationResult muxExNodeInsertion

(

const MRRG &

src_mrrg

)

Adding nodes to satisfy constraint where a node with multiple fan-out cannot fan-out to a node with multiple fan-in

Make sure that node with multiple fanout does not fanout to a node with multiple fanin

Definition at line 458 of file MRRGProcedures.cpp.

nodeIsCompatibleWithOperand()

bool nodeIsCompatibleWithOperand	(	const MRRG &	mrrg,
		MRRG::NodeDescriptor	node,
		const OperandTag &	operand_tag
	)

Is this node compatible with the operand tag? Handles null tags and nodes with no supplied tags.

Definition at line 391 of file MRRGProcedures.cpp.

operator<<() [1/2]

std::ostream& operator<<	(	std::ostream &	os,
		const FunctionalUnitNeighbours &	fu_neighbours
	)

Definition at line 38 of file MRRGProcedures.cpp.

operator<<() [2/2]

std::ostream& operator<<	(	std::ostream &	os,
		const InterMRRGMap &	imm
	)

Definition at line 98 of file MRRGProcedures.cpp.

recordNodeMerge()

static void recordNodeMerge ( const MRRG &  src_mrrg, MRRGTransformationResult &  transformation_result, MRRG::NodeDescriptor  into_ndesc, MRRG::NodeDescriptor  from_ndesc  )

static

Definition at line 405 of file MRRGProcedures.cpp.

reduceLosslessly()

MRRGTransformationResult reduceLosslessly	(	const MRRG &	src_mrrg,
		const MRRGTransformFlags &	flags
	)

Make a simplified copy of the given MRRG, in a way that looses no information. A reverse mapping is guaranteed to exist.

Definition at line 420 of file MRRGProcedures.cpp.

transformToOriginalMRRG()

Mapping transformToOriginalMRRG	(	const Mapping &	map,
		const MRRGTransformationResult &	transformation
	)

Assuming the mapping operated on a transformed (reduced mrrg), undo the transformation.

Iterate through the mapping and replace each node withs its respective reverse mapping. All nodes should have a reverse mapping, although it may just be itself but in the original MRRG.

Definition at line 607 of file MRRGProcedures.cpp.

tripCountOfWalk()

int tripCountOfWalk	(	const MRRG &	mrrg,
		const std::vector< MRRG::NodeDescriptor > &	walk
	)

Count the number of times this walk goes from context N to context 0. It includes delay from all nodes except the last; delay is defined as from the input of the front() to the input of the back() This definition is used because a walk is a a sequence of connected edges, but we are using a sequence of vertices to describe it. The following additive identity holds: tripCountOfWalk({a,..,b}) + tripCountOfWalk({b,..,c}) = tripCountOfWalk({a,..,b,..,c}) Will throw ifwalk` does not have at least 2 elements.

Definition at line 379 of file MRRGProcedures.cpp.

walkIsCompatibleWithOperand()

bool walkIsCompatibleWithOperand	(	const MRRG &	mrrg,
		const std::vector< MRRG::NodeDescriptor > &	walk,
		const OperandTag &	operand_tag
	)

Does this walk consist soley of either nodes that have the operand, or nodes with no operand set? Uses the usual definition of a walk (ie. the last node is not part of the walk). Invariant: concatenated walks behave like logical AND, ie. f(a) && f(b) == f(a+b) always holds.

Definition at line 396 of file MRRGProcedures.cpp.