#include <boost/config.hpp>
#include <iostream>
#include <fstream>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/copy.hpp>
#include <queue>
#include <map>
#include <list>
#include <bitset>
#include <algorithm>

Include dependency graph for routing.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

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.

Parameters

G	Pointer to the directed graph representing the device model.

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.

Parameters

a	Pointer to the first item.
b	Pointer to the second item.

Returns: int The result of the comparison.

Comparison function for sorting.

◆ depositRoute()

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

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

Parameters

signal	The signal (application-graph node) for which to deposit the route.
nodes	Pointer to the list of device-model nodes used in routing the signal.

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 GRAMM 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.

Parameters

signal	The signal for which to find the root output pin.
gConfig	Pointer to the map containing configuration data for nodes in the graph.

Returns: int Returns the root output pin acting as the driver for the signal.

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.

Parameters

signal The signal whose cost is to be retrieved.

Returns: int The cost of the specified 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.

Parameters

signal The signal to check for overlap.

Returns: bool True if there is an overlap, false otherwise.

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.

Parameters

signal	The signal (application-graph-node) whose routing is to be removed.
nodes	Pointer to the list of (device-model-nodes) used in routing structure of the "signal".

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)

Parameters

signal	The signal (application-graph-node) whose routing is to be removed.
G	Pointer to the directed graph representing the device model.

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

Parameters

G	Pointer to the device model graph.
signal	The source node (signal) to be routed.
sink-set	:: The destination nodes (sink) for the routing.
route	Pointer to the list where the route will be stored.
gConfig	Pointer to the map containing node configurations for the device model graph.
hConfig	A map containing node configuration details of device-model graph.

Returns: int Returns an integer cost of the routing path.

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.

Parameters

G	Pointer to the device model graph.
H	Pointer to the application graph.
y	The application-graph node whose fanout edges are to be routed.
gConfig	Pointer to the map containing node configurations for the device model graph.
hConfig	A map containing node configuration details of device-model graph.

Returns: int Returns an integer cost of the routing path.

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

Parameters

list	Pointer to the integer array describing the ordering of the vertices of H graph.
n	The number of elements/vertices in the H graph

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.

Parameters

G	Pointer to the directed graph representing the device model.

Returns: int The total overused resources in the graph.

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.

Parameters

G	Pointer to the directed graph representing the device model.

Returns: int The total used resources in the graph.

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

Functions

Function Documentation

◆ adjustHistoryCosts()

◆ calculate_cost()

◆ cmpfunc()

◆ depositRoute()

◆ findFuncCellFromOutputPin()

◆ findGNodeID_FuncCell()

◆ findOutputPinFromFuncCell()

◆ findRoot()

◆ getSignalCost()

◆ hasOverlap()

◆ matchesPattern()

◆ ripup()

◆ ripUpRouting()

◆ route()

◆ routeSignal()

◆ sortList()

◆ totalOveruse()

◆ totalUsed()