AMF-Placer  2.0
An Open-Source Timing-driven Analytical Mixed-size FPGA Placer
ClusterPlacer Class Reference

ClusterPlacer will cluster nodes in the given netlist and place the clusters on the device based on simulated-annealing as initial placement. More...

#include <ClusterPlacer.h>

Collaboration diagram for ClusterPlacer:

Public Member Functions

 ClusterPlacer (PlacementInfo *placementInfo, std::map< std::string, std::string > &JSONCfg, float connectionToFixedFactor=5.0)
 Construct a new Cluster Placer object. More...
 
 ~ClusterPlacer ()
 
void ClusterPlacement ()
 conduct cluster placement, cluster nodes in the given netlist and place the clusters on the device as initial placement. More...
 

Private Member Functions

bool isDensePlacement ()
 
void resetClusterInfo ()
 clean all information of the clusters (including PlacementUnit-Cluster mapping and the cluster-level netlist) More...
 
void creaeClusterNets ()
 construct the netlist of the generated clusters based on the PlacementNet in PlacementInfo More...
 
void setClusterNetsAdjMat ()
 construct the cluster nets adjacent matrix for simulated-annealing cluster placement More...
 
void hypergraphPartitioning ()
 call specific partitioners to partition the design netlist into clusters for initial placement More...
 
void basicPartitioning (int minClusterCellNum, int eachClusterDSPNum, int eachClusterBRAMNum)
 pure connectivity-based partitioning based on PaToH More...
 
void clockBasedPartitioning (int minClusterCellNum, int eachClusterDSPNum, int eachClusterBRAMNum)
 initially cluster cells based on clock domains and conduct connectivity-based partitioning based on PaToH More...
 
void userDefinedClusterBasedPartitioning (int minClusterCellNum, int eachClusterDSPNum, int eachClusterBRAMNum)
 initially cluster cells based on user-defined clusters and conduct connectivity-based partitioning based on PaToH More...
 
void createUserDefinedClusterBasedClusterUnits ()
 initially cluster cells based on user-defined clusters More...
 
void createLongPathClusterUnits ()
 initially cluster cells based on user-defined clusters More...
 
void createClockBasedClusterUnits ()
 initially cluster cells based on clock domains More...
 
void createSinglePUClusterUnits ()
 wrap single PlacementUnits into ClusterUnit for later uniform processing More...
 
void refineClustersWithPredefinedClusters ()
 refine the elements in obtained clusters to ensure the cells in user-defined clusters in the same cluster More...
 
void clusterPlacementUnits ()
 cluster the netlist and create ClusterUnit level netlist for SA placement More...
 
void placeClusters ()
 conduct the ClusterUnit level SA placement and then map PlacementUnit to cluster location More...
 
void placeUnitBaseOnClusterPlacement (const std::vector< std::pair< int, int >> &cluster2XY)
 map PlacementUnit to cluster location More...
 
bool isClustersToLarges ()
 check whether the average size of clusters is greater than the given threshold More...
 
int getPlacementUnitMaxPathLen (PlacementInfo::PlacementUnit *curPU)
 
float random_float (float min, float max)
 
void dumpClusters ()
 
void drawClusters ()
 

Private Attributes

PlacementInfoplacementInfo
 the PlacementInfo for this placer to handle More...
 
std::vector< std::set< int > > clusters
 the resultant clusters of PlacementUnit (id) More...
 
std::map< std::string, std::string > & JSONCfg
 
float connectionToFixedFactor
 the enhancement ratio of the net between elements and I/Os More...
 
float y2xRatio = 1.0
 the Y/X coordinate calibration factor More...
 
bool verbose
 
bool randomInitialPlacement = false
 
int avgClusterSizeRequirement = 40000
 the requirement of the average size of clusters (the number of cells) More...
 
double maxMinCutRate = 0.0333
 the maximum cut rate for netlist min-cut partitioning More...
 
std::vector< std::pair< int, int > > cluster2XY
 mapping cluster id to X/Y location in the cluster bin More...
 
std::vector< std::pair< float, float > > cluster2FP_XY
 mapping cluster id to floating-point X/Y location on device More...
 
std::vector< std::vector< float > > clusterAdjMat
 
std::vector< float > clusterCLBCellWeights
 
std::vector< float > clusterDSPCellWeights
 
std::vector< float > clusterBRAMCellWeights
 
std::vector< std::vector< float > > cluster2FixedUnitMat
 
std::vector< float > fixedX
 
std::vector< float > fixedY
 
std::vector< int > placementUnit2ClusterId
 
std::vector< int > placementUnitId2ClusterUnitId
 
std::vector< PlacementInfo::ClusterUnit * > clusterUnits
 
std::vector< PlacementInfo::ClusterNet * > clusterNets
 
int clockRegionXNum
 
int clockRegionYNum
 
int jobs
 the parallel (multi-threading) worker number More...
 
SAPlacersaPlacer = nullptr
 simulated-annealing placer for the cluster placement. More...
 
GraphPartitioner< std::vector< PlacementInfo::PlacementUnit * >, std::vector< PlacementInfo::PlacementNet * > > * basicGraphPartitioner = nullptr
 basicGraphPartitioner will conduct partitioning at the PlacementUnit level considering connectivity and resource demand More...
 
GraphPartitioner< std::vector< PlacementInfo::ClusterUnit * >, std::vector< PlacementInfo::ClusterNet * > > * userDefinedClusterBasedGraphPartitioner = nullptr
 userDefinedClusterBasedGraphPartitioner will conduct partitioning at the Cluster level considering connectivity and resource demand. The input clusters are obtained by user-defined information More...
 
GraphPartitioner< std::vector< PlacementInfo::ClusterUnit * >, std::vector< PlacementInfo::ClusterNet * > > * clockBasedGraphPartitioner = nullptr
 clockBasedGraphPartitioner will conduct partitioning at the Cluster level considering connectivity and resource demand. The input clusters are obtained by clock domain. More...
 

Detailed Description

ClusterPlacer will cluster nodes in the given netlist and place the clusters on the device based on simulated-annealing as initial placement.

Definition at line 53 of file ClusterPlacer.h.

Constructor & Destructor Documentation

◆ ClusterPlacer()

ClusterPlacer::ClusterPlacer ( PlacementInfo placementInfo,
std::map< std::string, std::string > &  JSONCfg,
float  connectionToFixedFactor = 5.0 
)

Construct a new Cluster Placer object.

Parameters
placementInfothe PlacementInfo for this placer to handle
JSONCfgthe user-defined placement configuration
connectionToFixedFactorthe enhancement ratio of the net between elements and I/Os

Definition at line 33 of file ClusterPlacer.cc.

◆ ~ClusterPlacer()

ClusterPlacer::~ClusterPlacer ( )
inline

Definition at line 65 of file ClusterPlacer.h.

Member Function Documentation

◆ basicPartitioning()

void ClusterPlacer::basicPartitioning ( int  minClusterCellNum,
int  eachClusterDSPNum,
int  eachClusterBRAMNum 
)
private

pure connectivity-based partitioning based on PaToH

Parameters
minClusterCellNumminimum number of cells in a cluster
eachClusterDSPNummaximum number of DSP cells in a cluster
eachClusterBRAMNummaximum number of BRAM cells in a cluster

Definition at line 338 of file ClusterPlacer.cc.

Here is the call graph for this function:

◆ clockBasedPartitioning()

void ClusterPlacer::clockBasedPartitioning ( int  minClusterCellNum,
int  eachClusterDSPNum,
int  eachClusterBRAMNum 
)
private

initially cluster cells based on clock domains and conduct connectivity-based partitioning based on PaToH

Parameters
minClusterCellNumminimum number of cells in a cluster
eachClusterDSPNummaximum number of DSP cells in a cluster
eachClusterBRAMNummaximum number of BRAM cells in a cluster

Definition at line 399 of file ClusterPlacer.cc.

Referenced by hypergraphPartitioning().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ ClusterPlacement()

void ClusterPlacer::ClusterPlacement ( )

conduct cluster placement, cluster nodes in the given netlist and place the clusters on the device as initial placement.

Definition at line 60 of file ClusterPlacer.cc.

Referenced by GlobalPlacer::clusterPlacement().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ clusterPlacementUnits()

void ClusterPlacer::clusterPlacementUnits ( )
private

cluster the netlist and create ClusterUnit level netlist for SA placement

Definition at line 100 of file ClusterPlacer.cc.

Referenced by ClusterPlacement().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ creaeClusterNets()

void ClusterPlacer::creaeClusterNets ( )
inlineprivate

construct the netlist of the generated clusters based on the PlacementNet in PlacementInfo

Definition at line 225 of file ClusterPlacer.h.

Referenced by clockBasedPartitioning(), and createUserDefinedClusterBasedClusterUnits().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ createClockBasedClusterUnits()

void ClusterPlacer::createClockBasedClusterUnits ( )
private

initially cluster cells based on clock domains

Definition at line 235 of file ClusterPlacer.cc.

Referenced by clockBasedPartitioning().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ createLongPathClusterUnits()

void ClusterPlacer::createLongPathClusterUnits ( )
private

initially cluster cells based on user-defined clusters

Definition at line 144 of file ClusterPlacer.cc.

Referenced by clockBasedPartitioning().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ createSinglePUClusterUnits()

void ClusterPlacer::createSinglePUClusterUnits ( )
private

wrap single PlacementUnits into ClusterUnit for later uniform processing

Definition at line 324 of file ClusterPlacer.cc.

Referenced by clockBasedPartitioning(), and createUserDefinedClusterBasedClusterUnits().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ createUserDefinedClusterBasedClusterUnits()

void ClusterPlacer::createUserDefinedClusterBasedClusterUnits ( )
private

initially cluster cells based on user-defined clusters

Definition at line 269 of file ClusterPlacer.cc.

Referenced by userDefinedClusterBasedPartitioning().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ drawClusters()

void ClusterPlacer::drawClusters ( )
private

Definition at line 843 of file ClusterPlacer.cc.

Referenced by ClusterPlacement().

Here is the caller graph for this function:

◆ dumpClusters()

void ClusterPlacer::dumpClusters ( )
private

Definition at line 777 of file ClusterPlacer.cc.

Referenced by ClusterPlacement().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ getPlacementUnitMaxPathLen()

int ClusterPlacer::getPlacementUnitMaxPathLen ( PlacementInfo::PlacementUnit curPU)
inlineprivate

Definition at line 340 of file ClusterPlacer.h.

Referenced by setClusterNetsAdjMat().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ hypergraphPartitioning()

void ClusterPlacer::hypergraphPartitioning ( )
private

call specific partitioners to partition the design netlist into clusters for initial placement

Definition at line 113 of file ClusterPlacer.cc.

Referenced by clusterPlacementUnits().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ isClustersToLarges()

bool ClusterPlacer::isClustersToLarges ( )
private

check whether the average size of clusters is greater than the given threshold

Returns
true if the granularity is too high
false if the granularity is under constraints

Definition at line 527 of file ClusterPlacer.cc.

Referenced by hypergraphPartitioning().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ isDensePlacement()

bool ClusterPlacer::isDensePlacement ( )
inlineprivate

Definition at line 203 of file ClusterPlacer.h.

Referenced by setClusterNetsAdjMat().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ placeClusters()

void ClusterPlacer::placeClusters ( )
private

conduct the ClusterUnit level SA placement and then map PlacementUnit to cluster location

Definition at line 709 of file ClusterPlacer.cc.

Referenced by ClusterPlacement().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ placeUnitBaseOnClusterPlacement()

void ClusterPlacer::placeUnitBaseOnClusterPlacement ( const std::vector< std::pair< int, int >> &  cluster2XY)
private

map PlacementUnit to cluster location

Parameters
cluster2XYthe cluster location at grid level

Definition at line 740 of file ClusterPlacer.cc.

Referenced by placeClusters().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ random_float()

float ClusterPlacer::random_float ( float  min,
float  max 
)
inlineprivate

Definition at line 366 of file ClusterPlacer.h.

Referenced by ClusterPlacement().

Here is the caller graph for this function:

◆ refineClustersWithPredefinedClusters()

void ClusterPlacer::refineClustersWithPredefinedClusters ( )
private

refine the elements in obtained clusters to ensure the cells in user-defined clusters in the same cluster

It seems that this refining solution work poorly. Might be abandoned in the future.

Definition at line 457 of file ClusterPlacer.cc.

Here is the call graph for this function:

◆ resetClusterInfo()

void ClusterPlacer::resetClusterInfo ( )
inlineprivate

clean all information of the clusters (including PlacementUnit-Cluster mapping and the cluster-level netlist)

Definition at line 214 of file ClusterPlacer.h.

Referenced by clockBasedPartitioning().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ setClusterNetsAdjMat()

void ClusterPlacer::setClusterNetsAdjMat ( )
private

construct the cluster nets adjacent matrix for simulated-annealing cluster placement

Definition at line 593 of file ClusterPlacer.cc.

Referenced by clusterPlacementUnits().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ userDefinedClusterBasedPartitioning()

void ClusterPlacer::userDefinedClusterBasedPartitioning ( int  minClusterCellNum,
int  eachClusterDSPNum,
int  eachClusterBRAMNum 
)
private

initially cluster cells based on user-defined clusters and conduct connectivity-based partitioning based on PaToH

Parameters
minClusterCellNumminimum number of cells in a cluster
eachClusterDSPNummaximum number of DSP cells in a cluster
eachClusterBRAMNummaximum number of BRAM cells in a cluster

Definition at line 361 of file ClusterPlacer.cc.

Here is the call graph for this function:

Member Data Documentation

◆ avgClusterSizeRequirement

int ClusterPlacer::avgClusterSizeRequirement = 40000
private

the requirement of the average size of clusters (the number of cells)

Definition at line 125 of file ClusterPlacer.h.

Referenced by hypergraphPartitioning(), and isClustersToLarges().

◆ basicGraphPartitioner

GraphPartitioner<std::vector<PlacementInfo::PlacementUnit *>, std::vector<PlacementInfo::PlacementNet *> >* ClusterPlacer::basicGraphPartitioner = nullptr
private

basicGraphPartitioner will conduct partitioning at the PlacementUnit level considering connectivity and resource demand

Definition at line 185 of file ClusterPlacer.h.

Referenced by basicPartitioning(), and ~ClusterPlacer().

◆ clockBasedGraphPartitioner

GraphPartitioner<std::vector<PlacementInfo::ClusterUnit *>, std::vector<PlacementInfo::ClusterNet *> >* ClusterPlacer::clockBasedGraphPartitioner = nullptr
private

clockBasedGraphPartitioner will conduct partitioning at the Cluster level considering connectivity and resource demand. The input clusters are obtained by clock domain.

Definition at line 201 of file ClusterPlacer.h.

Referenced by clockBasedPartitioning().

◆ clockRegionXNum

int ClusterPlacer::clockRegionXNum
private

Definition at line 162 of file ClusterPlacer.h.

Referenced by ClusterPlacer(), and setClusterNetsAdjMat().

◆ clockRegionYNum

int ClusterPlacer::clockRegionYNum
private

Definition at line 162 of file ClusterPlacer.h.

Referenced by ClusterPlacer().

◆ cluster2FixedUnitMat

std::vector<std::vector<float> > ClusterPlacer::cluster2FixedUnitMat
private

Definition at line 152 of file ClusterPlacer.h.

Referenced by placeClusters(), and setClusterNetsAdjMat().

◆ cluster2FP_XY

std::vector<std::pair<float, float> > ClusterPlacer::cluster2FP_XY
private

mapping cluster id to floating-point X/Y location on device

Definition at line 143 of file ClusterPlacer.h.

Referenced by placeUnitBaseOnClusterPlacement().

◆ cluster2XY

std::vector<std::pair<int, int> > ClusterPlacer::cluster2XY
private

mapping cluster id to X/Y location in the cluster bin

Definition at line 137 of file ClusterPlacer.h.

Referenced by dumpClusters(), placeClusters(), and placeUnitBaseOnClusterPlacement().

◆ clusterAdjMat

std::vector<std::vector<float> > ClusterPlacer::clusterAdjMat
private

Definition at line 147 of file ClusterPlacer.h.

Referenced by drawClusters(), placeClusters(), and setClusterNetsAdjMat().

◆ clusterBRAMCellWeights

std::vector<float> ClusterPlacer::clusterBRAMCellWeights
private

Definition at line 150 of file ClusterPlacer.h.

Referenced by setClusterNetsAdjMat().

◆ clusterCLBCellWeights

std::vector<float> ClusterPlacer::clusterCLBCellWeights
private

Definition at line 148 of file ClusterPlacer.h.

Referenced by placeClusters(), and setClusterNetsAdjMat().

◆ clusterDSPCellWeights

std::vector<float> ClusterPlacer::clusterDSPCellWeights
private

Definition at line 149 of file ClusterPlacer.h.

Referenced by setClusterNetsAdjMat().

◆ clusterNets

◆ clusters

std::vector<std::set<int> > ClusterPlacer::clusters
private

the resultant clusters of PlacementUnit (id)

a vector of the sets of PlacementUnit Id ==> clusters of PlacementUnit id

Definition at line 103 of file ClusterPlacer.h.

Referenced by basicPartitioning(), clockBasedPartitioning(), clusterPlacementUnits(), dumpClusters(), hypergraphPartitioning(), isClustersToLarges(), isDensePlacement(), refineClustersWithPredefinedClusters(), setClusterNetsAdjMat(), and userDefinedClusterBasedPartitioning().

◆ clusterUnits

◆ connectionToFixedFactor

float ClusterPlacer::connectionToFixedFactor
private

the enhancement ratio of the net between elements and I/Os

Definition at line 110 of file ClusterPlacer.h.

Referenced by placeClusters().

◆ fixedX

std::vector<float> ClusterPlacer::fixedX
private

Definition at line 153 of file ClusterPlacer.h.

Referenced by placeClusters(), and setClusterNetsAdjMat().

◆ fixedY

std::vector<float> ClusterPlacer::fixedY
private

Definition at line 154 of file ClusterPlacer.h.

Referenced by placeClusters(), and setClusterNetsAdjMat().

◆ jobs

int ClusterPlacer::jobs
private

the parallel (multi-threading) worker number

Definition at line 168 of file ClusterPlacer.h.

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

◆ JSONCfg

std::map<std::string, std::string>& ClusterPlacer::JSONCfg
private

◆ maxMinCutRate

double ClusterPlacer::maxMinCutRate = 0.0333
private

the maximum cut rate for netlist min-cut partitioning

Definition at line 131 of file ClusterPlacer.h.

Referenced by basicPartitioning(), clockBasedPartitioning(), hypergraphPartitioning(), and userDefinedClusterBasedPartitioning().

◆ placementInfo

◆ placementUnit2ClusterId

◆ placementUnitId2ClusterUnitId

std::vector<int> ClusterPlacer::placementUnitId2ClusterUnitId
private

◆ randomInitialPlacement

bool ClusterPlacer::randomInitialPlacement = false
private

◆ saPlacer

SAPlacer* ClusterPlacer::saPlacer = nullptr
private

simulated-annealing placer for the cluster placement.

It will map the clusters to different cluster bins and try to minimize the rough total wirelength between the clusters.

Definition at line 177 of file ClusterPlacer.h.

Referenced by placeClusters(), and ~ClusterPlacer().

◆ userDefinedClusterBasedGraphPartitioner

GraphPartitioner<std::vector<PlacementInfo::ClusterUnit *>, std::vector<PlacementInfo::ClusterNet *> >* ClusterPlacer::userDefinedClusterBasedGraphPartitioner = nullptr
private

userDefinedClusterBasedGraphPartitioner will conduct partitioning at the Cluster level considering connectivity and resource demand. The input clusters are obtained by user-defined information

Definition at line 193 of file ClusterPlacer.h.

Referenced by userDefinedClusterBasedPartitioning(), and ~ClusterPlacer().

◆ verbose

bool ClusterPlacer::verbose
private

◆ y2xRatio

float ClusterPlacer::y2xRatio = 1.0
private

the Y/X coordinate calibration factor

Definition at line 116 of file ClusterPlacer.h.

Referenced by ClusterPlacer(), and placeClusters().


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