SpreadRegion is an object that record cell spreading region information, including boundaries, cells, bins, and spreading boxes. More...

#include <GeneralSpreader.h>

Collaboration diagram for GeneralSpreader::SpreadRegion:

[legend]

Classes
struct	expandOp
	a struct to describe the expanding operation for the SpreadRegion More...

class	SubBox
	SubBox is the exact container which is the object for bi-partitioning-based cell spreading. More...

Public Types
enum	dirType { expandLeft, expandRight, expandUp, expandDown }
	four direction options to expand the SpreadRegion More...

Public Member Functions
	SpreadRegion (PlacementInfo::PlacementBinInfo curBin, PlacementInfo placementInfo, std::vector< std::vector< PlacementInfo::PlacementBinInfo * >> &binGrid, float capacityShrinkRatio)
	Construct a new Spread Region object. More...

	~SpreadRegion ()

bool	isRegionOverlap (int tmpRegionTopBinY, int tmpRegionBottomBinY, int tmpRegionLeftBinX, int tmpRegionRightBinX)
	check whether the SpreadRegion is overlapped with a given boundary More...

bool	isRegionOverlap (SpreadRegion *anotherRegion)
	check whether overlapped with another SpreadRegion More...

void	addBinRegion (int newRegionTopBinY, int newRegionBottomBinY, int newRegionLeftBinX, int newRegionRightBinX, std::set< PlacementInfo::PlacementBinInfo * > &coveredBinSet)
	add cell bins into SpreadRegion with a new boundary and update region information including boundary and the sets of cells and bins More...

std::vector< PlacementInfo::PlacementBinInfo * > &	getBinsInRegion ()
	Get the bins in the SpreadRegion. More...

bool	isOverflow ()
	check whether the resource in this region is less than the requirement More...

bool	isCovered (int newTopBinY, int newBottomBinY, int newLeftBinX, int newRightBinX, dirType tmpDir, std::set< PlacementInfo::PlacementBinInfo * > &coveredBinSet)
	check whether an expansion in a given direction will make the SpreadRegion overlapped with some bins in another SpreadRegion More...

void	getDirCapacityAndUtilization (int newTopBinY, int newBottomBinY, int newLeftBinX, int newRightBinX, dirType tmpDir, float &tmpUtilization, float &tmpCapacity)
	evaluation the utilization and capacity of the incoming bins which will be included in the SpreadRegion after an expansion . More...

bool	smartFindExpandDirection (std::set< PlacementInfo::PlacementBinInfo * > &coveredBinSet)
	find the legal expansion direction More...

bool	expandable (int tmpDir)

void	smartExpand (std::set< PlacementInfo::PlacementBinInfo * > &coveredBinSet)
	select the expansion direction greedily More...

bool	simpleFindExpandDirection (std::set< PlacementInfo::PlacementBinInfo * > &coveredBinSet)
	find the expansion direction iteratively in pre-defined order More...

void	simpleExpand (std::set< PlacementInfo::PlacementBinInfo * > &coveredBinSet)
	select the the expansion direction which is found in a pre-defined order More...

bool	contains (PlacementInfo::PlacementBinInfo *curBin)
	check whether SpreadRegion contains the given bin More...

std::vector< DesignInfo::DesignCell * > &	getCells ()
	Get the cells in the SpreadRegion. More...

int	top ()
	get the top bin coordinate Y of the SpreadRegion in bin grid More...

int	bottom ()
	get the bottom bin coordinate Y of the SpreadRegion in bin grid More...

int	left ()
	get the left bin coordinate X of the SpreadRegion in bin grid More...

int	right ()
	get the right bin coordinate X of the SpreadRegion in bin grid More...

float	getOverflowRatio ()
	Get the resource overflow ratio. More...

Public Attributes
expandOp	expandOps [4] = {{0, 0, -1, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}, {0, -1, 0, 0}}

expandOp	actualExpandOps [4]

Static Public Attributes
static constexpr float	eps = 1e-4

Private Attributes
PlacementInfo *	placementInfo

float	totalCapacity

float	totalUtilization

float	overflowRatio

int	topBinY

int	bottomBinY

int	leftBinX

int	rightBinX

int	curDirectionIndex = 0
	record the last selection of expansion direction for later expansion More...

dirType	curDirection = expandLeft
	make the direction into enum type for clearer identification More...

std::vector< std::vector< PlacementInfo::PlacementBinInfo * > > &	binGrid
	a reference of the global bin grid for data accessing and updating of cell density More...

float	dir2utilization [4]
	the utilization of the four directions (absolute value) More...

float	dir2capacity [4]
	the capacity of the four directions (absolute value) More...

bool	legalDir [4]
	a boolean array to record legal directions to expand the SpreadRegion More...

float	capacityShrinkRatio = 1.0

std::set< DesignInfo::DesignCell * >	cellsInRegion
	a set of cells in the SpreadRegion More...

std::vector< DesignInfo::DesignCell * >	cellsInRegionVec
	a vector of cells in the SpreadRegion More...

std::vector< PlacementInfo::PlacementBinInfo * >	binsInRegion
	a vector of bins in the SpreadRegion More...

std::set< PlacementInfo::PlacementBinInfo * >	binSetInRegion
	a set of bins in the SpreadRegion More...

Detailed Description

SpreadRegion is an object that record cell spreading region information, including boundaries, cells, bins, and spreading boxes.

Definition at line 85 of file GeneralSpreader.h.

Member Enumeration Documentation

◆ dirType

enum GeneralSpreader::SpreadRegion::dirType

four direction options to expand the SpreadRegion

Enumerator
expandLeft
expandRight
expandUp
expandDown

Definition at line 196 of file GeneralSpreader.h.

Constructor & Destructor Documentation

◆ SpreadRegion()

GeneralSpreader::SpreadRegion::SpreadRegion	(	PlacementInfo::PlacementBinInfo *	curBin,
		PlacementInfo *	placementInfo,
		std::vector< std::vector< PlacementInfo::PlacementBinInfo * >> &	binGrid,
		float	capacityShrinkRatio
	)

inline

Construct a new Spread Region object.

Parameters

curBin	the initial bin for the SpreadRegion object, which should be overflowed.
placementInfo	PlacementInfo so this object can access the corresponding placement database
binGrid	the reference of the binGrid for cell spreading. A bin grid is used to record the density of cells on the device
capacityShrinkRatio	shrink the area supply to a specific ratio

Definition at line 97 of file GeneralSpreader.h.

Here is the call graph for this function:

◆ ~SpreadRegion()

GeneralSpreader::SpreadRegion::~SpreadRegion ( )

inline

Definition at line 118 of file GeneralSpreader.h.

Member Function Documentation

◆ addBinRegion()

void GeneralSpreader::SpreadRegion::addBinRegion	(	int	newRegionTopBinY,
		int	newRegionBottomBinY,
		int	newRegionLeftBinX,
		int	newRegionRightBinX,
		std::set< PlacementInfo::PlacementBinInfo * > &	coveredBinSet
	)

add cell bins into SpreadRegion with a new boundary and update region information including boundary and the sets of cells and bins

Parameters

newRegionTopBinY
newRegionBottomBinY
newRegionLeftBinX
newRegionRightBinX
coveredBinSet

Definition at line 656 of file GeneralSpreader.cc.

Referenced by simpleExpand(), and smartExpand().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ bottom()

int GeneralSpreader::SpreadRegion::bottom ( )

inline

get the bottom bin coordinate Y of the SpreadRegion in bin grid

Returns: int

Definition at line 779 of file GeneralSpreader.h.

Referenced by isRegionOverlap(), and GeneralSpreader::spreadPlacementUnits().

Here is the caller graph for this function:

◆ contains()

bool GeneralSpreader::SpreadRegion::contains ( PlacementInfo::PlacementBinInfo * curBin )

inline

check whether SpreadRegion contains the given bin

Parameters

curBin a given bin

Returns: true when SpreadRegion contains the given bin; false when SpreadRegion does not contain the given bin

Definition at line 747 of file GeneralSpreader.h.

◆ expandable()

bool GeneralSpreader::SpreadRegion::expandable ( int tmpDir )

inline

Definition at line 478 of file GeneralSpreader.h.

Referenced by smartExpand().

Here is the caller graph for this function:

◆ getBinsInRegion()

std::vector<PlacementInfo::PlacementBinInfo *>& GeneralSpreader::SpreadRegion::getBinsInRegion ( )

inline

Get the bins in the SpreadRegion.

Returns: std::vector<PlacementInfo::PlacementBinInfo *>&

Definition at line 176 of file GeneralSpreader.h.

Referenced by GeneralSpreader::expandFromABin(), and GeneralSpreader::spreadPlacementUnits().

Here is the caller graph for this function:

◆ getCells()

std::vector<DesignInfo::DesignCell *>& GeneralSpreader::SpreadRegion::getCells ( )

inline

Get the cells in the SpreadRegion.

please be aware that a SpreadRegion will only contain cells in a specific type defined by its constructor.

Returns: std::vector<DesignInfo::DesignCell *>&

Definition at line 759 of file GeneralSpreader.h.

Referenced by addBinRegion(), GeneralSpreader::DumpCellsCoordinate(), GeneralSpreader::spreadPlacementUnits(), and GeneralSpreader::SpreadRegion::SubBox::SubBox().

Here is the caller graph for this function:

◆ getDirCapacityAndUtilization()

void GeneralSpreader::SpreadRegion::getDirCapacityAndUtilization	(	int	newTopBinY,
		int	newBottomBinY,
		int	newLeftBinX,
		int	newRightBinX,
		dirType	tmpDir,
		float &	tmpUtilization,
		float &	tmpCapacity
	)

inline

evaluation the utilization and capacity of the incoming bins which will be included in the SpreadRegion after an expansion .

Parameters

newTopBinY	the top boundary after expansion
newBottomBinY	the bottom boundary after expansion
newLeftBinX	the left boundary after expansion
newRightBinX	the right boundary after expansion
tmpDir	a given direction
tmpUtilization	the resultant utilization
tmpCapacity	the resultant capacity

Definition at line 319 of file GeneralSpreader.h.

Referenced by smartFindExpandDirection().

Here is the caller graph for this function:

◆ getOverflowRatio()

float GeneralSpreader::SpreadRegion::getOverflowRatio ( )

inline

Get the resource overflow ratio.

Returns: float

Definition at line 809 of file GeneralSpreader.h.

Referenced by GeneralSpreader::expandFromABin().

Here is the caller graph for this function:

◆ isCovered()

bool GeneralSpreader::SpreadRegion::isCovered	(	int	newTopBinY,
		int	newBottomBinY,
		int	newLeftBinX,
		int	newRightBinX,
		dirType	tmpDir,
		std::set< PlacementInfo::PlacementBinInfo * > &	coveredBinSet
	)

inline

check whether an expansion in a given direction will make the SpreadRegion overlapped with some bins in another SpreadRegion

Parameters

newTopBinY	the top boundary after expansion
newBottomBinY	the bottom boundary after expansion
newLeftBinX	the left boundary after expansion
newRightBinX	the right boundary after expansion
tmpDir	a given direction
coveredBinSet	a set of bins which have been included in other SpreadRegion

Returns: true when the expansion will be overlapped with some bins in another SpreadRegion; false when the expansion will NOT be overlapped with some bins in another SpreadRegion

Definition at line 269 of file GeneralSpreader.h.

Referenced by simpleFindExpandDirection(), and smartFindExpandDirection().

Here is the caller graph for this function:

◆ isOverflow()

bool GeneralSpreader::SpreadRegion::isOverflow ( )

inline

check whether the resource in this region is less than the requirement

Returns: true when the resource in this region is less than the requirement; false when the resource in this region is more than the requirement

Definition at line 187 of file GeneralSpreader.h.

◆ isRegionOverlap() [1/2]

bool GeneralSpreader::SpreadRegion::isRegionOverlap	(	int	tmpRegionTopBinY,
		int	tmpRegionBottomBinY,
		int	tmpRegionLeftBinX,
		int	tmpRegionRightBinX
	)

inline

check whether the SpreadRegion is overlapped with a given boundary

Parameters

tmpRegionTopBinY
tmpRegionBottomBinY
tmpRegionLeftBinX
tmpRegionRightBinX

Returns: true when overlapped; false when not overlapped

Definition at line 132 of file GeneralSpreader.h.

Referenced by addBinRegion().

Here is the caller graph for this function:

◆ isRegionOverlap() [2/2]

bool GeneralSpreader::SpreadRegion::isRegionOverlap ( SpreadRegion * anotherRegion )

inline

check whether overlapped with another SpreadRegion

Parameters

anotherRegion another SpreadRegion object

Returns: true when overlapped; false when not overlapped

Definition at line 149 of file GeneralSpreader.h.

Here is the call graph for this function:

◆ left()

int GeneralSpreader::SpreadRegion::left ( )

inline

get the left bin coordinate X of the SpreadRegion in bin grid

Returns: int

Definition at line 789 of file GeneralSpreader.h.

Referenced by isRegionOverlap(), and GeneralSpreader::spreadPlacementUnits().

Here is the caller graph for this function:

◆ right()

int GeneralSpreader::SpreadRegion::right ( )

inline

get the right bin coordinate X of the SpreadRegion in bin grid

Returns: int

Definition at line 799 of file GeneralSpreader.h.

Referenced by isRegionOverlap(), and GeneralSpreader::spreadPlacementUnits().

Here is the caller graph for this function:

◆ simpleExpand()

void GeneralSpreader::SpreadRegion::simpleExpand ( std::set< PlacementInfo::PlacementBinInfo * > & coveredBinSet )

inline

select the the expansion direction which is found in a pre-defined order

Parameters

coveredBinSet a set of bins which have been included in other SpreadRegion

Definition at line 724 of file GeneralSpreader.h.

Referenced by GeneralSpreader::expandFromABin().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ simpleFindExpandDirection()

bool GeneralSpreader::SpreadRegion::simpleFindExpandDirection ( std::set< PlacementInfo::PlacementBinInfo * > & coveredBinSet )

inline

find the expansion direction iteratively in pre-defined order

Parameters

coveredBinSet a set of bins which have been included in other SpreadRegion

Returns: true when there is legal direction to expand the SpreadRegion; false when there is NO legal direction to expand the SpreadRegion

Definition at line 689 of file GeneralSpreader.h.

Referenced by GeneralSpreader::expandFromABin().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ smartExpand()

void GeneralSpreader::SpreadRegion::smartExpand ( std::set< PlacementInfo::PlacementBinInfo * > & coveredBinSet )

inline

select the expansion direction greedily

evaluate the 4 potential directions and select the direction, which can significantly reduce the overflow, to conduct expansion

Parameters

coveredBinSet a set of bins which have been included in other SpreadRegion

Definition at line 491 of file GeneralSpreader.h.

Referenced by GeneralSpreader::expandFromABin().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ smartFindExpandDirection()

bool GeneralSpreader::SpreadRegion::smartFindExpandDirection ( std::set< PlacementInfo::PlacementBinInfo * > & coveredBinSet )

inline

find the legal expansion direction

evaluate the utilization/capacity of 4 legal directions

Parameters

coveredBinSet a set of bins which have been included in other SpreadRegion

Returns: true when there is legal direction to expand the SpreadRegion; false when there is NO legal direction to expand the SpreadRegion

Definition at line 375 of file GeneralSpreader.h.

Referenced by GeneralSpreader::expandFromABin().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ top()

int GeneralSpreader::SpreadRegion::top ( )

inline

get the top bin coordinate Y of the SpreadRegion in bin grid

Returns: int

Definition at line 769 of file GeneralSpreader.h.

Referenced by isRegionOverlap(), and GeneralSpreader::spreadPlacementUnits().

Here is the caller graph for this function:

Member Data Documentation

◆ actualExpandOps

expandOp GeneralSpreader::SpreadRegion::actualExpandOps[4]

Definition at line 254 of file GeneralSpreader.h.

Referenced by smartExpand(), and smartFindExpandDirection().

◆ binGrid

std::vector<std::vector<PlacementInfo::PlacementBinInfo *> >& GeneralSpreader::SpreadRegion::binGrid

private

a reference of the global bin grid for data accessing and updating of cell density

Definition at line 1099 of file GeneralSpreader.h.

Referenced by addBinRegion(), getDirCapacityAndUtilization(), isCovered(), simpleFindExpandDirection(), and smartFindExpandDirection().

◆ binSetInRegion

std::set<PlacementInfo::PlacementBinInfo *> GeneralSpreader::SpreadRegion::binSetInRegion

private

a set of bins in the SpreadRegion

Definition at line 1146 of file GeneralSpreader.h.

Referenced by addBinRegion(), contains(), and SpreadRegion().

◆ binsInRegion

std::vector<PlacementInfo::PlacementBinInfo *> GeneralSpreader::SpreadRegion::binsInRegion

private

a vector of bins in the SpreadRegion

vector can ensure the iteration order to get rid of random factors in multi-threading

Definition at line 1140 of file GeneralSpreader.h.

Referenced by addBinRegion(), getBinsInRegion(), and SpreadRegion().

◆ bottomBinY

int GeneralSpreader::SpreadRegion::bottomBinY

private

Definition at line 1080 of file GeneralSpreader.h.

Referenced by addBinRegion(), bottom(), isRegionOverlap(), simpleExpand(), simpleFindExpandDirection(), smartExpand(), smartFindExpandDirection(), and SpreadRegion().

◆ capacityShrinkRatio

float GeneralSpreader::SpreadRegion::capacityShrinkRatio = 1.0

private

Definition at line 1120 of file GeneralSpreader.h.

Referenced by smartExpand().

◆ cellsInRegion

std::set<DesignInfo::DesignCell *> GeneralSpreader::SpreadRegion::cellsInRegion

private

a set of cells in the SpreadRegion

Definition at line 1126 of file GeneralSpreader.h.

Referenced by addBinRegion(), and SpreadRegion().

◆ cellsInRegionVec

std::vector<DesignInfo::DesignCell *> GeneralSpreader::SpreadRegion::cellsInRegionVec

private

a vector of cells in the SpreadRegion

vector can ensure the iteration order to get rid of random factors in multi-threading

Definition at line 1133 of file GeneralSpreader.h.

Referenced by addBinRegion(), getCells(), and SpreadRegion().

◆ curDirection

dirType GeneralSpreader::SpreadRegion::curDirection = expandLeft

private

make the direction into enum type for clearer identification

Definition at line 1093 of file GeneralSpreader.h.

Referenced by simpleExpand(), and simpleFindExpandDirection().

◆ curDirectionIndex

int GeneralSpreader::SpreadRegion::curDirectionIndex = 0

private

record the last selection of expansion direction for later expansion

Definition at line 1087 of file GeneralSpreader.h.

Referenced by simpleFindExpandDirection().

◆ dir2capacity

float GeneralSpreader::SpreadRegion::dir2capacity[4]

private

the capacity of the four directions (absolute value)

Definition at line 1111 of file GeneralSpreader.h.

Referenced by smartExpand(), and smartFindExpandDirection().

◆ dir2utilization

float GeneralSpreader::SpreadRegion::dir2utilization[4]

private

the utilization of the four directions (absolute value)

Definition at line 1105 of file GeneralSpreader.h.

Referenced by smartExpand(), and smartFindExpandDirection().

◆ eps

constexpr float GeneralSpreader::SpreadRegion::eps = 1e-4

staticconstexpr

Definition at line 1073 of file GeneralSpreader.h.

◆ expandOps

expandOp GeneralSpreader::SpreadRegion::expandOps[4] = {{0, 0, -1, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}, {0, -1, 0, 0}}

Definition at line 253 of file GeneralSpreader.h.

Referenced by simpleExpand(), simpleFindExpandDirection(), and smartFindExpandDirection().

◆ leftBinX

int GeneralSpreader::SpreadRegion::leftBinX

private

Definition at line 1081 of file GeneralSpreader.h.

Referenced by addBinRegion(), isRegionOverlap(), left(), simpleExpand(), simpleFindExpandDirection(), smartExpand(), smartFindExpandDirection(), and SpreadRegion().

◆ legalDir

bool GeneralSpreader::SpreadRegion::legalDir[4]

private

a boolean array to record legal directions to expand the SpreadRegion

legal direction means that

Definition at line 1119 of file GeneralSpreader.h.

Referenced by expandable(), and smartFindExpandDirection().

◆ overflowRatio

float GeneralSpreader::SpreadRegion::overflowRatio

private

Definition at line 1079 of file GeneralSpreader.h.

Referenced by addBinRegion(), getOverflowRatio(), isOverflow(), and SpreadRegion().

◆ placementInfo

PlacementInfo* GeneralSpreader::SpreadRegion::placementInfo

private

Definition at line 1076 of file GeneralSpreader.h.

◆ rightBinX

int GeneralSpreader::SpreadRegion::rightBinX

private

Definition at line 1081 of file GeneralSpreader.h.

Referenced by addBinRegion(), isRegionOverlap(), right(), simpleExpand(), simpleFindExpandDirection(), smartExpand(), smartFindExpandDirection(), and SpreadRegion().

◆ topBinY

int GeneralSpreader::SpreadRegion::topBinY

private

Definition at line 1080 of file GeneralSpreader.h.

Referenced by addBinRegion(), isRegionOverlap(), simpleExpand(), simpleFindExpandDirection(), smartExpand(), smartFindExpandDirection(), SpreadRegion(), and top().

◆ totalCapacity

float GeneralSpreader::SpreadRegion::totalCapacity

private

Definition at line 1077 of file GeneralSpreader.h.

Referenced by addBinRegion(), smartExpand(), and SpreadRegion().

◆ totalUtilization

float GeneralSpreader::SpreadRegion::totalUtilization

private

Definition at line 1078 of file GeneralSpreader.h.

Referenced by addBinRegion(), smartExpand(), and SpreadRegion().

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

src/lib/HiFPlacer/placement/globalPlacement/GeneralSpreader.h
src/lib/HiFPlacer/placement/globalPlacement/GeneralSpreader.cc

Classes

Public Types

Public Member Functions

Public Attributes

Static Public Attributes

Private Attributes

Detailed Description

Member Enumeration Documentation

◆ dirType

Constructor & Destructor Documentation

◆ SpreadRegion()

◆ ~SpreadRegion()

Member Function Documentation

◆ addBinRegion()

◆ bottom()

◆ contains()

◆ expandable()

◆ getBinsInRegion()

◆ getCells()

◆ getDirCapacityAndUtilization()

◆ getOverflowRatio()

◆ isCovered()

◆ isOverflow()

◆ isRegionOverlap() [1/2]

◆ isRegionOverlap() [2/2]

◆ left()

◆ right()

◆ simpleExpand()

◆ simpleFindExpandDirection()

◆ smartExpand()

◆ smartFindExpandDirection()

◆ top()

Member Data Documentation

◆ actualExpandOps

◆ binGrid

◆ binSetInRegion

◆ binsInRegion

◆ bottomBinY

◆ capacityShrinkRatio

◆ cellsInRegion

◆ cellsInRegionVec

◆ curDirection

◆ curDirectionIndex

◆ dir2capacity

◆ dir2utilization

◆ eps

◆ expandOps

◆ leftBinX

◆ legalDir

◆ overflowRatio

◆ placementInfo

◆ rightBinX

◆ topBinY

◆ totalCapacity

◆ totalUtilization