GeneralSpreader.h

Go to the documentation of this file.

 
#ifndef _GENERALSPREADER
#define _GENERALSPREADER
 
#include "DesignInfo.h"
#include "DeviceInfo.h"
#include "PlacementInfo.h"
#include "const.h"
#include "dumpZip.h"
#include <assert.h>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <vector>
 
class GeneralSpreader
{
  public:
    GeneralSpreader(PlacementInfo *placementInfo, std::map<std::string, std::string> &JSONCfg,
                    std::string &sharedCellType, int currentIteration, float capacityShrinkRatio, bool verbose = true);
    ~GeneralSpreader()
    {
    }
 
    void spreadPlacementUnits(float forgetRatio, bool enableClockRegionAware = false, float displacementLimit = -10,
                              unsigned int spreadRegionBinSizeLimit = 1000000);
    void dumpLUTFFCoordinate();
 
    class SpreadRegion
    {
      public:
        SpreadRegion(PlacementInfo::PlacementBinInfo *curBin, PlacementInfo *placementInfo,
                     std::vector<std::vector<PlacementInfo::PlacementBinInfo *>> &binGrid, float capacityShrinkRatio)
            : placementInfo(placementInfo), binGrid(binGrid), capacityShrinkRatio(capacityShrinkRatio)
        {
            topBinY = bottomBinY = curBin->Y();
            leftBinX = rightBinX = curBin->X();
            cellsInRegion.clear();
            binsInRegion.clear();
            cellsInRegionVec.clear();
            binSetInRegion.clear();
            binsInRegion.push_back(curBin);
            binSetInRegion.insert(curBin);
            for (auto curCell : curBin->getCells())
            {
                cellsInRegion.insert(curCell);
                cellsInRegionVec.push_back(curCell);
            }
            totalCapacity = curBin->getCapacity();
            totalUtilization = curBin->getUtilization();
            overflowRatio = totalUtilization / totalCapacity;
        }
        ~SpreadRegion()
        {
        }
 
        inline bool isRegionOverlap(int tmpRegionTopBinY, int tmpRegionBottomBinY, int tmpRegionLeftBinX,
                                    int tmpRegionRightBinX)
        {
            if (leftBinX > tmpRegionRightBinX || tmpRegionLeftBinX > rightBinX)
                return false;
            if (topBinY < tmpRegionBottomBinY || tmpRegionTopBinY < bottomBinY)
                return false;
            return true;
        }
 
        inline bool isRegionOverlap(SpreadRegion *anotherRegion)
        {
            if (leftBinX > anotherRegion->right() || anotherRegion->left() > rightBinX)
                return false;
            if (topBinY < anotherRegion->bottom() || anotherRegion->top() < bottomBinY)
                return false;
            return true;
        }
 
        void addBinRegion(int newRegionTopBinY, int newRegionBottomBinY, int newRegionLeftBinX, int newRegionRightBinX,
                          std::set<PlacementInfo::PlacementBinInfo *> &coveredBinSet);
 
        inline std::vector<PlacementInfo::PlacementBinInfo *> &getBinsInRegion()
        {
            return binsInRegion;
        }
 
        inline bool isOverflow()
        {
            return overflowRatio > 1.0;
        }
 
        enum dirType
        {
            expandLeft,
            expandRight,
            expandUp,
            expandDown
        };
 
        struct expandOp
        {
            int topYOp, bottomYOp, leftXOp, rightXOp;
 
            expandOp()
            {
            }
 
            expandOp(int topYOp, int bottomYOp, int leftXOp, int rightXOp)
                : topYOp(topYOp), bottomYOp(bottomYOp), leftXOp(leftXOp), rightXOp(rightXOp)
            {
            }
 
            inline expandOp &operator=(const expandOp &a)
            {
                topYOp = a.topYOp;
                bottomYOp = a.bottomYOp;
                leftXOp = a.leftXOp;
                rightXOp = a.rightXOp;
                return *this;
            }
 
            inline expandOp operator+(int x) const
            {
                assert(x == 1);
                if (topYOp)
                    return expandOp(topYOp + 1, bottomYOp, leftXOp, rightXOp);
                if (bottomYOp)
                    return expandOp(topYOp, bottomYOp - 1, leftXOp, rightXOp);
                if (leftXOp)
                    return expandOp(topYOp, bottomYOp, leftXOp - 1, rightXOp);
                if (rightXOp)
                    return expandOp(topYOp, bottomYOp, leftXOp, rightXOp + 1);
                assert(false && "should not reach here");
                return expandOp(topYOp * x, bottomYOp * x, leftXOp * x, rightXOp * x);
            }
        };
 
        // topBinY, bottomBinY, leftBinX, rightBinX;
        expandOp expandOps[4] = {{0, 0, -1, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}, {0, -1, 0, 0}};
        expandOp actualExpandOps[4];
 
        inline bool isCovered(int newTopBinY, int newBottomBinY, int newLeftBinX, int newRightBinX, dirType tmpDir,
                              std::set<PlacementInfo::PlacementBinInfo *> &coveredBinSet)
        {
            if (tmpDir == expandUp)
            {
                for (int binX = newLeftBinX; binX <= newRightBinX; binX++)
                {
                    if (coveredBinSet.find(binGrid[newTopBinY][binX]) != coveredBinSet.end())
                        return true;
                }
            }
            else if (tmpDir == expandDown)
            {
                for (int binX = newLeftBinX; binX <= newRightBinX; binX++)
                {
                    if (coveredBinSet.find(binGrid[newBottomBinY][binX]) != coveredBinSet.end())
                        return true;
                }
            }
            else if (tmpDir == expandLeft)
            {
                for (int binY = newBottomBinY; binY <= newTopBinY; binY++)
                {
                    if (coveredBinSet.find(binGrid[binY][newLeftBinX]) != coveredBinSet.end())
                        return true;
                }
            }
            else if (tmpDir == expandRight)
            {
                for (int binY = newBottomBinY; binY <= newTopBinY; binY++)
                {
                    if (coveredBinSet.find(binGrid[binY][newRightBinX]) != coveredBinSet.end())
                        return true;
                }
            }
            return false;
        }
 
        inline void getDirCapacityAndUtilization(int newTopBinY, int newBottomBinY, int newLeftBinX, int newRightBinX,
                                                 dirType tmpDir, float &tmpUtilization, float &tmpCapacity)
        {
            // tmpCapacity = 0.0;
            // tmpUtilization = 0.0;
            if (tmpDir == expandUp)
            {
                //  for (int binY = newBottomBinY; binY <= newTopBinY; binY++)
                for (int binX = newLeftBinX; binX <= newRightBinX; binX++)
                {
                    tmpCapacity += binGrid[newTopBinY][binX]->getCapacity();
                    tmpUtilization += binGrid[newTopBinY][binX]->getUtilization();
                }
            }
            else if (tmpDir == expandDown)
            {
                //  for (int binY = newBottomBinY; binY <= newTopBinY; binY++)
                for (int binX = newLeftBinX; binX <= newRightBinX; binX++)
                {
                    tmpCapacity += binGrid[newBottomBinY][binX]->getCapacity();
                    tmpUtilization += binGrid[newBottomBinY][binX]->getUtilization();
                }
            }
            else if (tmpDir == expandLeft)
            {
                for (int binY = newBottomBinY; binY <= newTopBinY; binY++)
                //       for (int binX = newLeftBinX; binX <= newRightBinX; binX++)
                {
                    tmpCapacity += binGrid[binY][newLeftBinX]->getCapacity();
                    tmpUtilization += binGrid[binY][newLeftBinX]->getUtilization();
                }
            }
            else if (tmpDir == expandRight)
            {
                for (int binY = newBottomBinY; binY <= newTopBinY; binY++)
                //         for (int binX = newLeftBinX; binX <= newRightBinX; binX++)
                {
                    tmpCapacity += binGrid[binY][newRightBinX]->getCapacity();
                    tmpUtilization += binGrid[binY][newRightBinX]->getUtilization();
                }
            }
            if (tmpCapacity < 1e-5)
                tmpCapacity = 1e-5;
            if (tmpUtilization < 1e-5)
                tmpUtilization = 2e-5;
        }
 
        inline bool smartFindExpandDirection(std::set<PlacementInfo::PlacementBinInfo *> &coveredBinSet)
        {
            int possibleCnt = 0;
 
            // iterate the 4 direction
            for (int tmpDir = 0; tmpDir < 4; tmpDir++)
            {
                // initialize the expansion result (boundary, utlization, capacity, legal or not)
                unsigned int newTopBinY = topBinY + expandOps[tmpDir].topYOp;
                int newBottomBinY = bottomBinY + expandOps[tmpDir].bottomYOp;
                int newLeftBinX = leftBinX + expandOps[tmpDir].leftXOp;
                unsigned int newRightBinX = rightBinX + expandOps[tmpDir].rightXOp;
                dir2utilization[tmpDir] = 1e-1;
                dir2capacity[tmpDir] = 1e-5;
                legalDir[tmpDir] = false;
                if (newTopBinY < binGrid.size() && newBottomBinY >= 0)
                {
                    if (newRightBinX < binGrid[newTopBinY].size() && newLeftBinX >= 0)
                    {
                        // don't include the bins in other existing SpreadRegion
                        if (!isCovered(newTopBinY, newBottomBinY, newLeftBinX, newRightBinX,
                                       static_cast<dirType>(tmpDir), coveredBinSet))
                        {
                            // evaluate the utilization and capacity
                            getDirCapacityAndUtilization(newTopBinY, newBottomBinY, newLeftBinX, newRightBinX,
                                                         static_cast<dirType>(tmpDir), dir2utilization[tmpDir],
                                                         dir2capacity[tmpDir]);
 
                            // capacity greater than 0 => legal direction
                            if (dir2capacity[tmpDir] > 2e-5)
                            {
                                actualExpandOps[tmpDir] = expandOps[tmpDir];
                                legalDir[tmpDir] = true;
                                possibleCnt++;
                            }
 
                            // if the capacity is legal, then try to further expand 1 more bin step in this direction
                            if (!legalDir[tmpDir])
                            {
                                actualExpandOps[tmpDir] = expandOps[tmpDir] + 1; // <== further expand
                                unsigned int newTopBinY = topBinY + actualExpandOps[tmpDir].topYOp;
                                int newBottomBinY = bottomBinY + actualExpandOps[tmpDir].bottomYOp;
                                int newLeftBinX = leftBinX + actualExpandOps[tmpDir].leftXOp;
                                unsigned int newRightBinX = rightBinX + actualExpandOps[tmpDir].rightXOp;
                                if (newTopBinY < binGrid.size() && newBottomBinY >= 0)
                                {
                                    if (newRightBinX < binGrid[newTopBinY].size() && newLeftBinX >= 0)
                                    {
                                        if (!isCovered(newTopBinY, newBottomBinY, newLeftBinX, newRightBinX,
                                                       static_cast<dirType>(tmpDir), coveredBinSet))
                                        {
                                            getDirCapacityAndUtilization(newTopBinY, newBottomBinY, newLeftBinX,
                                                                         newRightBinX, static_cast<dirType>(tmpDir),
                                                                         dir2utilization[tmpDir], dir2capacity[tmpDir]);
                                            if (dir2capacity[tmpDir] > 2e-5)
                                            {
                                                legalDir[tmpDir] = true;
                                                possibleCnt++;
                                            }
 
                                            // if the capacity is legal, then try to further expand 1 more bin step in
                                            // this direction
                                            if (!legalDir[tmpDir])
                                            {
                                                actualExpandOps[tmpDir] =
                                                    (expandOps[tmpDir] + 1) + 1; // <== further expand
                                                unsigned int newTopBinY = topBinY + actualExpandOps[tmpDir].topYOp;
                                                int newBottomBinY = bottomBinY + actualExpandOps[tmpDir].bottomYOp;
                                                int newLeftBinX = leftBinX + actualExpandOps[tmpDir].leftXOp;
                                                unsigned int newRightBinX =
                                                    rightBinX + actualExpandOps[tmpDir].rightXOp;
                                                if (newTopBinY < binGrid.size() && newBottomBinY >= 0)
                                                {
                                                    if (newRightBinX < binGrid[newTopBinY].size() && newLeftBinX >= 0)
                                                    {
                                                        if (!isCovered(newTopBinY, newBottomBinY, newLeftBinX,
                                                                       newRightBinX, static_cast<dirType>(tmpDir),
                                                                       coveredBinSet))
                                                        {
                                                            getDirCapacityAndUtilization(
                                                                newTopBinY, newBottomBinY, newLeftBinX, newRightBinX,
                                                                static_cast<dirType>(tmpDir), dir2utilization[tmpDir],
                                                                dir2capacity[tmpDir]);
                                                            if (dir2capacity[tmpDir] > 2e-5)
                                                            {
                                                                legalDir[tmpDir] = true;
                                                                possibleCnt++;
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
            return possibleCnt;
        }
 
        inline bool expandable(int tmpDir)
        {
            return legalDir[tmpDir];
        }
 
        inline void smartExpand(std::set<PlacementInfo::PlacementBinInfo *> &coveredBinSet)
        {
            float hCapacity = dir2capacity[0] + dir2capacity[1];
            float vCapacity = dir2capacity[2] + dir2capacity[3];
            float hUtilization = dir2utilization[0] + dir2utilization[1];
            float vUtilization = dir2utilization[2] + dir2utilization[3];
            bool expanded = false;
 
            // try to expand in horizontal direction when horizontal utilization ratio is lower than vertical
            // utilization ratio
            if ((expandable(0) || expandable(1)) &&
                ((hUtilization / hCapacity < 0.9 * vUtilization / vCapacity) ||
                 (std::fabs(hUtilization + vUtilization) < 1e-4 && hCapacity > vCapacity)))
            {
                if (random() % 2)
                {
                    if (expandable(0))
                    {
                        if ((dir2utilization[0] + totalUtilization) / (dir2capacity[0] + totalCapacity) <
                            capacityShrinkRatio)
                        {
                            // if expanding left can solve the overflow, then only expand to left direction
                            unsigned int newTopBinY = topBinY + actualExpandOps[0].topYOp;
                            int newBottomBinY = bottomBinY + actualExpandOps[0].bottomYOp;
                            int newLeftBinX = leftBinX + actualExpandOps[0].leftXOp;
                            addBinRegion(newTopBinY, newBottomBinY, newLeftBinX, leftBinX - 1, coveredBinSet);
                            return;
                        }
                    }
                    if (expandable(1))
                    {
                        if ((dir2utilization[1] + totalUtilization) / (dir2capacity[1] + totalCapacity) <
                            capacityShrinkRatio)
                        {
                            // if expanding right can solve the overflow, then only expand to right direction
                            unsigned int newTopBinY = topBinY + actualExpandOps[1].topYOp;
                            int newBottomBinY = bottomBinY + actualExpandOps[1].bottomYOp;
                            unsigned int newRightBinX = rightBinX + actualExpandOps[1].rightXOp;
                            addBinRegion(newTopBinY, newBottomBinY, rightBinX + 1, newRightBinX, coveredBinSet);
                            return;
                        }
                    }
                }
                else
                {
                    if (expandable(1))
                    {
                        if ((dir2utilization[1] + totalUtilization) / (dir2capacity[1] + totalCapacity) <
                            capacityShrinkRatio)
                        {
                            // if expanding right can solve the overflow, then only expand to right direction
                            unsigned int newTopBinY = topBinY + actualExpandOps[1].topYOp;
                            int newBottomBinY = bottomBinY + actualExpandOps[1].bottomYOp;
                            unsigned int newRightBinX = rightBinX + actualExpandOps[1].rightXOp;
                            addBinRegion(newTopBinY, newBottomBinY, rightBinX + 1, newRightBinX, coveredBinSet);
                            return;
                        }
                    }
                    if (expandable(0))
                    {
                        if ((dir2utilization[0] + totalUtilization) / (dir2capacity[0] + totalCapacity) <
                            capacityShrinkRatio)
                        {
                            // if expanding left can solve the overflow, then only expand to left direction
                            unsigned int newTopBinY = topBinY + actualExpandOps[0].topYOp;
                            int newBottomBinY = bottomBinY + actualExpandOps[0].bottomYOp;
                            int newLeftBinX = leftBinX + actualExpandOps[0].leftXOp;
                            addBinRegion(newTopBinY, newBottomBinY, newLeftBinX, leftBinX - 1, coveredBinSet);
                            return;
                        }
                    }
                }
 
                // left and right
                unsigned int newTopBinY = topBinY + actualExpandOps[0].topYOp;
                int newBottomBinY = bottomBinY + actualExpandOps[0].bottomYOp;
                int newLeftBinX = leftBinX + actualExpandOps[0].leftXOp;
                unsigned int newRightBinX = rightBinX + actualExpandOps[0].rightXOp;
                if (expandable(0))
                {
                    addBinRegion(newTopBinY, newBottomBinY, newLeftBinX, leftBinX - 1, coveredBinSet);
                    expanded = true;
                }
                newTopBinY = topBinY + actualExpandOps[1].topYOp;
                newBottomBinY = bottomBinY + actualExpandOps[1].bottomYOp;
                newLeftBinX = leftBinX + actualExpandOps[1].leftXOp;
                newRightBinX = rightBinX + actualExpandOps[1].rightXOp;
                if (expandable(1))
                {
                    addBinRegion(newTopBinY, newBottomBinY, rightBinX + 1, newRightBinX, coveredBinSet);
                    expanded = true;
                }
            }
            else
            {
                if (random() % 2)
                {
                    if (expandable(2))
                    {
                        if ((dir2utilization[2] + totalUtilization) / (dir2capacity[2] + totalCapacity) <
                            capacityShrinkRatio)
                        {
                            // if expanding upward can solve the overflow, then only expand to upward direction
                            unsigned int newTopBinY = topBinY + actualExpandOps[2].topYOp;
                            int newLeftBinX = leftBinX + actualExpandOps[2].leftXOp;
                            unsigned int newRightBinX = rightBinX + actualExpandOps[2].rightXOp;
                            addBinRegion(newTopBinY, topBinY + 1, newLeftBinX, newRightBinX, coveredBinSet);
                            return;
                        }
                    }
                    if (expandable(3))
                    {
                        if ((dir2utilization[3] + totalUtilization) / (dir2capacity[3] + totalCapacity) <
                            capacityShrinkRatio)
                        {
                            // if expanding downward can solve the overflow, then only expand to downward direction
                            int newBottomBinY = bottomBinY + actualExpandOps[3].bottomYOp;
                            int newLeftBinX = leftBinX + actualExpandOps[3].leftXOp;
                            unsigned int newRightBinX = rightBinX + actualExpandOps[3].rightXOp;
                            addBinRegion(bottomBinY - 1, newBottomBinY, newLeftBinX, newRightBinX, coveredBinSet);
                            return;
                        }
                    }
                }
                else
                {
                    if (expandable(3))
                    {
                        if ((dir2utilization[3] + totalUtilization) / (dir2capacity[3] + totalCapacity) <
                            capacityShrinkRatio)
                        {
                            // if expanding downward can solve the overflow, then only expand to downward direction
                            int newBottomBinY = bottomBinY + actualExpandOps[3].bottomYOp;
                            int newLeftBinX = leftBinX + actualExpandOps[3].leftXOp;
                            unsigned int newRightBinX = rightBinX + actualExpandOps[3].rightXOp;
                            addBinRegion(bottomBinY - 1, newBottomBinY, newLeftBinX, newRightBinX, coveredBinSet);
                            return;
                        }
                    }
                    if (expandable(2))
                    {
                        if ((dir2utilization[2] + totalUtilization) / (dir2capacity[2] + totalCapacity) <
                            capacityShrinkRatio)
                        {
                            // if expanding upward can solve the overflow, then only expand to upward direction
                            unsigned int newTopBinY = topBinY + actualExpandOps[2].topYOp;
                            int newLeftBinX = leftBinX + actualExpandOps[2].leftXOp;
                            unsigned int newRightBinX = rightBinX + actualExpandOps[2].rightXOp;
                            addBinRegion(newTopBinY, topBinY + 1, newLeftBinX, newRightBinX, coveredBinSet);
                            return;
                        }
                    }
                }
 
                // up and down
                unsigned int newTopBinY = topBinY + actualExpandOps[2].topYOp;
                int newBottomBinY = bottomBinY + actualExpandOps[2].bottomYOp;
                int newLeftBinX = leftBinX + actualExpandOps[2].leftXOp;
                unsigned int newRightBinX = rightBinX + actualExpandOps[2].rightXOp;
                if (expandable(2))
                {
                    addBinRegion(newTopBinY, topBinY + 1, newLeftBinX, newRightBinX, coveredBinSet);
                    expanded = true;
                }
                newTopBinY = topBinY + actualExpandOps[3].topYOp;
                newBottomBinY = bottomBinY + actualExpandOps[3].bottomYOp;
                newLeftBinX = leftBinX + actualExpandOps[3].leftXOp;
                newRightBinX = rightBinX + actualExpandOps[3].rightXOp;
                if (expandable(3))
                {
                    addBinRegion(bottomBinY - 1, newBottomBinY, newLeftBinX, newRightBinX, coveredBinSet);
                    expanded = true;
                }
            }
 
            if (!expanded)
            {
                std::cout << "expandable(0,1,2,3):" << expandable(0) << expandable(1) << expandable(2) << expandable(3)
                          << "\ndir2capacity[0]:" << dir2capacity[0] << " dir2capacity[1]:" << dir2capacity[1]
                          << " dir2capacity[2]:" << dir2capacity[2] << " dir2capacity[3]:" << dir2capacity[3]
                          << "\ndir2utilization[0]:" << dir2utilization[0]
                          << " dir2utilization[1]:" << dir2utilization[1]
                          << " dir2utilization[2]:" << dir2utilization[2]
                          << " dir2utilization[3]:" << dir2utilization[3] << "\n"
                          << " hUtilization / hCapacity < vUtilization / vCapacity:"
                          << (hUtilization / hCapacity < vUtilization / vCapacity) << "\n";
                std::cout.flush();
                assert(false && "should not be unexpandable");
            }
        }
 
        inline bool simpleFindExpandDirection(std::set<PlacementInfo::PlacementBinInfo *> &coveredBinSet)
        {
            char failureCnt = 0;
            curDirectionIndex = random() % 4;
            while (failureCnt < 4)
            {
 
                unsigned int newTopBinY = topBinY + expandOps[curDirectionIndex].topYOp;
                int newBottomBinY = bottomBinY + expandOps[curDirectionIndex].bottomYOp;
                int newLeftBinX = leftBinX + expandOps[curDirectionIndex].leftXOp;
                unsigned int newRightBinX = rightBinX + expandOps[curDirectionIndex].rightXOp;
                if (newTopBinY < binGrid.size() && newBottomBinY >= 0)
                {
                    if (newRightBinX < binGrid[newTopBinY].size() && newLeftBinX >= 0)
                    {
                        if (!isCovered(newTopBinY, newBottomBinY, newLeftBinX, newRightBinX,
                                       static_cast<dirType>(curDirectionIndex), coveredBinSet))
                        {
                            curDirection = static_cast<dirType>(curDirectionIndex);
                            curDirectionIndex = (curDirectionIndex + 1) % 4;
                            return true;
                        }
                    }
                }
                curDirectionIndex = (curDirectionIndex + 1) % 4;
                failureCnt++;
            }
            return false;
        }
 
        inline void simpleExpand(std::set<PlacementInfo::PlacementBinInfo *> &coveredBinSet)
        {
            unsigned int newTopBinY = topBinY + expandOps[curDirection].topYOp;
            int newBottomBinY = bottomBinY + expandOps[curDirection].bottomYOp;
            int newLeftBinX = leftBinX + expandOps[curDirection].leftXOp;
            unsigned int newRightBinX = rightBinX + expandOps[curDirection].rightXOp;
            if (curDirection == expandUp)
                addBinRegion(newTopBinY, newTopBinY, newLeftBinX, newRightBinX, coveredBinSet);
            else if (curDirection == expandDown)
                addBinRegion(newBottomBinY, newBottomBinY, newLeftBinX, newRightBinX, coveredBinSet);
            else if (curDirection == expandLeft)
                addBinRegion(newTopBinY, newBottomBinY, newLeftBinX, newLeftBinX, coveredBinSet);
            else if (curDirection == expandRight)
                addBinRegion(newTopBinY, newBottomBinY, newRightBinX, newRightBinX, coveredBinSet);
        }
 
        inline bool contains(PlacementInfo::PlacementBinInfo *curBin)
        {
            return binSetInRegion.find(curBin) != binSetInRegion.end();
        }
 
        inline std::vector<DesignInfo::DesignCell *> &getCells()
        {
            return cellsInRegionVec;
        }
 
        inline int top()
        {
            return topBinY;
        }
 
        inline int bottom()
        {
            return bottomBinY;
        }
 
        inline int left()
        {
            return leftBinX;
        }
 
        inline int right()
        {
            return rightBinX;
        }
 
        inline float getOverflowRatio()
        {
            return overflowRatio;
        }
 
        class SubBox
        {
          public:
            SubBox(PlacementInfo *placementInfo, SpreadRegion *curRegion,
                   std::vector<std::vector<PlacementInfo::PlacementBinInfo *>> &binGrid,
                   float capacityShrinkRatio = 1.0, int level = 100, bool dirIsH = true)
                : placementInfo(placementInfo), binGrid(binGrid), capacityShrinkRatio(capacityShrinkRatio),
                  topBinY(curRegion->top()), bottomBinY(curRegion->bottom()), leftBinX(curRegion->left()),
                  rightBinX(curRegion->right()), level(level), dirIsH(dirIsH)
            {
                cellIds.clear();
                std::vector<DesignInfo::DesignCell *> tmpCells;
                tmpCells.clear();
                for (auto curCell : curRegion->getCells())
                {
                    tmpCells.push_back(curCell);
                }
                std::sort(tmpCells.begin(), tmpCells.end(),
                          [](DesignInfo::DesignCell *a, DesignInfo::DesignCell *b) -> bool {
                              return a->getCellId() > b->getCellId();
                          });
                for (auto curCell : tmpCells)
                {
                    cellIds.push_back(curCell->getCellId());
                }
            }
 
            SubBox(SubBox *parentBox, int topBinY, int bottomBinY, int leftBinX, int rightBinX, int cellRangeBegin,
                   int cellRangeEnd)
                : placementInfo(parentBox->placementInfo), binGrid(parentBox->binGrid),
                  capacityShrinkRatio(parentBox->capacityShrinkRatio), topBinY(topBinY), bottomBinY(bottomBinY),
                  leftBinX(leftBinX), rightBinX(rightBinX), level(parentBox->getLevel() - 1), dirIsH(!parentBox->dirIsH)
            {
                if (cellRangeBegin <= cellRangeEnd)
                    cellIds = std::vector<int>(
                        {parentBox->cellIds.begin() + cellRangeBegin, parentBox->cellIds.begin() + cellRangeEnd + 1});
                else
                    cellIds.clear();
            }
 
            ~SubBox()
            {
            }
 
            PlacementInfo *placementInfo;
            std::vector<std::vector<PlacementInfo::PlacementBinInfo *>> &binGrid;
            float capacityShrinkRatio = 1.0;
 
            inline void addCellId(int cellId)
            {
                cellIds.push_back(cellId);
            }
 
            void spreadAndPartition();
 
            inline int Partition(std::vector<int> &cellIds, int low, int high, bool Xsort)
            {
                if (Xsort)
                {
                    int pivot, index, i;
                    index = low;
                    pivot = high;
                    for (i = low; i < high; i++)
                    {
                        // finding index of pivot.
                        // if (a[i] < a[pivot])
                        if (placementInfo->getCellId2location()[cellIds[i]].X <
                            placementInfo->getCellId2location()[cellIds[pivot]].X)
                        {
                            std::swap(cellIds[i], cellIds[index]);
                            index++;
                        }
                    }
                    std::swap(cellIds[pivot], cellIds[index]);
                    return index;
                }
                else
                {
                    int pivot, index, i;
                    index = low;
                    pivot = high;
                    for (i = low; i < high; i++)
                    {
                        // finding index of pivot.
                        // if (a[i] < a[pivot])
                        if (placementInfo->getCellId2location()[cellIds[i]].Y <
                            placementInfo->getCellId2location()[cellIds[pivot]].Y)
                        {
                            std::swap(cellIds[i], cellIds[index]);
                            index++;
                        }
                    }
                    std::swap(cellIds[pivot], cellIds[index]);
                    return index;
                }
            }
 
            inline int RandomPivotPartition(std::vector<int> &cellIds, int low, int high, bool Xsort)
            {
                // Random selection of pivot.
                int pvt, n;
                n = HiFPlacer_hashprimes[low & 0xff];
                pvt = low + n % (high - low + 1); // Randomizing the pivot value from sub-array.
                std::swap(cellIds[high], cellIds[pvt]);
                return Partition(cellIds, low, high, Xsort);
            }
 
            void quick_sort(std::vector<int> &cellIds, int p, int q, bool Xsort)
            {
                // recursively sort the list
                int pindex;
                if (p < q)
                {
                    pindex = RandomPivotPartition(cellIds, p, q, Xsort); // randomly choose pivot
                    // Recursively implementing QuickSort.
                    quick_sort(cellIds, p, pindex - 1, Xsort);
                    quick_sort(cellIds, pindex + 1, q, Xsort);
                }
            }
 
            inline int getLevel()
            {
                return level;
            }
 
            void spreadCellsH(SubBox **boxA, SubBox **boxB);
 
            void spreadCellsV(SubBox **boxA, SubBox **boxB);
 
            inline int top()
            {
                return topBinY;
            }
 
            inline int bottom()
            {
                return bottomBinY;
            }
 
            inline int left()
            {
                return leftBinX;
            }
 
            inline int right()
            {
                return rightBinX;
            }
 
          private:
            int topBinY, bottomBinY, leftBinX, rightBinX;
 
            std::vector<int> cellIds;
            int level;
 
          public:
            bool dirIsH;
 
            int minExpandSize = 2;
        };
 
        static constexpr float eps = 1e-4;
 
      private:
        PlacementInfo *placementInfo;
        float totalCapacity;
        float totalUtilization;
        float overflowRatio;
        int topBinY, bottomBinY;
        int leftBinX, rightBinX;
 
        int curDirectionIndex = 0;
 
        dirType curDirection = expandLeft;
 
        std::vector<std::vector<PlacementInfo::PlacementBinInfo *>> &binGrid;
 
        float dir2utilization[4];
 
        float dir2capacity[4];
 
        bool legalDir[4];
        float capacityShrinkRatio = 1.0;
 
        std::set<DesignInfo::DesignCell *> cellsInRegion;
 
        std::vector<DesignInfo::DesignCell *> cellsInRegionVec;
 
        std::vector<PlacementInfo::PlacementBinInfo *> binsInRegion;
 
        std::set<PlacementInfo::PlacementBinInfo *> binSetInRegion;
    };
 
    void updatePlacementUnitsWithSpreadedCellLocations(std::set<PlacementInfo::PlacementUnit *> &involvedPUs,
                                                       std::set<DesignInfo::DesignCell *> &involvedCells,
                                                       std::vector<PlacementInfo::PlacementUnit *> &involvedPUVec,
                                                       float forgetRatio, bool enableClockRegionAware,
                                                       float displacementLimit);
 
    static void updatePlacementUnitsWithSpreadedCellLocationsWorker(
        PlacementInfo *placementInfo, std::set<PlacementInfo::PlacementUnit *> &involvedPUs,
        std::set<DesignInfo::DesignCell *> &involvedCells, std::vector<PlacementInfo::PlacementUnit *> &involvedPUVec,
        float forgetRatio, float displacementLimit, int startId, int endId);
 
    static void makeCellInLegalArea(PlacementInfo *placementInfo, float &cellX, float &cellY)
    {
        float eps = 1e-4;
        if (cellX < placementInfo->getGlobalMinX())
        {
            cellX = placementInfo->getGlobalMinX() + eps;
        }
        if (cellY < placementInfo->getGlobalMinY())
        {
            cellY = placementInfo->getGlobalMinY() + eps;
        }
        if (cellX > placementInfo->getGlobalMaxX())
        {
            cellX = placementInfo->getGlobalMaxX() - eps;
        }
        if (cellY > placementInfo->getGlobalMaxY())
        {
            cellY = placementInfo->getGlobalMaxY() - eps;
        }
    }
 
    void recordSpreadedCellLocations();
 
    void DumpCellsCoordinate(std::string dumpFileName, GeneralSpreader::SpreadRegion *curRegion);
    void DumpPUCoordinate(std::string dumpFileName, std::vector<PlacementInfo::PlacementUnit *> &involvedPUVec);
 
  private:
    PlacementInfo *placementInfo;
    std::map<std::string, std::string> &JSONCfg;
    std::string sharedCellType;
    int currentIteration = 0;
    float capacityShrinkRatio = 1.0;
    bool verbose;
 
    std::vector<std::vector<PlacementInfo::PlacementBinInfo *>> &binGrid;
 
    int dumpSiteGridDensityCnt = 0;
    int LUTFFCoordinateDumpCnt = 0;
    int nJobs = 1;
 
    bool useSimpleExpland = false;
    bool enforceSimpleExpland = false;
    int dumpCnt = 0;
 
    std::vector<PlacementInfo::PlacementBinInfo *> overflowBins;
 
    std::set<PlacementInfo::PlacementBinInfo *> overflowBinSet;
 
    std::set<PlacementInfo::PlacementBinInfo *> coveredBinSet;
 
    void dumpSiteGridDensity(std::string dumpFileName);
 
    void findOverflowBins(float overflowThreshold);
 
    GeneralSpreader::SpreadRegion *expandFromABin(PlacementInfo::PlacementBinInfo *curBin, float capacityShrinkRatio,
                                                  unsigned int numBinThr = 1000000);
 
    std::vector<GeneralSpreader::SpreadRegion *> expandedRegions;
};
 
std::ostream &operator<<(std::ostream &os, GeneralSpreader::SpreadRegion::SubBox *curBox);
#endif