routing.cpp File Reference

#include "../lib/UGRAMM.h"
#include "../lib/utilities.h"
#include "../lib/routing.h"

Include dependency graph for routing.cpp:

Classes
struct	CustomComparator

Functions
bool	matchesPattern (const std::string &key, const std::string &gName, const std::string &lockName)
void	findGNodeID_FuncCell (const std::string &lockedNodeName, std::vector< int > &suitableGIDs)
int	findFuncCellFromOutputPin (int signal, DirectedGraph *G)
int	findOutputPinFromFuncCell (int signal, DirectedGraph *G)
int	findRoot (int signal, std::map< int, NodeConfig > *gConfig)
int	getSignalCost (int signal)
bool	hasOverlap (int signal)
int	totalUsed (DirectedGraph *G)
int	totalOveruse (DirectedGraph *G)
void	adjustHistoryCosts (DirectedGraph *G)
int	cmpfunc (const void *a, const void *b)
void	sortList (int list[], int n, std::map< int, NodeConfig > *hConfig)
void	ripup (int signal, std::list< int > *nodes)
void	ripUpRouting (int signal, DirectedGraph *G)
void	depositRoute (int signal, std::list< int > *nodes)
float	calculate_cost (int next)
int	route (DirectedGraph *G, int signal, std::set< int > sink, std::list< int > *route, std::map< int, NodeConfig > *gConfig, std::map< int, NodeConfig > *hConfig)
int	routeSignal (DirectedGraph *G, DirectedGraph *H, int y, std::map< int, NodeConfig > *gConfig, std::map< int, NodeConfig > *hConfig)

Function Documentation

adjustHistoryCosts()

void adjustHistoryCosts

(

DirectedGraph *

G

)

Adjusts the history costs for the device model graph for the next iteartion.

calculate_cost()

float calculate_cost

(

int

next

)

Calculate Pathfinder-based cost for a given vertex.

Parameters

next	Vertex for which to calculate the cost.

Returns

Calculated cost for the vertex.

cmpfunc()

int cmpfunc	(	const void *	a,
		const void *	b )

Comparison function for sorting.

depositRoute()

void depositRoute	(	int	signal,
		std::list< int > *	nodes )

Deposits the route into the routing structure for the given signal.

findFuncCellFromOutputPin()

int findFuncCellFromOutputPin	(	int	signal,
		DirectedGraph *	G )

For the given outputPin (signal), finds the associated FunCell node from the device model.

This function identifies the FunCell node in the device model graph G associated with the specified output pin (signal), tracing the source of this edge (walking uphill).

Ex: FunCell(signal) -> outPin (selectedCellOutputPin) [Walking uphill — finding the source of this edge]

Parameters

signal	The output pin (signal) for which to find the associated FunCell.
G	Pointer to the directed graph representing the device model.

Returns

int Returns the FunCell node corresponding to the given output pin.

findGNodeID_FuncCell()

void findGNodeID_FuncCell	(	const std::string &	lockedNodeName,
		std::vector< int > &	suitableGIDs )

This function gets the GID for the the funcCell node in the device model graph that meets the the lockedNodeName

Parameters

lockedNodeName	Passes the name for the locked PE node
suitableGIDs	Modifies this vector list with suitable G-graph node IDs

Returns

void

findOutputPinFromFuncCell()

int findOutputPinFromFuncCell	(	int	signal,
		DirectedGraph *	G )

For the given FunCell (signal), finds the associated outputPin node from the device model.

This function identifies the outputPin node in the device model graph G that is associated with the given FunCell (signal), tracing the sink of the edge (walking downhill).

Ex: FunCell(signal) -> outPin (selectedCellOutputPin) [Walking downhill — finding the sink of this edge]

Parameters

signal	The FunCell (signal) for which to find the associated outputPin.
G	Pointer to the directed graph representing the device model.

Returns

int Returns the outputPin node corresponding to the given FunCell.

findRoot()

int findRoot	(	int	signal,
		std::map< int, NodeConfig > *	gConfig )

Finds the root of the vertex model for the given signal.

As UGRAMM performs pin-to-pin mapping, the root of the vertex model, or starting point, will always be an output pin that serves as the driver for the routing fanout of the specified signal.

getSignalCost()

int getSignalCost

(

int

signal

)

Gets the current cost associated with the given signal.

hasOverlap()

bool hasOverlap

(

int

signal

)

Checks if there is an overlap for the given signal. Confirms by checking if there are more than one users for any element in the routing tree.

matchesPattern()

bool matchesPattern	(	const std::string &	key,
		const std::string &	gName,
		const std::string &	lockName )

This function enables wildcard naming for the locked.

It breaks the provided lock Name string into substrings based on a key. Once a list of substrings have been created, it checks in the gNamesInv map to see if all substring is present within a gName.

Parameters

key	a char used to split the string into substrings
gName	name of node in the device model graph
lockName	name of the locked name with wildcard included

Returns

bool Returns true if all of the substrings of the locked name are found in gName, false otherwise.

ripup()

void ripup	(	int	signal,
		std::list< int > *	nodes )

Removes the specified signal from the list of nodes.

ripUpRouting()

void ripUpRouting	(	int	signal,
		DirectedGraph *	G )

Removes the routing associated with the given signal from the routing structure. Make a list of used (device-model-nodes) for the given the given siganl (application-graph-node)

route()

int route	(	DirectedGraph *	G,
		int	signal,
		std::set< int >	sink,
		std::list< int > *	route,
		std::map< int, NodeConfig > *	gConfig,
		std::map< int, NodeConfig > *	hConfig )

Pathfinder approach for routing signal -> sink

routeSignal()

int routeSignal	(	DirectedGraph *	G,
		DirectedGraph *	H,
		int	y,
		std::map< int, NodeConfig > *	gConfig,
		std::map< int, NodeConfig > *	hConfig )

Routes all fanout edges of the specified application-graph node.

sortList()

void sortList	(	int	list[],
		int	n,
		std::map< int, NodeConfig > *	hConfig )

Sorting the nodes of H according to the size (number of vertices) of their vertex model

totalOveruse()

int totalOveruse

(

DirectedGraph *

G

)

Calculates the total amount of overused resources in the device model graph.

totalUsed()

int totalUsed

(

DirectedGraph *

G

)

Calculates the total amount of used resources in the device model graph.