CLBLegalizer.h

Go to the documentation of this file.

 
#ifndef _CLBLEGALIZER
#define _CLBLEGALIZER
 
#include "DesignInfo.h"
#include "DeviceInfo.h"
#include "MinCostBipartiteMatcher.h"
#include "PlacementInfo.h"
#include "dumpZip.h"
#include "sysInfo.h"
#include <assert.h>
#include <fstream>
#include <iostream>
#include <map>
#include <mutex>
#include <omp.h>
#include <semaphore.h>
#include <set>
#include <sstream>
#include <string>
#include <thread>
#include <vector>
 
class CLBLegalizer
{
  public:
    CLBLegalizer(std::string legalizerName, PlacementInfo *placementInfo, DeviceInfo *deviceInfo,
                 std::vector<std::string> &siteTypesToLegalize, std::map<std::string, std::string> &JSONCfg);
    ~CLBLegalizer()
    {
        if (minCostBipartiteMatcher)
            delete minCostBipartiteMatcher;
    }
 
    void legalize(bool exactLegalization = false);
 
    inline float getAverageDisplacementOfExactLegalization()
    {
        if (finalAverageDisplacement > 1000)
            return finalAverageDisplacement;
        float tmpAverageDisplacement = 0.0;
        for (auto PUSitePair : PULevelMatching)
        {
            tmpAverageDisplacement += std::fabs(PUSitePair.first->X() - PUSitePair.second->X()) +
                                      std::fabs(PUSitePair.first->Y() - PUSitePair.second->Y());
        }
        tmpAverageDisplacement /= PULevelMatching.size();
 
        return tmpAverageDisplacement;
    }
 
    inline float getAverageDisplacementOfRoughLegalization()
    {
        return roughAverageDisplacement;
    }
 
    void setIntitialParameters(float displacementThr, int candidateNum, int _candidateFactor = -1)
    {
        initialDisplacementThreshold = displacementThr;
        initialMaxNumCandidate = candidateNum;
        if (_candidateFactor > 1)
        {
            candidateFactor = _candidateFactor;
        }
    }
 
    void resetSitesMapped();
    void dumpMatching(bool fixedColumn = false, bool enforce = false);
 
    inline bool hasNoTarget()
    {
        return noTarget;
    }
 
  private:
    std::string legalizerName;
    PlacementInfo *placementInfo;
    DeviceInfo *deviceInfo;
 
    PlacementInfo::CompatiblePlacementTable *compatiblePlacementTable;
 
    std::vector<std::string> siteTypesToLegalize;
 
    std::vector<PlacementInfo::Location> &cellLoc;
 
    std::map<std::string, std::string> &JSONCfg;
 
    MinCostBipartiteMatcher *minCostBipartiteMatcher = nullptr;
 
    std::vector<PlacementInfo::PlacementUnit *> PUsToLegalize;
 
    std::vector<PlacementInfo::PlacementUnit *> initialPUsToLegalize;
 
    std::set<PlacementInfo::PlacementUnit *> PUsToLegalizeSet;
 
    std::map<std::string, std::vector<DeviceInfo::DeviceSite *>> siteType2Sites;
 
    std::map<PlacementInfo::PlacementUnit *, std::vector<DeviceInfo::DeviceSite *>> PU2Sites;
 
    std::map<DeviceInfo::DeviceSite *, int> rightSiteIds;
 
    std::vector<DeviceInfo::DeviceSite *> siteList;
 
    std::vector<std::vector<std::pair<int, float>>> adjList;
 
    std::map<PlacementInfo::PlacementUnit *, std::map<DeviceInfo::DeviceSite *, float>> PU2Site2HPWLIncrease;
 
    std::set<PlacementInfo::PlacementUnit *> matchedPUs;
 
    std::set<DeviceInfo::DeviceSite *> matchedSites;
 
    std::vector<std::pair<PlacementInfo::PlacementUnit *, DeviceInfo::DeviceSite *>> PULevelMatching;
 
    int DumpCLBLegalizationCnt = 0;
 
    float displacementThreshold = 20;
 
    int maxNumCandidate = 20;
 
    int candidateFactor = 5;
 
    int nJobs = 1;
 
    int MCLBColumnNum = -1;
 
    int LCLBColumnNum = -1;
 
    int MCLBRowNum = -1;
 
    int LCLBRowNum = -1;
 
    std::vector<float> MCLBColumnXs;
 
    std::vector<float> LCLBColumnXs;
 
    std::vector<std::vector<DeviceInfo::DeviceSite *>> MCLBColumn2Sites;
 
    std::vector<std::vector<DeviceInfo::DeviceSite *>> LCLBColumn2Sites;
 
    std::vector<std::deque<PlacementInfo::PlacementUnit *>> MCLBColumn2PUs;
 
    std::vector<std::deque<PlacementInfo::PlacementUnit *>> LCLBColumn2PUs;
 
    std::vector<int> MCLBColumnUntilization;
 
    std::vector<int> LCLBColumnUntilization;
 
    std::map<PlacementInfo::PlacementUnit *, int> MCLB2Column;
 
    std::map<PlacementInfo::PlacementUnit *, int> LCLB2Column;
 
    std::map<PlacementInfo::PlacementUnit *, std::vector<DeviceInfo::DeviceSite *>> PU2LegalSites;
 
    std::map<PlacementInfo::PlacementUnit *, float> PU2X;
    std::map<PlacementInfo::PlacementUnit *, float> PU2Y;
 
    std::map<PlacementInfo::PlacementUnit *, int> PU2SiteX;
 
    std::map<PlacementInfo::PlacementUnit *, std::vector<int>> PU2Columns;
 
    std::set<PlacementInfo::PlacementUnit *> MCLBPUs;
 
    std::set<PlacementInfo::PlacementUnit *> LCLBPUs;
 
    std::map<PlacementInfo::PlacementUnit *, std::vector<DeviceInfo::DeviceSite *> *> PU2SitesInDisplacementThreshold;
 
    bool enableMCLBLegalization = false;
    bool enableLCLBLegalization = false;
    bool verbose = false;
    float y2xRatio = 1.0;
 
    float finalAverageDisplacement = 10000.0;
 
    float fixedColumnAverageDisplacement = 10000.0;
 
    float roughAverageDisplacement = 10000.0;
 
    bool noTarget = false;
 
    float initialDisplacementThreshold = 20;
 
    int initialMaxNumCandidate = 20;
 
    void getPUsToLegalize();
 
    void findSiteType2AvailableSites();
 
    void resolveOverflowColumns();
 
    void findPossibleLegalLocation(bool fixedColumn = false);
 
    void mapPUsToColumns();
 
    void createBipartiteGraph();
 
    void roughlyLegalize();
 
    void fixedColumnLegalize();
 
    void updatePUMatchingLocation(bool isRoughLegalization = true, bool updateDisplacement = true);
 
    void finalLegalizeBasedOnDP();
 
    float DPForMinHPWL(int colNum, std::vector<std::vector<DeviceInfo::DeviceSite *>> &Column2Sites,
                       std::vector<std::deque<PlacementInfo::PlacementUnit *>> &Column2PUs);
 
    void updateMatchingAndUnmatchedPUs();
 
    void spreadPUs(int columnNum, std::vector<int> &columnUntilization,
                   std::vector<std::vector<DeviceInfo::DeviceSite *>> &column2Sites,
                   std::vector<std::deque<PlacementInfo::PlacementUnit *>> &column2PUs,
                   std::map<PlacementInfo::PlacementUnit *, int> &cell2Column);
 
    int findIdMaxWithRecurence(int minId, int maxId, std::vector<int> &ids);
 
    void setSitesMapped();
 
    inline void resetSettings()
    {
        displacementThreshold = initialDisplacementThreshold;
        maxNumCandidate = initialMaxNumCandidate;
        matchedPUs.clear();
        matchedSites.clear();
        PULevelMatching.clear();
    }
 
    void findPU2SitesInDistance()
    {
        PU2SitesInDisplacementThreshold.clear();
 
        int PUsNum = PUsToLegalize.size();
 
        for (int i = 0; i < PUsNum; i++)
        {
            PU2SitesInDisplacementThreshold[PUsToLegalize[i]] = nullptr;
        }
 
#pragma omp parallel for
        for (int i = 0; i < PUsNum; i++)
        {
            PlacementInfo::PlacementUnit *curPU = PUsToLegalize[i];
            DesignInfo::DesignCell *curCell = nullptr;
            if (auto unpackedCell = dynamic_cast<PlacementInfo::PlacementUnpackedCell *>(curPU))
            {
                curCell = unpackedCell->getCell();
            }
            else if (auto curMacro = dynamic_cast<PlacementInfo::PlacementMacro *>(curPU))
            {
                assert(curMacro->getCells().size() > 0);
                curCell = curMacro->getCells()[0];
            }
            assert(curCell);
            PU2SitesInDisplacementThreshold[curPU] = placementInfo->findNeiborSiteFromBinGrid(
                curCell, cellLoc[curCell->getCellId()].X, cellLoc[curCell->getCellId()].Y, displacementThreshold,
                candidateFactor * maxNumCandidate);
        }
    }
 
    void resetPU2SitesInDistance()
    {
        int PUsNum = PUsToLegalize.size();
        for (int i = 0; i < PUsNum; i++)
        {
            PlacementInfo::PlacementUnit *curPU = PUsToLegalize[i];
            delete PU2SitesInDisplacementThreshold[curPU];
        }
    }
 
    int getPUSiteNum(PlacementInfo::PlacementUnit *tmpPUUnit);
 
    inline void swapPU(PlacementInfo::PlacementUnit **A, PlacementInfo::PlacementUnit **B)
    {
        PlacementInfo::PlacementUnit *C = *A;
        *A = *B;
        *B = C;
    }
 
    void sortPUsByPU2Y(std::deque<PlacementInfo::PlacementUnit *> &PUs);
 
    void sortSitesBySiteY(std::vector<DeviceInfo::DeviceSite *> &sites);
 
    inline float getDisplacement(PlacementInfo::Location &PULoc, DeviceInfo::DeviceSite *curSite)
    {
        return std::fabs(PULoc.X - curSite->X()) + y2xRatio * std::fabs(PULoc.Y - curSite->Y());
    }
 
    inline float getDisplacement(PlacementInfo::PlacementUnit *curPU, DeviceInfo::DeviceSite *curSite)
    {
        return std::fabs(curPU->X() - curSite->X()) + y2xRatio * std::fabs(curPU->Y() - curSite->Y());
    }
 
    inline float getHPWLChange(PlacementInfo::PlacementUnit *curPU, DeviceInfo::DeviceSite *curSite)
    {
        assert(PU2Site2HPWLIncrease.find(curPU) != PU2Site2HPWLIncrease.end());
        if (PU2Site2HPWLIncrease[curPU].find(curSite) != PU2Site2HPWLIncrease[curPU].end())
        {
            return PU2Site2HPWLIncrease[curPU][curSite];
        }
        float oriHPWL = 0.0;
        float newHPWL = 0.0;
        float PUX = curSite->X();
        float PUY = curSite->Y();
        auto nets = placementInfo->getPlacementUnitId2Nets()[curPU->getId()];
 
        for (auto curNet : nets)
        {
            if (curNet->getDesignNet()->getPins().size() > 10000) // it could be clock
                continue;
            oriHPWL += curNet->getHPWL(y2xRatio);
            newHPWL += curNet->getNewHPWLByTrying(curPU, PUX, PUY, y2xRatio);
        }
 
        PU2Site2HPWLIncrease[curPU][curSite] = (newHPWL - oriHPWL);
        return (newHPWL - oriHPWL);
    }
 
    inline float getHPWLChange(PlacementInfo::PlacementUnit *tmpPU, float PUX, float PUY)
    {
 
        float oriHPWL = 0.0;
        float newHPWL = 0.0;
        auto nets = placementInfo->getPlacementUnitId2Nets()[tmpPU->getId()];
 
        for (auto curNet : nets)
        {
            if (curNet->getDesignNet()->getPins().size() > 10000) // it could be clock
                continue;
            oriHPWL += curNet->getHPWL(y2xRatio);
            newHPWL += curNet->getNewHPWLByTrying(tmpPU, PUX, PUY, y2xRatio);
        }
 
        return (newHPWL - oriHPWL);
    }
 
    inline void swapSitePtr(DeviceInfo::DeviceSite **siteA, DeviceInfo::DeviceSite **siteB)
    {
        DeviceInfo::DeviceSite *tmp = *siteA;
        *siteA = *siteB;
        *siteB = tmp;
    }
 
    inline int sortPartition(PlacementInfo::PlacementUnit *curPU, std::vector<DeviceInfo::DeviceSite *> &sites, int low,
                             int high)
    {
        int pivot, index, i;
        index = low;
        pivot = high;
        for (i = low; i < high; i++)
        {
            // finding index of pivot.
            // if (a[i] < a[pivot])
            // if (getDisplacement(PULoc, sites[i]) < getDisplacement(PULoc, sites[pivot]))
            if (getHPWLChange(curPU, sites[i]) < getHPWLChange(curPU, sites[pivot]))
            {
                swapSitePtr(&sites[i], &sites[index]);
                index++;
            }
        }
        swapSitePtr(&sites[pivot], &sites[index]);
        return index;
    }
    inline int RandomPivotPartition(PlacementInfo::PlacementUnit *curPU, std::vector<DeviceInfo::DeviceSite *> &sites,
                                    int low, int high)
    {
        // Random selection of pivot.
        int pvt;
        pvt = (high + low) / 2; // Randomizing the pivot value from sub-array.
        swapSitePtr(&sites[high], &sites[pvt]);
        return sortPartition(curPU, sites, low, high);
    }
    void quick_sort_WLChange(PlacementInfo::PlacementUnit *curPU, std::vector<DeviceInfo::DeviceSite *> &sites, int p,
                             int q)
    {
        // recursively sort the list
        int pindex;
        if (p < q)
        {
            pindex = RandomPivotPartition(curPU, sites, p, q); // randomly choose pivot
            // Recursively implementing QuickSort.
            quick_sort_WLChange(curPU, sites, p, pindex - 1);
            quick_sort_WLChange(curPU, sites, pindex + 1, q);
        }
    }
 
    inline void swapPUs(PlacementInfo::PlacementUnit **siteA, PlacementInfo::PlacementUnit **siteB)
    {
        PlacementInfo::PlacementUnit *tmp = *siteA;
        *siteA = *siteB;
        *siteB = tmp;
    }
 
    inline int sortPartition(std::vector<PlacementInfo::PlacementUnit *> &PUs, int low, int high)
    {
        int pivot, index, i;
        index = low;
        pivot = high;
        for (i = low; i < high; i++)
        {
            // finding index of pivot.
            // if (a[i] < a[pivot])
            // if (getDisplacement(PULoc, PUs[i]) < getDisplacement(PULoc, PUs[pivot]))
            if (PUs[i]->X() < PUs[pivot]->X())
            {
                swapPUs(&PUs[i], &PUs[index]);
                index++;
            }
        }
        swapPUs(&PUs[pivot], &PUs[index]);
        return index;
    }
    inline int RandomPivotPartition(std::vector<PlacementInfo::PlacementUnit *> &PUs, int low, int high)
    {
        // Random selection of pivot.
        int pvt, n;
        n = random();
        pvt = low + n % (high - low + 1); // Randomizing the pivot value from sub-array.
        swapPUs(&PUs[high], &PUs[pvt]);
        return sortPartition(PUs, low, high);
    }
    void quick_sort_locX(std::vector<PlacementInfo::PlacementUnit *> &PUs, int p, int q)
    {
        // recursively sort the list
        int pindex;
        if (p < q)
        {
            pindex = RandomPivotPartition(PUs, p, q); // randomly choose pivot
            // Recursively implementing QuickSort.
            quick_sort_locX(PUs, p, pindex - 1);
            quick_sort_locX(PUs, pindex + 1, q);
        }
    }
};
 
#endif