placement.cpp

uploading the file , the system will delete the file when time expires

#include "placement.h"
#include "rand32.h"
#include <math.h>

Placement::Placement(Netlist * nl) {
  this->nl = nl;
  celln = new int[nl->nCells];
  x     = new int[nl->nCells];
  y     = new int[nl->nCells];
  serial= new int[nl->nCells];
  disqualified = new bool[nl->nCells];
}

Placement::~Placement() {
  if(celln!=NULL) delete celln;
  if(x!=NULL) delete x;
  if(y!=NULL) delete y;
  if(serial!=NULL) delete serial;
  if(disqualified!=NULL) delete disqualified;

}

Placement * Placement::Clone() {
	Placement * myClone = new Placement(nl);
	myClone->myFitness = myFitness;
	for(int i=0;i<nl->nCells;i++) {
		myClone->celln[i] = celln[i];
		myClone->x[i] = x[i];
		myClone->y[i] = y[i];
		myClone->serial[i] = serial[i];
	}

	return myClone;
}

bool Placement::IsCloneOf(Placement * p) {
	// two placements are clones iff
	// for indexes i and j:
	// serial[i] == p->serial[j] =>
	// celln[i]  == p->celln[j]
	// IE all serial/celln pairs are identical,
	// regardless of ordering
	int i,j;

	for(int ser=0;ser<nl->nCells;ser++) {
		// find the index in this that correponsds to ser

		for(i=0;i<nl->nCells;i++) {
			if(serial[i]==ser) break;
		}

		// find the index in p that corresponds to ser
		for(j=0;j<nl->nCells;j++) {
			if(p->serial[j]==ser) break;
		}
//		printf("Serial %i is at %i in A and %i in B\n",ser,i,j);

		if(!(celln[i]==p->celln[j])) {
			// at least one difference here!
			return false;
		}

	}

	return true;
}

bool Placement::Crossover(Placement * a, Placement * b) {

//	printf("Crossingover has been invoked...");
	int i;
	Placement * temp_p;

	// initialize this placement to -1, and the disqualification
	// variables in a and b to false
	for(i=0;i<nl->nCells;i++) {
		celln[i] = -1;
		serial[i] = i;
		a->disqualified[i] = false;
		b->disqualified[i] = false;
	}

//	printf("Variables initialized\n");

	// select first parent randomly
	if(rand()%2==0) {
		// 50% of the time select b as first parent (a)
		temp_p = a;
		a = b;
		b = temp_p;
//		printf("Swapping parents!\n");
	}

	int nth_ser;
	int cur_ser;
	int cellnum;
	bool exists_in_child;
	bool xyz;

	// start the cyclic exchange process
	int unassigned_cells = nl->nCells;
	while(unassigned_cells>0) {
		
//		printf("Starting loop, unassiged cells = %i\n",unassigned_cells);

		// select a serial number ser_i in A 
		// corresponding to an index i that is not disqualified:
		// that is: a->y[i] is not == -1
		nth_ser = randOnRange(0,unassigned_cells-1);

		// find the index (i) of the nth unassiged serial number
		// in a
		cur_ser = -1;
		for(i=0;i<nl->nCells;i++) {
			if(!a->disqualified[i]) cur_ser++;
			if(cur_ser==nth_ser) break;
		}

//		printf("Selecting index %i to start with\n",i);

		xyz = true;
		while(xyz) {

			// give cell at a[i] to child at serial from a[i]
			celln[a->serial[i]] = a->celln[i];

//			printf("Giving Cell %i to child at index/serial = %i\n",a->celln[i],a->serial[i]);

			// disqualify cell at index [i] in a and at same serial in B
			// disqualify cell in A:
			a->disqualified[i] = true;

			// disqualify cell in B:
			cur_ser = b->DisqualifyCell(a->serial[i]);

			// decrement count of unassigned cells
			unassigned_cells--;

//			printf("A[%i] and B[%i] have been disqualified\n",i,cur_ser);

			// try to find b->celln[cur_ser] in the child (me)
			exists_in_child = false;
			cellnum = b->celln[cur_ser];
			for(i=0;i<nl->nCells;i++) {
				if(celln[i]==cellnum) {
					// already exists in child
					exists_in_child = true;
					break;
				} 
			}

			if(exists_in_child) {
				// swap A & B
//				printf("Cell exists in child: cycle over: swapping\n");
				temp_p = a;
				a = b;
				b = temp_p;
				xyz = false;
			} else {
				// find i st a->celln[i] == cellnum
				for(i=0;i<nl->nCells;i++) {
					if(a->celln[i]==cellnum) break;
				}

//				printf("Cell not in child, now giving cell %i\n",a->celln[i]);

				xyz = true;
			}
		}

	}

	rePlace();

	return true;
}

int Placement::DisqualifyCell(int cellnum) {
	for(int i=0;i<nl->nCells;i++) {
		if(serial[i]==cellnum) {
			disqualified[i] = true;
			return i;
		}
	}

	return -1;
}

bool Placement::Invert(int a, int b) {
	// param check
	if(a<0||a>=nl->nCells) return false;
	if(b<0||b>=nl->nCells) return false;
	if(a>=b) return false;

	int temp;
	// a and b inclusively specify the inversion bounds
	while(a<b) {
		// invert a and b
		
		// invert celln
		temp = celln[a];
		celln[a] = celln[b];
		celln[b] = temp;

		// invert x
		temp = x[a];
		x[a] = x[b];
		x[b] = temp;

		// invert y;
		temp = y[a];
		y[a] = y[b];
		y[b] = temp;

		// invert serial number
		temp = serial[a];
		serial[a] = serial[b];
		serial[b] = temp;

		a++;
		b--;
	}

	return true;

}

bool Placement::Mutate(int a, int b) {
	// check params
	if(a<0||a>=nl->nCells) return false;
	if(b<0||b>=nl->nCells) return false;
	if(a==b) return false;

	// swap the chromosomal positions of A and B,
	// then recalculate x & y positions of every cell
//	printf("Mutating cells %i and %i\n",celln[a]+1,celln[b]+1);

	int temp = celln[b];
	celln[b] = celln[a];
	celln[a] = temp;

//	temp = serial[b];
//	serial[b] = serial[a];
//	serial[a] = temp;

	rePlace();

	return true;
}

void Placement::Randomize() {
  // generate a random placement--this amounts to a
  // random sequence of genes, AKA a random ordering
  // of the cells
	int i;
  // use celln as assignment space--initialize to -1
  // use x as temporary space--initialize to cell #
	for( i=0;i<nl->nCells;i++) {
		x[i] = i;
		serial[i] = i;
	}

	// assign slots randomly
	int j,index;
	int cell;

	for(i=0;i<nl->nCells;i++) {
		cell = randOnRange(0,nl->nCells-i-1);
		
		// find the jth cell
		j = -1;
		index = -1;
		while(j!=cell) {
			index++;

			// skip all -1's
			while(x[index]==-1) 
				index++;

			// index points to first non- -1 entry, aka
			// the jth non- -1 entry
			j++;
		}

		celln[i] = x[index];
		x[index] = -1;
	}

	rePlace();


}

void Placement::rePlace() {
	// do the bookkeeping to assign x & y

	// NEXT OPEN SPOT
	int x_pos = 0;
	int y_pos = 0;

	// CURRENT ROW'S LENGTH
	int rowlen = 0;
	int i;

	for(int j=0;j<nl->nCells;j++) {
		// find the index i corresponding to serial number j
		i = 0;
		while(serial[i]!=j) i++;

		// i now is the index correpsonding to the current serial number
		// check to see if current cell will fit on current row
		if(rowlen+nl->cell_widths[celln[i]]<=nl->nRowMax) {
			// the cell won't fit on the current row
			x[i] = x_pos;
			y[i] = y_pos;

			// compute next open spot
			x_pos = x_pos + nl->cell_widths[celln[i]];

			// y_pos is unchanged
			rowlen += nl->cell_widths[celln[i]];
		} else {
			// the cell will not fit on the current row

			// place cell on next row
			y_pos = y_pos + nl->cell_height + nl->channel_height;
			
			x[i] = 0;
			y[i] = y_pos;

			rowlen = nl->cell_widths[celln[i]];

			x_pos = rowlen;
		}
	}
}

void Placement::dump(FILE * file) {
    int i,j,printed,printed_width;
	int last_y = 0;
	int size = nl->nCells;
	
	// unit size
	double unit_size = 75.0 / nl->nRowMax ;

	for(i=0;i<size;i++) {
		// i is the current cell we're printing
		for(j=0;j<size;j++) {
			// j is where we're looking for i
			if(serial[j]==i) break;
		}

		if(y[j]!=last_y) {
			last_y = y[j];
			fprintf(file,"\n");
		}

		// the cell's data is at celln[j], x[j], etc...

		// figure out how much space each cell can occupy
		printed_width = (int) (unit_size * nl->cell_widths[celln[j]]);
		printed = fprintf(file,"<");
		while(printed<printed_width/2) printed+=fprintf(file,"-");
		printed += fprintf(file,"%i",celln[j]+1);
		while(printed+1<printed_width) printed+=fprintf(file,"-");
		fprintf(file,">");

	}

	fprintf(file,"\n");

}

void Placement::dumpLiteral(FILE * file) {
	int i;
	for( i=0;i<nl->nCells;i++) {
		fprintf(file,"%i\t",celln[i]+1);
	}

	fprintf(file,"\n");
	
	for( i=0;i<nl->nCells;i++) {
		fprintf(file,"%i\t",x[i]);
	}

	fprintf(file,"\n");

	for( i=0;i<nl->nCells;i++) {
		fprintf(file,"%i\t",y[i]);
	}

	fprintf(file,"\n");

	for( i=0;i<nl->nCells;i++) {
		fprintf(file,"%i\t",serial[i]);
	}

	fprintf(file,"\n");
}

#define HORIZ_WEIGHT   1
#define VERT_WEIGHT    1

double Placement::Fitness() {
	// since this implementation assumes nothing about the
	// I/O layout of blocks, assume the average-case I/O placement--
	// that is, all connections go to the geographic middle of
	// of a given cell

	// ASSUME additional weight of hoziontal nets is HORIZ_WEIGHT
	// ASSUME additional weight of vert nets is VERT_WEIGHT

	// fitness is just the reciprical of the total weighted manhattan
	// interconnect span of all nets
	long interconnect = 0;
	int leftmost,rightmost,topmost,bottommost,span;

	int x_eff, y_eff;

	// find the weighted manhattan interconnect span of each net
	for(int net=0;net<nl->nNets;net++) {
		leftmost = topmost = 0x7FFFFFFF;
		rightmost = bottommost = -1;
		for(int cell=0;cell<nl->nconnections[net];cell++) {
			// the coordinates of the center of a cell is given by
			// x = (x_cell + cell_width) / 2
			// y = y_cell + CELL_HEIGHT / 2

			x_eff = (x[cell]+nl->cell_widths[cell]) >> 1;
			y_eff =  y[cell] + ( nl->cell_height >> 1 );

			// check superlatives
			
			// if left of leftmost
			if(x_eff<leftmost) leftmost = x_eff;

			// if right of rightmost
			if(x_eff>rightmost) rightmost = x_eff;

			// if below bottommost
			if(y_eff>bottommost) bottommost = y_eff;

			// if above topmost
			if(y_eff<topmost) topmost = y_eff;
		}
		span = HORIZ_WEIGHT * (rightmost-leftmost) +
			   VERT_WEIGHT  * (bottommost-topmost);

		// weight according to net weight
		span *= nl->net_weights[net];

		interconnect += span;

	}


	return 1.0 / interconnect;
}