GraphPartitioner will recursively bi-partition the netlist (which could be netlist of clusters) based on connectivitity and the net weights. More...

#include <GraphPartitioner.h>

Public Member Functions
	GraphPartitioner (NodeList &nodeList, NetList &netList, int minClusterCellNum, int jobs, bool verbose)
	Construct a new Graph Partitioner object. More...

	~GraphPartitioner ()

void	solve (int eachClusterDSPNum, int eachClusterBRAMNum)
	a caller which will start the partitioning procedure More...

const std::vector< std::vector< int > > &	getClusters ()
	Get the clusters after partitioning (each is a vector containing ids for nodes inside the clusters) More...

const std::vector< std::set< int > > &	getClustersPUIdSets ()
	Get the clusters after partitioning (each is a set containing ids for nodes inside the clusters) More...

unsigned	minCutBipartition (const std::vector< int > &inputCluster, std::array< std::vector< int >, 2 > &outputClusters, GraphPartitioner< NodeList, NetList > *graphPartitioner, int eachClusterDSPNum, int eachClusterBRAMNum)
	the actual function to call partitioner to conduct partitioning with given clusters and parameters More...

void	setMaxCutRate (double _maxCutRate)
	Set the max mincut rate. More...

Static Public Member Functions
static void	recursiveMinCutPartition (std::vector< int > &inputCluster, GraphPartitioner< NodeList, NetList > *graphPartitioner, int eachClusterDSPNum, int eachClusterBRAMNum)
	a recursive function which will recursively bi-partition the input cluster into two based on connectivity and some resouce constraints More...

Private Member Functions
void	sortClustersBySize ()
	sort clusters by sizes to fix the output clusters' order for later processing and avoid the random factor due to the multi-process procedure More...

Private Attributes
std::vector< std::vector< int > >	clusters
	the resultant clusters (vectors) after partitioning More...

std::vector< std::set< int > >	ClusterPUIdSets
	the resultant clusters (set) after partitioning More...

sem_t	partitionSem
	used to limit the number of processes for the parallel partitioning More...

std::mutex	clustersLock

std::mutex	cntLock

double	maxCutRate = 0.0333

NodeList &	nodeList

NetList &	netList

unsigned int	minClusterCellNum

bool	verbose

Detailed Description

template<class NodeList, class NetList>
class GraphPartitioner< NodeList, NetList >

GraphPartitioner will recursively bi-partition the netlist (which could be netlist of clusters) based on connectivitity and the net weights.

Template Parameters

NodeList	given node list type
NetList	given net list type

Definition at line 51 of file GraphPartitioner.h.

Constructor & Destructor Documentation

◆ GraphPartitioner()

template<class NodeList , class NetList >

GraphPartitioner< NodeList, NetList >::GraphPartitioner	(	NodeList &	nodeList,
		NetList &	netList,
		int	minClusterCellNum,
		int	jobs,
		bool	verbose
	)

inline

Construct a new Graph Partitioner object.

Parameters

nodeList	the node list (it should be a vector)
netList	the net list (it should be a vector)
minClusterCellNum	a constraint to set the minimum size of the cluster
jobs	the number of parallel partitioning workers
verbose	whether dumps detailed information

Definition at line 63 of file GraphPartitioner.h.

◆ ~GraphPartitioner()

template<class NodeList , class NetList >

GraphPartitioner< NodeList, NetList >::~GraphPartitioner ( )

inline

Definition at line 71 of file GraphPartitioner.h.

Member Function Documentation

◆ getClusters()

template<class NodeList , class NetList >

const std::vector<std::vector<int> >& GraphPartitioner< NodeList, NetList >::getClusters ( )

inline

Get the clusters after partitioning (each is a vector containing ids for nodes inside the clusters)

Returns: const std::vector<std::vector<int>>&

Definition at line 88 of file GraphPartitioner.h.

◆ getClustersPUIdSets()

template<class NodeList , class NetList >

const std::vector<std::set<int> >& GraphPartitioner< NodeList, NetList >::getClustersPUIdSets ( )

inline

Get the clusters after partitioning (each is a set containing ids for nodes inside the clusters)

Returns: const std::vector<std::set<int>>&

Definition at line 98 of file GraphPartitioner.h.

Referenced by ClusterPlacer::basicPartitioning(), ClusterPlacer::clockBasedPartitioning(), and ClusterPlacer::userDefinedClusterBasedPartitioning().

Here is the caller graph for this function:

◆ minCutBipartition()

template<class NodeList , class NetList >

unsigned GraphPartitioner< NodeList, NetList >::minCutBipartition	(	const std::vector< int > &	inputCluster,
		std::array< std::vector< int >, 2 > &	outputClusters,
		GraphPartitioner< NodeList, NetList > *	graphPartitioner,
		int	eachClusterDSPNum,
		int	eachClusterBRAMNum
	)

the actual function to call partitioner to conduct partitioning with given clusters and parameters

Parameters

inputCluster	a given input cluster
outputClusters	the resultant two clusters
graphPartitioner	the partitioning worker (graphPartitioner) to handle this partitioning task (since this is a static function, we have to pass the worker as arguments to conduct partitioning)
eachClusterDSPNum	a constraint to limit the maximum of the DSP in a cluster
eachClusterBRAMNum	a constraint to limit the maximum of the BRAM in a cluster

Returns: unsigned

Definition at line 108 of file GraphPartitioner.cc.

Referenced by GraphPartitioner< NodeList, NetList >::recursiveMinCutPartition().

Here is the caller graph for this function:

◆ recursiveMinCutPartition()

template<class NodeList , class NetList >

void GraphPartitioner< NodeList, NetList >::recursiveMinCutPartition	(	std::vector< int > &	inputCluster,
		GraphPartitioner< NodeList, NetList > *	graphPartitioner,
		int	eachClusterDSPNum,
		int	eachClusterBRAMNum
	)

static

a recursive function which will recursively bi-partition the input cluster into two based on connectivity and some resouce constraints

Parameters

inputCluster	a given input cluster
graphPartitioner	the partitioning worker (graphPartitioner) to handle this partitioning task (since this is a static function, we have to pass the worker as arguments to conduct partitioning)
eachClusterDSPNum	a constraint to limit the maximum of the DSP in a cluster
eachClusterBRAMNum	a constraint to limit the maximum of the BRAM in a cluster

Definition at line 65 of file GraphPartitioner.cc.

Here is the call graph for this function:

◆ setMaxCutRate()

template<class NodeList , class NetList >

void GraphPartitioner< NodeList, NetList >::setMaxCutRate ( double _maxCutRate )

inline

Set the max mincut rate.

if the partitioning lead to a high mincut rate, the partitioning should be canceled.

Parameters

_maxCutRate

Definition at line 148 of file GraphPartitioner.h.

Referenced by ClusterPlacer::basicPartitioning(), ClusterPlacer::clockBasedPartitioning(), and ClusterPlacer::userDefinedClusterBasedPartitioning().

Here is the caller graph for this function:

◆ solve()

template<class NodeList , class NetList >

void GraphPartitioner< NodeList, NetList >::solve	(	int	eachClusterDSPNum,
		int	eachClusterBRAMNum
	)

a caller which will start the partitioning procedure

Parameters

eachClusterDSPNum	a constraint to limit the maximum of the DSP in a cluster
eachClusterBRAMNum	a constraint to limit the maximum of the BRAM in a cluster

Definition at line 32 of file GraphPartitioner.cc.

Referenced by ClusterPlacer::basicPartitioning(), ClusterPlacer::clockBasedPartitioning(), and ClusterPlacer::userDefinedClusterBasedPartitioning().

Here is the caller graph for this function:

◆ sortClustersBySize()

template<class NodeList , class NetList >

void GraphPartitioner< NodeList, NetList >::sortClustersBySize

private

sort clusters by sizes to fix the output clusters' order for later processing and avoid the random factor due to the multi-process procedure

Definition at line 45 of file GraphPartitioner.cc.

Member Data Documentation

◆ ClusterPUIdSets

template<class NodeList , class NetList >

std::vector<std::set<int> > GraphPartitioner< NodeList, NetList >::ClusterPUIdSets

private

the resultant clusters (set) after partitioning

Definition at line 164 of file GraphPartitioner.h.

Referenced by GraphPartitioner< std::vector< PlacementInfo::ClusterUnit * >, std::vector< PlacementInfo::ClusterNet * > >::getClustersPUIdSets().

◆ clusters

template<class NodeList , class NetList >

std::vector<std::vector<int> > GraphPartitioner< NodeList, NetList >::clusters

private

the resultant clusters (vectors) after partitioning

Definition at line 158 of file GraphPartitioner.h.

Referenced by GraphPartitioner< std::vector< PlacementInfo::ClusterUnit * >, std::vector< PlacementInfo::ClusterNet * > >::getClusters(), GraphPartitioner< std::vector< PlacementInfo::ClusterUnit * >, std::vector< PlacementInfo::ClusterNet * > >::getClustersPUIdSets(), and GraphPartitioner< NodeList, NetList >::recursiveMinCutPartition().

◆ clustersLock

template<class NodeList , class NetList >

std::mutex GraphPartitioner< NodeList, NetList >::clustersLock

private

Definition at line 171 of file GraphPartitioner.h.

Referenced by GraphPartitioner< NodeList, NetList >::recursiveMinCutPartition().

◆ cntLock

template<class NodeList , class NetList >

std::mutex GraphPartitioner< NodeList, NetList >::cntLock

private

Definition at line 171 of file GraphPartitioner.h.

◆ maxCutRate

template<class NodeList , class NetList >

double GraphPartitioner< NodeList, NetList >::maxCutRate = 0.0333

private

Definition at line 173 of file GraphPartitioner.h.

Referenced by GraphPartitioner< std::vector< PlacementInfo::ClusterUnit * >, std::vector< PlacementInfo::ClusterNet * > >::setMaxCutRate().

◆ minClusterCellNum

template<class NodeList , class NetList >

unsigned int GraphPartitioner< NodeList, NetList >::minClusterCellNum

private

Definition at line 177 of file GraphPartitioner.h.

◆ netList

template<class NodeList , class NetList >

NetList& GraphPartitioner< NodeList, NetList >::netList

private

Definition at line 176 of file GraphPartitioner.h.

◆ nodeList

template<class NodeList , class NetList >

NodeList& GraphPartitioner< NodeList, NetList >::nodeList

private

Definition at line 175 of file GraphPartitioner.h.

Referenced by GraphPartitioner< std::vector< PlacementInfo::ClusterUnit * >, std::vector< PlacementInfo::ClusterNet * > >::recursiveMinCutPartition().

◆ partitionSem

template<class NodeList , class NetList >

sem_t GraphPartitioner< NodeList, NetList >::partitionSem

private

used to limit the number of processes for the parallel partitioning

Definition at line 170 of file GraphPartitioner.h.

Referenced by GraphPartitioner< std::vector< PlacementInfo::ClusterUnit * >, std::vector< PlacementInfo::ClusterNet * > >::GraphPartitioner(), and GraphPartitioner< NodeList, NetList >::recursiveMinCutPartition().

◆ verbose

template<class NodeList , class NetList >

bool GraphPartitioner< NodeList, NetList >::verbose

private

Definition at line 186 of file GraphPartitioner.h.

Referenced by GraphPartitioner< std::vector< PlacementInfo::ClusterUnit * >, std::vector< PlacementInfo::ClusterNet * > >::minCutBipartition().

The documentation for this class was generated from the following files:

src/lib/HiFPlacer/problemSolvers/GraphPartitioner.h
src/lib/HiFPlacer/problemSolvers/GraphPartitioner.cc

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<class NodeList, class NetList> class GraphPartitioner< NodeList, NetList >

Constructor & Destructor Documentation

◆ GraphPartitioner()

◆ ~GraphPartitioner()

Member Function Documentation

◆ getClusters()

◆ getClustersPUIdSets()

◆ minCutBipartition()

◆ recursiveMinCutPartition()

◆ setMaxCutRate()

◆ solve()

◆ sortClustersBySize()

Member Data Documentation

◆ ClusterPUIdSets

◆ clusters

◆ clustersLock

◆ cntLock

◆ maxCutRate

◆ minClusterCellNum

◆ netList

◆ nodeList

◆ partitionSem

◆ verbose

template<class NodeList, class NetList>
class GraphPartitioner< NodeList, NetList >