file: mincut.cc
/* VLSI CAD Project 3 */
/* Placement Tool */
/* Recursive MinCut */
/* Fall 2000 Anno Domini */
/* Written by Suraj Sudhir */
/* ssudhir@ece.cmu.edu */
#include "main.h"
///////////////////////////////////
//main recursive mincut procedure//
///////////////////////////////////
void recursiveMinCut(MetisIntfc metis, int BasePartitionNum, int partSX, int partSY, int partEX, int partEY)
{
int i,j;
int *ModList, *PadList;
int gateCount=0;
double WireLen1, WireLen2;
int Area11, Area12, Area13, Area14, Area21, Area22;
double fracLen, fracGateLen;
double UBFactor;
int violations = 0;
int ModWeight;
double ratio1, ratio2;
int quadOK;
int NumPart = 0;
//often happens with 4-way partitioning
//swap the coordinate. should fix things...
if ( NumPartitions == QUAD )
{
if (( partEX < partSX ) || ( partEY < partSY ))
{
int temp1, temp2;
temp1 = partSX; temp2 = partSY;
partSX = partEX;
partSY = partEY;
partEX = temp1;
partEY = temp2;
}
}
//everything modweight 1
ModWeight = 1;
//check if this can be partitioned 4-way
//needs atleast 2 rows and columns
if ( NumPartitions == QUAD )
{
if ((partEX-partSX)&&(partEY-partSY))
quadOK = 1;
else
quadOK = 0;
for (i=0;i<NumGates;i++)
{
if ( gatePart[i] == BasePartitionNum )
{
//printf("in this partition: %d\n",i);
NumPart++;
}
}
}
printf("Bounding Box: %d %d %d %d\n", partSX, partSY, partEX, partEY);
//couldnt do this in time :(
//quadPlace(BasePartitionNum, partSX, partSY, partEX, partEY);
//if I want to step thru the mincut...
//can see each stage of cut
if ( StepThru )
drawChip();
//just one square
if ( (partSX == partEX) && (partSY == partEY) )
return;
//no gates in this box
if ((NumPartitions == QUAD) && !NumPart)
return;
//compute based on what i'm optimizing for
if ( Optimization == MIN_WIRELENGTH )
computeWireLen(1,0);
if ( Optimization == MIN_DELAY )
computeWireDelay();
//cut in the (integer) middle of the partition
int tempX = partSX + (partEX-partSX)/2, tempY = partSY + (partEY-partSY)/2;
//do both vertical and horizontal cut.
//pick the best, and use it
//if both yield same, then make cut perpendicular
//to previous recursion level cut
//add each of the gates into metis
//along with the weights and partitions
for(i=0;i<NumGates;i++)
{
//insert gates only once; set partitions and weights
//on each iteration
if ( FirstRound )
metis.AddModule(i+1);
if ( gatePart[i] != BasePartitionNum )
{
//for vertical cut place cutline
if (( NumPartitions == DUAL ) || ((NumPartitions == QUAD) && !quadOK))
{
if ( gateX[i] <= tempX )
metis.setModPartition(i+1,0);
else
metis.setModPartition(i+1,1);
}
else //assume quad only, nothing else
{
//4 quadrants, 4 partition zones...
if( ( gateX[i] <= tempX ) && ( gateY[i] <= tempY ) )
metis.setModPartition(i+1,0);
else if ( ( gateX[i] > tempX ) && ( gateY[i] <= tempY ) )
metis.setModPartition(i+1,1);
else if ( ( gateX[i] <= tempX ) && ( gateY[i] > tempY ) )
metis.setModPartition(i+1,2);
else
metis.setModPartition(i+1,3);
}
metis.setModWeight(i+1,0);
}
else
{
//within partition - movable
metis.setModPartition(i+1,-1); //movable
metis.setModWeight(i+1,ModWeight);
}
}
//pad information to be added to metis
for(i=0;i<NumPinsConnNets;i++)
{
if ( FirstRound )
metis.AddPad(i+1);
//all pads 0 weight
metis.setPadWeight(i+1,0);
//set partition info according to k-way parameters
if (( NumPartitions == DUAL ) || ((NumPartitions == QUAD) && !quadOK))
{
if ( PinConnList[i].xSite <= tempX )
metis.setPadPartition(i+1,0);
else
metis.setPadPartition(i+1,1);
}
else //4-way
{
if ( (PinConnList[i].xSite <= tempX ) && (PinConnList[i].ySite <= tempY) )
metis.setPadPartition(i+1,0);
else if ( (PinConnList[i].xSite > tempX ) && (PinConnList[i].ySite <= tempY) )
metis.setPadPartition(i+1,1);
else if ( (PinConnList[i].xSite <= tempX ) && (PinConnList[i].ySite > tempY) )
metis.setPadPartition(i+1,2);
else
metis.setPadPartition(i+1,3);
}
}
for(i=0;i<NumNets;i++)
{
//add net info
//probably time consuming due to linked list chase...
//but doing it just once, so not an issue
if ( FirstRound )
{
ModList = (int *)malloc(sizeof(int) * GatesPerNet[i]);
PadList = (int *)malloc(sizeof(int) * PadsPerNet[i]);
netList *netTemp = &NetArr[i];
for(j=0;j<GatesPerNet[i];j++)
{
// only those gates that are in the current
// partition
ModList[j] = netTemp->GateID+1;
netTemp = netTemp->next;
}
padList *pTemp = &PadArr[i];
for(j=0;j<PadsPerNet[i];j++)
{
PadList[j] = pTemp->PadID;
pTemp = pTemp->next;
}
metis.AddNet(i+1,GatesPerNet[i],ModList,PadsPerNet[i],PadList);
free(ModList);
free(PadList);
}
//set net weight depending on optimization
if ( Optimization == MIN_CONGESTION )
metis.setNetWeight(i+1,getFanout(i));
else if ( Optimization == MIN_WIRELENGTH )
{
if ( NetWeight == CONSTR )
metis.setNetWeight(i+1,((netLen[i] > 6) ? 6 : (int)netLen[i]));
else if ( NetWeight == UNCONSTR )
metis.setNetWeight(i+1, netLen[i]);
else
metis.setNetWeight(i+1,NetWeight);
}
else if ( Optimization == MIN_DELAY )
metis.setNetWeight(i+1, netDelay[i]*100);
}
//if i wanna minimize the critical path
if ( CriticalPathMinimize )
{
for(i=0;i<NumTimingPaths;i++)
{
for(j=0;j<TimingPaths[i].NumObjects;j++)
{
if (j%2)
continue;
else
{
if ( Optimization == MIN_CONGESTION )
metis.setNetWeight(i+1,getFanout(i)+2);
else if ( Optimization == MIN_WIRELENGTH )
{
if ( NetWeight == CONSTR )
metis.setNetWeight(i+1,((netLen[i] > 6) ? 6 : (int)netLen[i])+2);
else if ( NetWeight == UNCONSTR )
metis.setNetWeight(i+1, netLen[i]+2);
else
metis.setNetWeight(i+1,NetWeight+2);
}
else if ( Optimization == MIN_DELAY )
metis.setNetWeight(i+1, netDelay[i]*200);
}
}
}
}
//setting options
//area of the partition, for balancing
if ( NumPartitions == DUAL )
{
Area11 = (tempX-partSX+1)*(partEY-partSY+1);
Area12 = (partEX-tempX)*(partEY-partSY+1);
UBFactor = (abs(Area11 - Area12))*50.0/(Area11 + Area12);
}
else
{
Area11 = (tempX-partSX+1)*(tempY-partSY+1);
Area12 = (partEX-tempX)*(tempY-partSY+1);
Area13 = (tempX-partSX+1)*(partEY-tempY);
Area14 = (partEX-tempX)*(partEY-tempY);
UBFactor = (abs(Area11 - Area14))*25.0/(Area11 + Area12 + Area13 + Area14);
}
if (UBFactor < 5.0)
UBFactor = 5.0;
else if (UBFactor > 49.0)
UBFactor = 49.0;
//dont play with this now.. just use default
//maybe fix up for clustering
metis.SetOption("CType", 1);
metis.SetOption("RType", 1);
//max tolerance, to get best cut
metis.SetOption("UBfactor", UBFactor);
metis.SetOption("Seed", Seed);
//I'm done with initializing
FirstRound = 0;
//partition
if (( NumPartitions == QUAD ) && quadOK )
metis.Partition(NumPartitions);
else
metis.Partition(2);
for (i=0,j=0;i<NumGates;i++)
if ( gatePart[i] == BasePartitionNum )
{
tempPart1[i] = metis.getModPartition(i+1);
}
//should hopefully fix the cut...
tempX = partSX + (partEX-partSX)/2;
tempY = partSY + (partEY-partSY)/2;
int violationFlag=0;
//see if partition fits into area, if not flag for
//balancing stuff
if (NumPartitions == DUAL)
violationFlag = foundViolations (BasePartitionNum*2+1,1,Area11, Area12);
else
violationFlag = foundViolations (BasePartitionNum*4+1,1,Area11, Area12);
//move to center-of-gravity
for (i=0;i<NumGates;i++)
{
if ( gatePart[i] == BasePartitionNum )
{
if (!tempPart1[i])
{
if (( NumPartitions == DUAL ) || ((NumPartitions == QUAD) && !quadOK))
tempX1[i] = tempX - (tempX-partSX)/2;
else
{
tempX1[i] = tempX - (tempX-partSX)/2;
tempY1[i] = tempY - (tempY-partSY)/2;
}
}
else
{
if (( NumPartitions == DUAL ) || ((NumPartitions == QUAD) && !quadOK))
{
// just this case
tempX1[i] = tempX + (partEX-tempX)/2;
if (!((partEX-tempX)/2) && !violationFlag)
tempX1[i] += 1;
}
else
{
//three more cases
if ( tempPart1[i] == 1 )
{
tempX1[i] = tempX + (partEX-tempX)/2 + 1;
if ( tempX1[i] > partEX )
tempX1[i]--;
tempY1[i] = tempY - (tempY-partSY)/2;
}
else if ( tempPart1[i] == 2 )
{
tempY1[i] = tempY + (partEY-tempY)/2 + 1;
if ( tempY1[i] > partEY )
tempY1[i]--;
tempX1[i] = tempX - (tempX-partSX)/2;
}
else
{
tempX1[i] = tempX + (partEX-tempX)/2 + 1;
if ( tempX1[i] > partEX )
tempX1[i]--;
tempY1[i] = tempY + (partEY-tempY)/2 + 1;
if ( tempY1[i] > partEY )
tempY1[i]--;
}
}
}
if (( NumPartitions == DUAL ) || ((NumPartitions == QUAD) && !quadOK))
tempY1[i] = tempY;
gateX[i] = tempX1[i];
gateY[i] = tempY1[i];
}
}
//partition numbering scheme
for(i=0;i<NumGates;i++)
if ( gatePart[i] == BasePartitionNum )
{
if ( ( NumPartitions == QUAD ) && quadOK )
gatePart[i] = gatePart[i]*4+1+tempPart1[i];
}
//only one partitioning step if 4-way
if (( NumPartitions == QUAD ) && quadOK)
{
//fix up violations and do next recursion
printf("4-Way Cut\n");
fixQuadViolations(BasePartitionNum*4+1, partSX, partSY, partEX, partEY, Area11, Area12, Area13, Area14);
recursiveMinCut(metis, BasePartitionNum*4+1, partSX, partSY, tempX, tempY);
recursiveMinCut(metis, BasePartitionNum*4+2, tempX+1, partSY, partEX, tempY);
recursiveMinCut(metis, BasePartitionNum*4+3, partSX, tempY+1, tempX, partEY);
recursiveMinCut(metis, BasePartitionNum*4+4, tempX+1, tempY+1, partEX, partEY);
return;
}
//try moving the cutline to see if it fits better
if (violationFlag)
{
printf("violation1\n");
Area11 = (tempX-partSX)*(partEY-partSY+1);
Area12 = (partEX-tempX+1)*(partEY-partSY+1);
}
violations = violationFlag;
WireLen1 = computeWireLen(0,0);
//setup for horizontal cut
//pads...
for(i=0;i<NumPinsConnNets;i++)
{
if ( PinConnList[i].ySite < (partSY + (partEY-partSY)/2) )
metis.setPadPartition(i+1,0);
else
metis.setPadPartition(i+1,1);
}
//gates...
for(i=0;i<NumGates;i++)
{
if ( gatePart[i] != BasePartitionNum )
{
if ( gateY[i] < (partSY + (partEY-partSY)/2) )
metis.setModPartition(i+1,0);
else
metis.setModPartition(i+1,1);
metis.setModWeight(i+1,0);
}
else
{
metis.setModPartition(i+1,-1); //movable
metis.setModWeight(i+1,ModWeight);
}
}
//nets...
for(i=0;i<NumNets;i++)
if ( Optimization == MIN_CONGESTION )
metis.setNetWeight(i+1,getFanout(i));
else if ( Optimization == MIN_WIRELENGTH )
{
if ( NetWeight == CONSTR )
metis.setNetWeight(i+1,((netLen[i] > 6) ? 6 : (int)netLen[i]));
else if ( NetWeight == UNCONSTR )
metis.setNetWeight(i+1, netLen[i]);
else
metis.setNetWeight(i+1,NetWeight);
}
else if ( Optimization == MIN_DELAY )
metis.setNetWeight(i+1, netDelay[i]*100);
if ( CriticalPathMinimize )
for(i=0;i<NumTimingPaths;i++)
{
for(j=0;j<TimingPaths[i].NumObjects;j++)
{
if (j%2)
continue;
else
{
if ( Optimization == MIN_CONGESTION )
metis.setNetWeight(i+1,getFanout(i)+2);
else if ( Optimization == MIN_WIRELENGTH )
{
if ( NetWeight == CONSTR )
metis.setNetWeight(i+1,((netLen[i] > 6) ? 6 : (int)netLen[i])+2);
else if ( NetWeight == UNCONSTR )
metis.setNetWeight(i+1, netLen[i]+2);
else
metis.setNetWeight(i+1,NetWeight+2);
}
else if ( Optimization == MIN_DELAY )
metis.setNetWeight(i+1, netDelay[i]*200);
}
}
}
//area of partitions after this cut
Area21 = (tempY-partSY+1)*(partEX-partSX+1);
Area22 = (partEY-tempY)*(partEX-partSX+1);
UBFactor = (abs(Area21 - Area22))*50.0/(Area21 + Area22);
if (UBFactor < 5.0)
UBFactor = 5.0;
else if (UBFactor > 49.0)
UBFactor = 49.0;
//setting options
//keep this default for now...
metis.SetOption("CType", 1);
metis.SetOption("RType", 1);
//set up balancing tolerance
metis.SetOption("UBfactor", UBFactor);
//seed dynamics, just to see what it does..
metis.SetOption("Seed", Seed);
//bipartition again
//4-way will not reach here
//if it somehow did, something is
//_very_ wrong!!
metis.Partition(2);
for (i=0,j=0;i<NumGates;i++)
if ( gatePart[i] == BasePartitionNum )
tempPart2[i] = metis.getModPartition(i+1);
//see if partition is violated
if ( NumPartitions == DUAL )
violationFlag = foundViolations (BasePartitionNum*2+1, 2, Area21, Area22);
else
violationFlag = foundViolations (BasePartitionNum*4+1, 2, Area21, Area22);
//move to C-O-G of new partitions
for (i=0;i<NumGates;i++)
{
if ( gatePart[i] == BasePartitionNum )
{
if (!tempPart2[i])
{
tempY2[i] = tempY - (tempY-partSY)/2;
}
else
{
tempY2[i] = tempY + (partEY-tempY)/2;
if (!((partEY-tempY)/2) && !violationFlag)
tempY2[i] += 1;
}
tempX2[i] = tempX;
gateY[i] = tempY2[i];
gateX[i] = tempX2[i];
}
}
//move cutline for better fit
if ( violationFlag )
{
printf("violation!\n");
Area21 = (tempY-partSY)*(partEX-partSX+1);
Area22 = (partEY-tempY+1)*(partEX-partSX+1);
}
violations += violationFlag*2;
WireLen2 = computeWireLen(0,0);
fflush(stdout);
//select the best cut and save:
//1.partition number
//2.gateX, gateY
//if a legal mincut cant be made, force the other cut
if ((WireLen1<=WireLen2) && (partEX == partSX) && !Rotate)
Rotate = 1;
else if ((WireLen1>=WireLen2) && (partEY == partSY) && Rotate)
Rotate = 0;
else if ((WireLen1 < WireLen2) && (partSX != partEX))
Rotate = 0;
else if ((WireLen1 == WireLen2) && (partEX != partSX))
{
if (partEY != partSY)
if ( Rotate )
Rotate = 0;
else
Rotate = 1;
else
if ( Rotate )
Rotate = 0;
}
else if ((WireLen1 > WireLen2 ) && (partSY != partEY) )
Rotate = 1;
else if ((WireLen1 == WireLen2) && (partSY != partEY) )
{
if ( partSX != partEX )
if ( Rotate )
Rotate = 0;
else
Rotate = 1;
else
if ( !Rotate )
Rotate = 1;
}
if ( !Rotate )
{
//final position at this point
for ( i=0;i<NumGates;i++)
{
if (gatePart[i] == BasePartitionNum )
{
gateX[i] = tempX1[i];
gateY[i] = tempY1[i];
}
}
printf("Vertical Cut\n");
//setup gate partition accordingly
for(i=0;i<NumGates;i++)
{
if ((gatePart[i] == BasePartitionNum) && (NumPartitions == DUAL))
gatePart[i] = gatePart[i]*2+tempPart1[i]+1;
else if ((gatePart[i] == BasePartitionNum) && (NumPartitions == QUAD) && !quadOK)
gatePart[i] = gatePart[i]*4+tempPart1[i]+1;
else if ((gatePart[i] == BasePartitionNum) && (NumPartitions == QUAD))
gatePart[i] = gatePart[i]*4+tempPart1[i]+1;
}
//fix any gatesite violation
if ( NumPartitions == DUAL )
fixCapacityViolations(BasePartitionNum*2+1, Area11, Area12);
else
fixCapacityViolations(BasePartitionNum*4+1, Area11, Area12);
int tempVar = (partEX-partSX)/2;
int NewPartition;
if ( NumPartitions == DUAL )
NewPartition = BasePartitionNum*2 + 1;
else
NewPartition = BasePartitionNum*4 + 1;
//if ( violations && ( violations % 2 ))
// {
// recursiveMinCut(metis, NewPartition,partSX,partSY,partSX + tempVar - 1,partEY);
// recursiveMinCut(metis, NewPartition+1,partSX + tempVar,partSY,partEX,partEY);
// }
// else
{
recursiveMinCut(metis, NewPartition,partSX,partSY,partSX + tempVar,partEY);
recursiveMinCut(metis, NewPartition+1,partSX + tempVar + 1,partSY,partEX,partEY);
}
}
else
{
//for the next time..
if ((WireLen1 == WireLen2) && Rotate )
Rotate = 0;
//gate positions at this point
for ( i=0;i<NumGates;i++)
{
if (gatePart[i] == BasePartitionNum )
{
gateX[i] = tempX2[i];
gateY[i] = tempY2[i];
}
}
printf("Horizontal Cut\n");
//partition info
for(i=0;i<NumGates;i++)
{
if ((gatePart[i] == BasePartitionNum) && (NumPartitions == DUAL))
gatePart[i] = gatePart[i]*2+tempPart2[i]+1;
else if ((gatePart[i] == BasePartitionNum) && (NumPartitions == QUAD) && !quadOK)
gatePart[i] = gatePart[i]*4+tempPart2[i]+1;
else if ((gatePart[i] == BasePartitionNum) && (NumPartitions == QUAD))
gatePart[i] = gatePart[i]*4+tempPart2[i]+1;
}
if ( NumPartitions == DUAL )
fixCapacityViolations(BasePartitionNum*2+1, Area21, Area22);
else
fixCapacityViolations(BasePartitionNum*4+1, Area21, Area22);
int tempVar = (partEY-partSY)/2;
int NewPartition;
if ( NumPartitions == DUAL )
NewPartition = BasePartitionNum*2 + 1;
else
NewPartition = BasePartitionNum*4 + 1;
//if (violations && !(violations % 2) )
// {
// recursiveMinCut(metis, NewPartition,partSX,partSY,partEX,partSY + tempVar - 1);
// recursiveMinCut(metis, NewPartition+1,partSX,partSY + tempVar,partEX,partEY);
// }
// else
{
recursiveMinCut(metis, NewPartition,partSX,partSY,partEX,partSY + tempVar);
recursiveMinCut(metis, NewPartition+1,partSX,partSY + tempVar + 1,partEX,partEY);
}
}
}
C++ to HTML Conversion by ctoohtml