routingarea.cpp

简单迷宫布线器源码

#include	<stdlib.h>
#include	<fstream.h>
#include	<assert.h>
#include	<stdarg.h>
#include    <stdio.h>
#include    <math.h>
#include	<time.h>
#include    "routing_area.h"
//using namespace std;

#define     EMPTY           -100000
#define     PORTBASE        1000000

CRoutingArea::~CRoutingArea()
{
 //   delete[] m_iNetPriority;
 //   delete[] m_iPortAmount;
 //   delete[] m_pRoutingCells;
}

bool CRoutingArea::isFinished()
{
    int     i;
    for (i=0; i<m_iNetAmount; i++)
    {
        if (isRouted(i)==0)
            return false;
    }
    return true;
}

bool CRoutingArea::isnotBottleNeck(int iXPos,int iYPos)
{
    int     iTmpXPos, iTmpYPos,iOthers,iPreNet;

    if (getCell(iXPos,iYPos)>=PORTBASE)
        return false;
    iPreNet=getCell(iXPos,iYPos);

    iOthers=0;
    iTmpXPos=iXPos-1;       iTmpYPos=iYPos-1;
    if (iTmpXPos>=0 && iTmpYPos>=0)
    {
        if (getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos) &&
            getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos)+PORTBASE)
        {
            iPreNet=getCell(iTmpXPos,iTmpYPos);
        }
    }

    iTmpXPos=iXPos;       iTmpYPos=iYPos-1;
    if (iTmpYPos>=0)
    {
        if (getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos) &&
            getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos)+PORTBASE)
        {
            if (iPreNet!=getCell(iXPos,iYPos) && 
                iPreNet!=getCell(iTmpXPos,iTmpYPos))
                return false;
            else
                iPreNet=getCell(iTmpXPos,iTmpYPos);
        }
    }

    iTmpXPos=iXPos+1;       iTmpYPos=iYPos-1;
    if (iTmpXPos<m_iXSize && iTmpYPos>=0)
    {
        if (getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos) &&
            getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos)+PORTBASE)
        {
            if (iPreNet!=getCell(iXPos,iYPos) && 
                iPreNet!=getCell(iTmpXPos,iTmpYPos))
                return false;
            else
                iPreNet=getCell(iTmpXPos,iTmpYPos);
        }
    }

    iTmpXPos=iXPos+1;   iTmpYPos=iYPos;
    if (iTmpXPos<m_iXSize)
    {
        if (getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos) &&
            getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos)+PORTBASE)
        {
            if (iPreNet!=getCell(iXPos,iYPos) && 
                iPreNet!=getCell(iTmpXPos,iTmpYPos))
                return false;
            else
                iPreNet=getCell(iTmpXPos,iTmpYPos);
        }
    }

    iTmpXPos=iXPos+1;   iTmpYPos=iYPos+1;
    if (iTmpXPos<m_iXSize && iTmpYPos<m_iYSize)
    {
        if (getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos) &&
            getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos)+PORTBASE)
        {
            if (iPreNet!=getCell(iXPos,iYPos) && 
                iPreNet!=getCell(iTmpXPos,iTmpYPos))
                return false;
            else
                iPreNet=getCell(iTmpXPos,iTmpYPos);
        }
    }

    iTmpXPos=iXPos;   iTmpYPos=iYPos+1;
    if (iTmpXPos<m_iXSize && iTmpYPos<m_iYSize)
    {
        if (getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos) &&
            getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos)+PORTBASE)
        {
            if (iPreNet!=getCell(iXPos,iYPos) && iPreNet!=getCell(iTmpXPos,iTmpYPos))
                return false;
            else
                iPreNet=getCell(iTmpXPos,iTmpYPos);
        }
    }

    iTmpXPos=iXPos+1;   iTmpYPos=iYPos+1;
    if (iTmpXPos<m_iXSize && iTmpYPos<m_iYSize)
    {
        if (getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos) &&
            getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos)+PORTBASE)
        {
            if (iPreNet!=getCell(iXPos,iYPos) && iPreNet!=getCell(iTmpXPos,iTmpYPos))
                return false;
            else
                iPreNet=getCell(iTmpXPos,iTmpYPos);
        }
    }

    iTmpXPos=iXPos-1;   iTmpYPos=iYPos+1;
    if (iTmpXPos>=0 && iTmpYPos<m_iYSize)
    {
        if (getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos) &&
            getCell(iTmpXPos,iTmpYPos)!=getCell(iXPos,iYPos)+PORTBASE)
        {
            if (iPreNet!=getCell(iXPos,iYPos) && iPreNet!=getCell(iTmpXPos,iTmpYPos))
                return false;
            else
                iPreNet=getCell(iTmpXPos,iTmpYPos);
        }
    }
    return true;
}

void CRoutingArea::initialize(int iNetAmount, int iMaxPortAmount)
{
    int         i,j,iPortAmount,iXPos, iYPos;

    srand(time(NULL));
    m_iNetAmount=iNetAmount;
    m_iNetPriority=new int(iNetAmount);
    for (i=0; i<iNetAmount; i++)
    {
        m_iNetPriority[i]=i;
    }
    m_iPortAmount=new int(iNetAmount);
    
    for (i=0; i<iNetAmount;i++)
    {
        iPortAmount=rand()%iMaxPortAmount;
        if (iPortAmount<=1)
            iPortAmount=2;
        m_iPortAmount[i]=iPortAmount;
        for (j=0;j<iPortAmount;j++)
        {
            do
            {
                iXPos=rand()%m_iXSize;
                iYPos=rand()%m_iYSize;
            }
            while (getCell(iXPos,iYPos)!=EMPTY);
            setCell(iXPos,iYPos,PORTBASE+i);
        }
    }
}

int CRoutingArea::getCell(int iXPos, int iYPos, int *pArea)
{
    if (pArea==NULL)
        pArea=m_pRoutingCells;
#ifdef _DEBUG
    int     iIndex;
    assert(iYPos*m_iXSize+iXPos>=0 && iYPos*m_iXSize+iXPos<(m_iXSize*m_iYSize));
    iIndex=iYPos*m_iXSize+iXPos;
    iIndex=pArea[iYPos*m_iXSize+iXPos];
#endif
    return pArea[iYPos*m_iXSize+iXPos];
}

void CRoutingArea::setCell(int iXPos, int iYPos, int iNet,int *pArea)
{
    if (pArea==NULL)
        pArea=m_pRoutingCells;
    assert(iYPos*m_iXSize+iXPos>=0 && iYPos*m_iXSize+iXPos<(m_iXSize*m_iYSize));
    pArea[iYPos*m_iXSize+iXPos]=iNet;
}

CRoutingArea::CRoutingArea(int iXSize,int iYSize)
{
    int         i,iAmount;

    m_iXSize=iXSize;
    m_iYSize=iYSize;
    iAmount=iXSize*iYSize;
    m_pRoutingCells=new int(iAmount);
    pTmpRoutingCells=new int(m_iXSize*m_iYSize);
    for (i=0; i<iAmount;i++)
    {
        m_pRoutingCells[i]=EMPTY;
    }

    iXQueue=new int(m_iXSize*m_iYSize);
    iYQueue=new int(m_iXSize*m_iYSize);
    m_iNetPriority=NULL;
    m_iPortAmount=NULL;
}

void CRoutingArea::SingleStepRouting(bool bBlackGrid)
{
    int     i,j,k;
#ifdef _DEBUG
    int     iDEBUG;
#endif

    for (k=0; k<m_iNetAmount; k++)//choose high priority net.
    {
        for (i=0; i<m_iXSize; i++)
        {
            for (j=0; j<m_iYSize; j++)
            {
                if ((i+j)%2==bBlackGrid) //the cell is black cell.
                {
#ifdef _DEBUG
                    iDEBUG=getCell(i,j);
#endif
                    if (getCell(i,j)==m_iNetPriority[k] || 
                        getCell(i,j)-PORTBASE==m_iNetPriority[k] )
                        Expand(m_iNetPriority[k],i,j);
                }
            }
        }
    }
}

void CRoutingArea::Expand(int iNet, int iPortX, int iPortY)
{
    if (iPortX-1>=0)
    {
        Occupy(iNet, iPortX-1, iPortY);
    }

    if (iPortY+1<m_iYSize)
    {
        Occupy(iNet, iPortX, iPortY+1);
    }

    if (iPortX+1<m_iXSize)
    {
        Occupy(iNet, iPortX+1, iPortY);
    }

    if (iPortY-1>=0)
    {
        Occupy(iNet, iPortX, iPortY-1);
    }
}

bool CRoutingArea::Occupy(int iNet, int iPosX, int iPosY)
{
    if (getCell(iPosX,iPosY)==EMPTY)
    {
        setCell(iPosX,iPosY, iNet);
        return true;
    }

    if (isnotBottleNeck(iPosX,iPosY)==true)
    {
        if (isHighPriority(iNet,getCell(iPosX,iPosY))==true)
        {
            if (isPortCell(iPosX,iPosY)==EMPTY)
            {
                setCell(iPosX,iPosY,iNet);
            }
        }
    }
    return false;
}

bool CRoutingArea::isHighPriority(int iSourceNet, int iNextNet)
{
    if (iNextNet==EMPTY)
        return true;
    if (abs(m_iNetPriority[iSourceNet])>abs(m_iNetPriority[iNextNet]))
        return true;
    else
        return false;
}

int CRoutingArea::isPortCell(int iXPos,int iYPos)
{
    if (abs(getCell(iXPos,iYPos))>=PORTBASE)
        return abs(getCell(iXPos,iYPos))-PORTBASE;
    else
        return EMPTY;
}

void CRoutingArea::ModifyPriority()
{
    int     i,iRouted, iRouting;
    int     *RoutedNetPriority, *RoutingNetPriority;

    iRouted=0; 
    iRouting=0;
    RoutedNetPriority=new int(m_iNetAmount);
    RoutingNetPriority=new int(m_iNetAmount);

    for (i=0;i<m_iNetAmount;i++)
    {
        if (isRouted(i)>0)
            RoutedNetPriority[iRouted++]=i;
        else
            RoutingNetPriority[iRouting++]=i;
    }

    for (i=0; i<iRouted; i++)
    {
    }

    for (i=0; i<iRouting; i++)
    {
    }
    delete[] RoutedNetPriority;
    delete[] RoutingNetPriority;
}

int CRoutingArea::isRouted(int iNet)
{
    int     i,j;
    int     iQueueStart,iQueueEnd,iAmount=0,iXPos,iYPos,iPortCount;

    for (i=0; i<m_iXSize*m_iYSize;i++)
    {
        pTmpRoutingCells[i]=m_pRoutingCells[i];
    }

    iPortCount=0;
    for (i=0; i<m_iXSize; i++)
    {
        for (j=0; j<m_iYSize; j++)
        {
            if (getCell(i,j,pTmpRoutingCells)==iNet || isPortCell(i,j)==iNet)
            {
                iXQueue[0]=i;    iYQueue[0]=j;
                iQueueStart=0;  iQueueEnd=1;
                iAmount++;
                
                if (isPortCell(i,j)==iNet)
                {
                    iPortCount++;
                    setCell(i,j,-iNet-PORTBASE,pTmpRoutingCells);
                }
                else
                    setCell(i,j,-iNet,pTmpRoutingCells);
                while (iQueueStart!=iQueueEnd)
                {
                    iXPos=iXQueue[iQueueStart];
                    iYPos=iYQueue[iQueueStart++];

                    if (iXPos-1>=0 && 
                        (getCell(iXPos-1,iYPos,pTmpRoutingCells)==getCell(iXPos,iYPos) ||
                        getCell(iXPos-1,iYPos,pTmpRoutingCells)==getCell(iXPos,iYPos)-PORTBASE))
                    {
                        iXQueue[iQueueEnd]=iXPos-1;
                        iYQueue[iQueueEnd++]=iYPos;
                        iAmount++;
                        setCell(iXPos-1,iYPos,-getCell(iXPos,iYPos),pTmpRoutingCells);
                        if (isPortCell(iXPos-1,iYPos)==iNet)
                            iPortCount++;
                    }

                    if (iXPos+1<m_iXSize && 
                        (getCell(iXPos+1,iYPos,pTmpRoutingCells)==getCell(iXPos,iYPos) ||
                        getCell(iXPos+1,iYPos,pTmpRoutingCells)==getCell(iXPos,iYPos)-PORTBASE))
                    {
                        iXQueue[iQueueEnd]=iXPos+1;
                        iYQueue[iQueueEnd++]=iYPos;
                        iAmount++;
                        setCell(iXPos+1,iYPos,-getCell(iXPos,iYPos),pTmpRoutingCells);
                        if (isPortCell(iXPos+1,iYPos)==iNet)
                            iPortCount++;
                    }

                    if (iYPos-1>=0 && 
                        (getCell(iXPos,iYPos-1,pTmpRoutingCells)==getCell(iXPos,iYPos) ||
                        getCell(iXPos,iYPos-1,pTmpRoutingCells)==getCell(iXPos,iYPos)-PORTBASE))
                    {
                        iXQueue[iQueueEnd]=iXPos;
                        iYQueue[iQueueEnd++]=iYPos-1;
                        iAmount++;
                        setCell(iXPos,iYPos-1,-getCell(iXPos,iYPos),pTmpRoutingCells);
                        if (isPortCell(iXPos,iYPos-1)==iNet)
                            iPortCount++;
                    }

                    if (iYPos+1<m_iYSize && 
                        (getCell(iXPos,iYPos+1,pTmpRoutingCells)==getCell(iXPos,iYPos) ||
                        getCell(iXPos,iYPos+1,pTmpRoutingCells)==getCell(iXPos,iYPos)-PORTBASE))
                    {
                        iXQueue[iQueueEnd]=iXPos;
                        iYQueue[iQueueEnd++]=iYPos+1;
                        iAmount++;
                        setCell(iXPos,iYPos+1,-getCell(iXPos,iYPos),pTmpRoutingCells);
                        if (isPortCell(iXPos,iYPos+1)==iNet)
                            iPortCount++;
                    }
                }


                if (iPortCount==m_iPortAmount[iNet])
                    return iAmount;
                else
                    return 0;
            }
            //广度优先遍历，如果找到的Port数等于线网Port数，则该线网已连接。并给出占用单元数
        }
    }

    return 0;
}

void CRoutingArea::Print()
{
    int     i,j;

    for (i=0; i<m_iYSize; i++)
    {
        for (j=0; j<m_iXSize; j++)
        {
            if (getCell(j,i)>=PORTBASE)
                printf("%d@",(getCell(j,i)-PORTBASE));
            else
            {
                if (abs(getCell(j,i))!=abs(EMPTY))
                    printf("%d",abs(getCell(j,i)));
                else
                    printf("-");
            }

            printf("\t");
        }
        printf("\n");
    }
}
/*

ostream& operator<<(ostream& os,CRoutingArea &Area)
{
    int     i,j;

    for (i=0; i<Area.m_iYSize; i++)
    {
        for (j=0; j<Area.m_iXSize; j++)
        {
            if (Area.getCell(j,i)>=PORTBASE)
                os<<(Area.getCell(j,i,.Area.m_pRoutingCells)-PORTBASE)<<"*";
            else
                os<<abs(Area.getCell(j,i,Area.m_pRoutingCells));

            os<<"\t";
        }
        os<<endl;
    }
    return os;
}

  */
/*
1. 待连接的线网应比已连接的线网扩展快，
2. 其它子线网的扩展必须不破坏任何已连接线网的连接性；
3. 为避免振荡，不允许任何两个子线网具有相同的优先度；
4. 不允许一个子线网扩展到另一子线网的节点所在的区域中。


Bottleneck. 沿一定方向搜索，若此8个单元中的线网号由中心单元的线网号变化为其它线网
号或未用单元、障碍单元的次数小于2次，则该单元一定不是瓶颈单元。

运用瓶颈单元概念，一个子线网要扩展到另一个线网已占的单元中必须满足下列条件：
(1). 该单元不是另一个线网的瓶颈单元；
(2). 扩展的线网应具有比已占该单元的线网更高的扩展优先权；
(3). 该单元不是另一个线网的节点；

在这种布线方法中，采用三种优先权：
(1). 未布通线网的子线网具有比已布线网更高的扩展优先权；
(2). 已布通线网的扩展优先权随其所占单元数的增加而减小；未布通线网的每个子线网
随着它们之间的距离缩短，扩展优先权上升；
*/