kl.c.tar.gz_KL_KL algorithm_KL vlsi_aplacer_vlsi

#include<stdio.h> #include<stdlib.h> #define MAX 101 int main() { int i,j,k,node1,node2,alliter; long int maxgain; int net1[MAX],net2[MAX],a[MAX][MAX]; /*int a[MAX][MAX]={ 0,0,0,0,0,0,0, 0,0,1,2,3,2,4, 0,1,0,1,4,2,1, 0,2,1,0,3,2,1, 0,3,4,3,0,4,3, 0,2,2,2,4,0,2, 0,4,1,1,3,2,0};*/ long int gain[MAX][MAX]; int inter[MAX]; int ext[MAX]; int d[MAX]; int node_stat[MAX][3]; //int net1[MAX]={0,1,2,3,0,0,0}; //int net2[MAX]={0,0,0,0,4,5,6}; //int net1[MAX]={0,1,2,3,0,0,0}; //int net2[MAX]={0,0,0,0,4,5,6}; for(i=0;i<MAX;i++) { for(j=0;j<=i+1;j++) { if(i==0) a[i][j]=0; else if(j==0) a[i][j]=0; else if(i==j) { a[i][j]=0; } else a[i][j]=random()%50; } } for(i=MAX-1;i>=0;i--) { for(j=MAX-1;j>=i;j--) { a[i][j]=a[j][i]; } } printf("|"); for(i=0;i<(MAX+1)/2;i++) { net1[i]=i; net2[i]=0; node_stat[i][0]=i; node_stat[i][1]=(i!=0)?1:0; node_stat[i][2]=0; //printf(" %d %d %d %d %d \n",net1[i],net2[i],node_stat[i][0],node_stat[i][1],node_stat[i][2]); } for(i=(MAX+1)/2;i<MAX;i++) { net2[i]=i; net1[i]=0; node_stat[i][0]=i; node_stat[i][1]=2; node_stat[i][2]=0; //printf(" %d %d %d %d %d \n",net1[i],net2[i],node_stat[i][0],node_stat[i][1],node_stat[i][2]); } /*int node_stat[MAX][3]={ 0,0,0, 1,1,0, 2,1,0, 3,1,0, 4,2,0, 5,2,0, 6,2,0};*/ for(i=0;i<MAX;i++) { for(j=0;j<MAX;j++) { //printf(" %d ",a[i][j]); } //printf("\n"); } alliter=0; while(alliter+1 < MAX) { //printf("External Internal Difference\n"); for(i=0;i<MAX;i++) { ext[i]=0; inter[i]=0; if(node_stat[i][1]==1) { for(j=0;j<MAX;j++) { ext[i]+=a[i][net2[j]]; } for(k=0;k<MAX;k++) { inter[i]+=a[i][net1[k]]; } } else if(node_stat[i][1]==2) { for(j=0;j<MAX;j++) { ext[i]+=a[net1[j]][i]; } for(k=0;k<MAX;k++) { inter[i]+=a[net2[k]][i]; } } d[i]=ext[i]-inter[i]; //printf("%d \t %d \t %d\n",ext[i],inter[i],d[i]); } maxgain=-2147483647; //free(maxgain); //maxgain=(int *)realloc(maxgain,sizeof(int)); node1=0; node2=0; for(i=0;i<MAX;i++) { for(j=0;j<MAX;j++) { if(net1[i]==0 || net2[j]==0 || node_stat[i][2]==1 || node_stat[j][2]==1){ gain[i][j]=0; } else { gain[i][j]=d[net1[i]]+d[net2[j]]-2*(a[net1[i]][net2[j]]); if(maxgain<gain[i][j]) { maxgain=gain[i][j]; node1=i; node2=j; } } //printf(" %d ",gain[i][j]); } //printf("\n"); } printf("Maximum gain : %d \t Exchange %d and %d \n",maxgain,node1,node2); net1[node1]=0; net2[node1]=node1; net2[node2]=0; net1[node2]=node2; node_stat[node1][1]=2; node_stat[node2][1]=1; node_stat[node1][2]=1; node_stat[node2][2]=1; alliter=alliter+2; } }