/*Copyright 2008 UC Regents. Permission to use or modify is granted for education and research purposes only. 
Any other use requires explicit permission. Contact Frank Vahid at vahid@cs.ucr.edu with questions.
For publications derived from these materials, kindly cite the following:
C. Huang and F. Vahid. Dynamic Coprocessor Management for FPGA-Enhanced Compute Platforms. 
IEEE/ACM Int. Conf. on Compilers, Architectures, and Synthesis for Embedded Systems (CASES), Oct 2008.*/

/* simulator for Dynamic coprocessor management problem
   Author: Chen Huang
   Advisor: Prof. Frank Vahid
   University of California, Riverside*/

#include <stdio.h>
#include <stdlib.h> 
#include <time.h> 
#include <cmath>

//defination
#define INF 1000000000000000.0
#define TASKNO 1000                    //the number of task queue
#define TASKTYPE 11                    //the number of task type
#define SNO 1                          //the number of simulation
#define FRE 1000000000                 //processor speed

int move_time[10];
int task[TASKNO];
double area = 5500;                    // total size
double t = 0.05/area;                  //transfer cost per gate(reconfiguration overhead)

/*double apps[TASKTYPE][5] =           //energe
{{1200723.75,  165092.5125,  1,  1,  1889},
{1404615.975,  451208,       1,  1,  2232},
{20778523.84,  2162545.125,  1,  1,  4513},
{272707915,    122376002,    1,  1,  2122},
{53298322.14,  3949257.293,  1,  1,  2274}
}; */

double apps[TASKTYPE][5] =             //apps: ori time, new time, ori energy, new energy, size
{{80502359,    33972359,    1,     1,     4770},
{348959508,   23766604,    1,     1,     3393},
{150019667,   6986215,     1,     1,     2991},
{70333614,    44899628,    1,     1,     2759},
{2668275,     375125,      1,     1,     1889},
{2860725,     904225,      1,     1,     2232},
{25376800,    2559225,     1,     1,     4513},
{4197443675,  1883577075,  1,     1,     2122},
{70138600,    5197075,     1,     1,     2274}
};  

/*double apps[TASKTYPE][5] =           //raw data set
{{16000000,	12700000,	1,	1,	29000},
{ 32000000,	4570000,	1,	1,	42000},
{ 4490000,	641000,	        1,	1,	47000},
{ 4000000, 	444000,	        1,	1,	4000},
{ 64000000,	1230000,	1,	1,	22000},
{ 63900000,	460000,	        1,	1,	42000},
{ 4110000,	46000,  	1,	1,	10000},
{ 10000000,	3850000,	1,	1,	14000},
{ 2000000, 	500000,	        1,	1,	14000},
{ 15980000,	2000000,        1,	1,	44000},
{ 15980000,	1140000,	1,	1,	56000}
};  */

/*double apps[TASKTYPE][5] =
{{16,	12.7,	1,	1,	29000},
{32,	4.57,	1,	1,	42000},
{4.49,	0.641,	1,	1,	47000},
{4, 	0.444,	1,	1,	4000},
{64,	1.23,	1,	1,	22000},
{63.9,	0.46,	1,	1,	42000},
{4.11,	0.046,	1,	1,	10000},
{10,	3.85,	1,	1,	14000},
{2, 	0.5,	1,	1,	14000},
{15.98,	2,	1,	1,	44000},
{15.98,	1.14,	1,	1,	56000}
}; */

//task generator
void randomtask()                       //task generator: random
{
	int i;
	srand(time(NULL));
	for(i = 0; i < TASKNO; i++)
	{
		task[i] = rand() % TASKTYPE;
	}
}

void biastask(double a, double b)      //task generator: biased
{          
	int i, j, r;
	int k = int(TASKTYPE * a);
	srand(time(NULL));    
	for(i = 0; i < TASKNO; i++)
	{
		r = rand() % 1000;
		if(r < b * 1000)
		{
			if(k == 0)
				j = 0;
			else
				j = rand() % k;
			task[i] = j;
		}
		else
		{
			j = rand() % TASKTYPE;
			while(j <= (TASKTYPE * a))
				j = rand() % TASKTYPE;
			task[i] = j;
		}
	}
}

void periodtask(int a)                 //task generator: period
{
	int i;
	srand(time(NULL));
	int seq[TASKNO];
	for(i = 0; i < a; i++)
	{
		seq[i] = rand() % TASKTYPE;
	}
	task[0] = seq[0];
	for(i = 1; i < TASKNO; i++)
	{
		task[i] = seq[i % a];
	}
}

//algorithms
double simu_greedy()                   //greedy algorithm, all speed up, priority replacement, return the total time
{
	int i, j, s, s1, move=0,ta = 0,minj;
	double min;
	double total = 0;
	double use=0;
        int cop[TASKTYPE];
	double pri[TASKTYPE];
	for(i=0;i<TASKTYPE;i++)
	{
		cop[i]=0;              //init coprocessors, 1 enable.
		pri[i]=apps[i][0]/apps[i][1];
	}

	for(i = 0; i < TASKNO; i++)    //execute the app queue
	{
		ta=task[i];
        	if(cop[ta])            //already in cop
			total+=apps[ta][1];
		else                   //not in the cop, put it in
		{
			if((use+apps[ta][4])<area)  // can put it in
			{
				use+=apps[ta][4];
				cop[ta]=1;
				total=total+apps[ta][1]+t*apps[ta][4]*FRE;
				move++;
			}
			else           //cannot put it in, priority replacement
			{
				if(apps[ta][4]>area)  //can not put it in
				{
					total=total+apps[ta][0];
					continue;
				}
				while((use+apps[ta][4])>area)
				{
					min=INF;
					for(j=0;j<TASKTYPE;j++)
					{
						if(cop[j] && pri[j]<min)
						{
							min=pri[j];
							minj=j;
						}
					}
					use-=apps[minj][4];
					cop[minj]=0;
				}
				use+=apps[ta][4];
				cop[ta]=1;
				total=total+apps[ta][1]+t*apps[ta][4]*FRE;
				move++;
			}
		}
	}
	move_time[4]=move;
	return total;
}
 
double simu_benefit()                  //cumulative benefit algorithm, return total time
{
        int i,j,ta,minj,flag,move=0;
	double benefit[TASKTYPE];
	int cop[TASKTYPE];
	int cop1[TASKTYPE];
	double total=0,use=0,min,use1=0;
	double save,rs;
	double a,b;
	int cc;
	double tasktime=0;
	for(i=0,cc=0;i<TASKTYPE;i++)
	{
		cc+=apps[i][4];
		tasktime+=apps[i][0];
		tasktime+=apps[i][1];
	}
	cc=cc/TASKTYPE;
	tasktime=tasktime/TASKTYPE/FRE/2;
	double tc=t*cc;
	for(i=0,b=0;i<TASKTYPE;i++)
	{
		benefit[i]=0;          //init counter
		cop[i]=0;
		cop1[i]=0;
	}
	for(i=0;i<TASKNO;i++)
	{
		ta=task[i];
        	benefit[ta]=benefit[ta]+(apps[ta][0]-apps[ta][1]);  //update the benefit table
		if(cop[ta])            //if it is in the cop, just run
			total+=apps[ta][1]; 
		else                   //not in the cop
		{
			if((use+apps[ta][4])<area && benefit[ta]>t*apps[ta][4]*FRE)  //can put in, put it in
			{
				use+=apps[ta][4];
				cop[ta]=1;
				total=total+apps[ta][1]+t*apps[ta][4]*FRE;
				move++;
			}
			else           //can not put it in, decide whether reconfigure
			{
				flag=1;
				min=INF;
				use1=use;  //backup
				for(j=0;j<TASKTYPE;j++)
				{
					if(cop[j])   //find the minimal benifit
					{
						if(benefit[j]<min)
						{
							min=benefit[j];
							minj=j;
						}
					}
					cop1[j]=cop[j];  //backup
				}
				rs=benefit[ta]-t*apps[ta][4]*FRE;
				while(rs>min)  //probably replace
				{		
					if((use-apps[minj][4]+apps[ta][4])<area)  //satisfy area, replace
					{
						flag=0;
						cop[minj]=0;  //replace minj
						use=use-apps[minj][4]+apps[ta][4];
						cop[ta]=1;
						total=total+apps[ta][1]+t*apps[ta][4]*FRE;
						move++;
						break;
					}
					else //not satisfy are
					{
						flag=1;
						cop[minj]=0;
						use=use-apps[minj][4];
						rs-=min;  //update rs
						for(j=0,min=INF;j<TASKTYPE;j++)  //find the next small value
						{
							if(cop[j])
							{
								if(benefit[j]<min)
								{
									min=benefit[j];
									minj=j;
								}
							}
						}
					}	
				}
				if(flag)  //restore, do not replace
				{
					for(j=0;j<TASKTYPE;j++)
						cop[j]=cop1[j];
					use=use1;
					total=total+apps[ta][0];  //use normal config
				}
			}
		}		
	}
	move_time[3]=move;
	return total;
}

double simu_min()                      //assuming every task run with coprocessor, return total time. 
{
	int i;
	double total=0;
	for(i=0;i<TASKNO;i++)
		total+=apps[task[i]][1];
	return total;
}

double simu_optimal()                  //dynamic programmingi: optimal solution
{
	int s, s1, i, j, k, move = 0, k1;
	                               //construct the configuration matrix
	int start,end;
	double config[100][TASKTYPE+1];//cost
	int conf[100][TASKTYPE+1];     //which apps in this config 
	int ss=TASKTYPE;
	double cs;                     //current size
    	for(i=0;i<100;i++)             //init matrix
	{
		for(j=0;j<TASKTYPE+1;j++)
		{
			config[i][j]=-1;
			conf[i][j]=-1;
		}
	}
	double trans[100][100];
	int confno=1;                  //number of configuration number
	for(i=0;i<TASKTYPE;i++)        //base config
		config[0][i]=apps[i][0];
	config[0][ss]=0;
	for(i=0;i<TASKTYPE;i++)        //length 1
	{
		if(apps[i][4]<=area)
		{
			conf[confno][0]=i;
			conf[confno][ss]=apps[i][4];
			confno++;
		}
	}
	for(i=1,start=1,end=confno-1;i<TASKTYPE;i++)  //length
	{
		for(j=start;j<end;j++)
		{
			for(k=conf[j][i-1]+1;k<TASKTYPE;k++)
			{
				cs=conf[j][ss]+apps[k][4];
				if(cs<=area)   //are constrain
				{
					for(k1=0;k1<i;k1++)
						conf[confno][k1]=conf[j][k1];
					conf[confno][i]=k;
					conf[confno][ss]=cs;
					confno++;
				}
			}				
		}
		start=end+1;           //new start and end
		end=confno-1;
	}
  
	                               //construct the cost matrix and trans matrix
	for(i=0;i<confno;i++)          //cost matrix
	{
		for(j=0;j<TASKTYPE;j++)
		{
			for(k=0;k<TASKTYPE;k++)
			{
				if(j==conf[i][k])
				{
					config[i][j]=apps[j][1];  //in the conf
					break;
				}
				config[i][j]=apps[j][0]; // not in the conf
			}
			config[i][ss]=conf[i][ss];
		}
	}
	double tcost;                  //transfer cost
	for(i=0;i<confno;i++)          //trans matrix
	{
		for(j=0;j<confno;j++)
		{
			tcost=0;
			k=0;
			while(conf[j][k]!=-1 && k<TASKTYPE)
			{
				tcost=tcost+t*apps[conf[j][k]][4]*FRE;
				k1=0;
				while(conf[i][k1]!=-1 && k1<TASKTYPE)
				{
					if(conf[i][k1]==conf[j][k])
					{
						tcost=tcost-t*apps[conf[j][k]][4]*FRE;
						break;
					}
					k1++;
				}
				k++;
			}
			trans[i][j]=tcost;
		}
	}

	int trace[TASKNO][100];
	double min,min1;
	double least[100];
	double current[100];
	double total = 0; 
	double cost = 0;
   	for(i = 0; i < confno; i++)    //initialize
	{
		least[i] = 0;
		current[i] = 0;
	}
   	srand(time(NULL));
	s = rand() % confno;           //initial state
	for(i = 0; i < TASKNO; i++)
	{
		min1 = INF;  //min j
		for(j = 0; j < confno; j++)
		{
           		min = INF;     //min current[j]
			for(k = 0; k < confno; k++)
			{
				if(k != j)   //transfer
					cost = least[k] + config[j][task[i]] + trans[k][j];
				else
					cost = least[k] + config[j][task[i]];
				if(min > cost)
				{
					current[j] = cost;
                    			min = cost;
					trace[i][j] = k;
				}			
			}
			if(min1 > current[j])
			{
				min1 = current[j];
				s1 = j;
			}
		}
		for(j = 0; j < confno; j++)    //update table
			least[j] = current[j];
	}
	// trace back
	k1 = s1;
	for(i = TASKNO - 1; i > 0; i--)
	{
		j = trace[i][k1];
		if(j != k1)
		{
			move++;
			k1 = j;
		}
	}
	move_time[0]=move;
	return current[s1]; 
}

double simu_workfunction()             //workfunction algorithm
{
	int s, s1, i, j, k, move = 0, k1;
	//construct the configuration matrix
	int start,end;
	double config[100][TASKTYPE+1];  //cost
	int conf[100][TASKTYPE+1];       //which apps in this config 
	int ss=TASKTYPE;
	double cs;                     //current size
   	for(i=0;i<100;i++)             //init matrix
	{
		for(j=0;j<TASKTYPE+1;j++)
		{
			config[i][j]=-1;
			conf[i][j]=-1;
		}
	}
	double trans[100][100];
	int confno=1;                  //number of configuration number
	for(i=0;i<TASKTYPE;i++)        //base config
		config[0][i]=apps[i][0];
	config[0][ss]=0;
	for(i=0;i<TASKTYPE;i++)        //length 1
	{
		if(apps[i][4]<=area)
		{
			conf[confno][0]=i;
			conf[confno][ss]=apps[i][4];
			confno++;
		}
	}
	for(i=1,start=1,end=confno-1;i<TASKTYPE;i++)  //length
	{
		for(j=start;j<end;j++)
		{
			for(k=conf[j][i-1]+1;k<TASKTYPE;k++)
			{
				cs=conf[j][ss]+apps[k][4];
				if(cs<=area)   //are constrain
				{
					for(k1=0;k1<i;k1++)
						conf[confno][k1]=conf[j][k1];
					conf[confno][i]=k;
					conf[confno][ss]=cs;
					confno++;
				}
			}				
		}
		start=end+1;  //new start and end
		end=confno-1;
	}
  
	//construct the cost matrix and trans matrix
	for(i=0;i<confno;i++)  //cost matrix
	{
		for(j=0;j<TASKTYPE;j++)
		{
			for(k=0;k<TASKTYPE;k++)
			{
				if(j==conf[i][k])
				{
					config[i][j]=apps[j][1];  //in the conf
					break;
				}
				config[i][j]=apps[j][0]; // not in the conf
			}
			config[i][ss]=conf[i][ss];
		}
	}
	double tcost;                  //transfer cost
	for(i=0;i<confno;i++)          //trans matrix
	{
		for(j=0;j<confno;j++)
		{
			tcost=0;
			k=0;
			while(conf[j][k]!=-1 && k<TASKTYPE)
			{
				tcost=tcost+t*apps[conf[j][k]][4]*FRE;
				k1=0;
				while(conf[i][k1]!=-1 && k1<TASKTYPE)
				{
					if(conf[i][k1]==conf[j][k])
					{
						tcost=tcost-t*apps[conf[j][k]][4]*FRE;
						break;
					}
					k1++;
				}
				k++;
			}
			trans[i][j]=tcost;
		}
	}

	double min,min1;
	double least[100];
	double current[100];
	double total = 0; 
	double cost = 0;
  	for(i = 0; i < confno; i++)    //initialize
	{
		least[i] = 0;
		current[i] = 0;
	}
    	srand(time(NULL));
	s = rand() % confno;           //initial state
	for(i = 0; i < TASKNO; i++)
	{
		min1 = INF;            //min j
		for(j = 0; j < confno; j++)
		{
            		min = INF;     //min current[j]
			for(k = 0; k < confno; k++)
			{
				if(k != j)   //transfer
					cost = least[k] + config[j][task[i]] + trans[k][j];
				else
					cost = least[k] + config[j][task[i]];
				if(min > cost)
				{
					current[j] = cost;
                    			min = cost;
				}			
			}
			if(min1 > current[j])
			{
				min1 = current[j];
				s1 = j;
			}
		}
		for(j = 0; j < confno; j++)    //update table
			least[j] = current[j];
	                               // make online decision
		if(s1!=s)
		{
			total=total+config[s1][task[i]]+trans[s][s1];
			s=s1;
			move++;
		}
		else
			total=total+config[s1][task[i]];
	}
	move_time[2]=move;
	return total;
}

double simu_wrecent(int kk)            //algorithm recent kk tasks
{
	int s, s1, i, j, k, move = 0, k1;
	//construct the configuration matrix
	int start,end;
	double config[100][TASKTYPE+1];  //cost
	int conf[100][TASKTYPE+1];       //which apps in this config 
	int ss=TASKTYPE;
	double cs;                     //current size
    	for(i=0;i<100;i++)             //init matrix
	{
		for(j=0;j<TASKTYPE+1;j++)
		{
			config[i][j]=-1;
			conf[i][j]=-1;
		}
	}
	double trans[100][100];
	int confno=1;                  //number of configuration number
	for(i=0;i<TASKTYPE;i++)        //base config
		config[0][i]=apps[i][0];
	config[0][ss]=0;
	for(i=0;i<TASKTYPE;i++)        //length 1
	{
		if(apps[i][4]<=area)
		{
			conf[confno][0]=i;
			conf[confno][ss]=apps[i][4];
			confno++;
		}
	}
	for(i=1,start=1,end=confno-1;i<TASKTYPE;i++)  //length
	{
		for(j=start;j<end;j++)
		{
			for(k=conf[j][i-1]+1;k<TASKTYPE;k++)
			{
				cs=conf[j][ss]+apps[k][4];
				if(cs<=area)   //are constrain
				{
					for(k1=0;k1<i;k1++)
						conf[confno][k1]=conf[j][k1];
					conf[confno][i]=k;
					conf[confno][ss]=cs;
					confno++;
				}
			}				
		}
		start=end+1;           //new start and end
		end=confno-1;
	}
  
	//construct the cost matrix and trans matrix
	for(i=0;i<confno;i++)          //cost matrix
	{
		for(j=0;j<TASKTYPE;j++)
		{
			for(k=0;k<TASKTYPE;k++)
			{
				if(j==conf[i][k])
				{
					config[i][j]=apps[j][1];  //in the conf
					break;
				}
				config[i][j]=apps[j][0]; // not in the conf
			}
			config[i][ss]=conf[i][ss];
		}
	}
	double tcost;                  //transfer cost
	for(i=0;i<confno;i++)          //trans matrix
	{
		for(j=0;j<confno;j++)
		{
			tcost=0;
			k=0;
			while(conf[j][k]!=-1 && k<TASKTYPE)
			{
				tcost=tcost+t*apps[conf[j][k]][4]*FRE;
				k1=0;
				while(conf[i][k1]!=-1 && k1<TASKTYPE)
				{
					if(conf[i][k1]==conf[j][k])
					{
						tcost=tcost-t*apps[conf[j][k]][4]*FRE;
						break;
					}
					k1++;
				}
				k++;
			}
			trans[i][j]=tcost;
		}
	}

	double sum = 0, a, b;
	double total = 0;
	double cost; 
	double min;
    	double temp;
	int c=0,m;
	int cc;
	for(i=0,cc=0;i<TASKTYPE;i++)
	{
		cc+=apps[i][4];
	}
	cc=cc/TASKTYPE;
	double tc=t*cc*FRE;
	s = rand() % confno;
	for(i = 0; i < confno; i++)
	{
		for(j = 0; j < TASKTYPE; j++)
		{
			if(config[i][j] > tc)
				c++;
		}
	}
    	b = confno * TASKTYPE;
	a = (double)c / b;
	for(i = 0; i < TASKNO; i++)
	{
		min = INF;
		for(j = 0; j < confno; j++)
		{	
			cost = 0;      // total cost for conf j at task[i-k+1 .. i]
			for(m = 0; m < k && i - m >= 0; m++)
			{
				cost = cost + (double)(config[j][task[i - m]]) * pow((1.0 - a),m);
			}
			if(s != j)
				cost += trans[s][j]; 
			if(min > cost)
			{
				min = cost;
				s1 = j;
			}
		}
		if( s != s1)
		{
			move++;
			total = total + config[s1][task[i]] + trans[s][s1];
			s = s1;
		}
		else
			total += config[s1][task[i]];
	}
	return total;
}

double simu_abenefit()                 //adjusted cumulative benefit algorithm: return total time
{
	int i,j,ta,minj,flag,move=0;
	double benefit[TASKTYPE];
	int cop[TASKTYPE];
	int cop1[TASKTYPE];
	double total=0,use=0,min,use1=0;
	double save,rs;
	double a,b;
	int cc;
	double tasktime=0;
	for(i=0,cc=0;i<TASKTYPE;i++)
	{
		cc+=apps[i][4];
		tasktime+=apps[i][0];
		tasktime+=apps[i][1];
	}
	cc=cc/TASKTYPE;
	tasktime=tasktime/TASKTYPE/FRE/2;
	double tc=t*area;
	for(i=0,b=0;i<TASKTYPE;i++)
	{
		benefit[i]=0;          //init counter
		cop[i]=0;
		cop1[i]=0;
		if(apps[i][0]<tc)
			b++;
		if(apps[i][1]<tc)
			b++; 
	}
	a=tc/(tasktime);
	if(a>1)
		a=1;
	for(i=0;i<TASKNO;i++)
	{
		ta=task[i];
		for(j=0;j<TASKTYPE;j++)
			benefit[j]=benefit[j]*a;  //fading

        	benefit[ta]=benefit[ta]+(apps[ta][0]-apps[ta][1]);  //current benefit

		if(cop[ta])            //if it is in the cop, just run
			total+=apps[ta][1]; 
		else                   //not in the cop
		{
			if((use+apps[ta][4])<area && benefit[ta]>t*apps[ta][4]*FRE)  //can put in, put it in
			{
				use+=apps[ta][4];
				cop[ta]=1;
				total=total+apps[ta][1]+t*apps[ta][4]*FRE;
				move++;
			}
			else           //can not put it in, see change or not
			{
				flag=1;
				min=INF;
				use1=use;  //backup
				for(j=0;j<TASKTYPE;j++)
				{
					if(cop[j])   //find the minimal benifit
					{
						if(benefit[j]<min)
						{
							min=benefit[j];
							minj=j;
						}
					}
					cop1[j]=cop[j];  //backup
				}
				rs=benefit[ta]-t*apps[ta][4]*FRE;
			   	rs = benefit[ta];  //change benifit
				while(rs>min)  //probably replace
				{		
					if((use-apps[minj][4]+apps[ta][4])<area)  //satisfy area, replace
					{
						flag=0;
						cop[minj]=0;  //replace minj
						use=use-apps[minj][4]+apps[ta][4];
						cop[ta]=1;
						total=total+apps[ta][1]+t*apps[ta][4]*FRE;
						move++;
						break;
					}
					else //not satisfy are
					{
						flag=1;
						cop[minj]=0;
						use=use-apps[minj][4];
						rs-=min;  //update rs
						for(j=0,min=INF;j<TASKTYPE;j++)  //find the next small value
						{
							if(cop[j])
							{
								if(benefit[j]<min)
								{
									min=benefit[j];
									minj=j;
								}
							}
						}
					}	
				}
				if(flag)  //restore, do not replace
				{
					for(j=0;j<TASKTYPE;j++)
						cop[j]=cop1[j];
					use=use1;
					total=total+apps[ta][0];  //use normal config
				}
			}
		}		
	}
	move_time[1]=move;
	return total;
}

int main()
{
	srand(time(NULL));
	int i;
	double j1=0,j2=0,j3=0,j4=0,j5=0,j6=0,j7=0,j8=0,j9=0,j10=0,j11=0;
	double s1=0,s2=0,s3=0,s4=0,s5=0,s6=0,s7=0,s8=0,s9=0;
       	long a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12;
	for(i=0;i<SNO;i++)
	{
		randomtask();
		biastask(0.2, 0.8);
         	periodtask(15);
		a1=clock();
		j1 += simu_greedy();
		a2=clock();
		j2 += simu_benefit();
		a3=clock();
		j3 += simu_min();
		a4=clock();
		j4 += simu_optimal();
		a5=clock();
		a6=clock();
		j6 += simu_wrecent(100);
		a7=clock();
		j7 += simu_abenefit();
		a8=clock();
		j8 += simu_workfunction();
		a9 =clock();
	}
	j1=j1/SNO/FRE;
	j2=j2/SNO/FRE;
	j3=j3/SNO/FRE;
	j4=j4/SNO/FRE;
	j6=j6/SNO/FRE;
	j7=j7/SNO/FRE;
	j8=j8/SNO/FRE;
	j9=j9/SNO/FRE;    
        printf("algorithm\tperformance(ms)\ttime(us)\n");
        printf("greedy: \t %f\t%ld\n",j1,(a2-a1));
        printf("benefit:\t %f\t%ld\n",j2,(a3-a2));
	printf("AWW:\t\t %f\t%ld\n",j6,(a7-a6));   
        printf("Abenefit:\t %f\t%ld\n",j7,(a8-a7));
	printf("optimal:\t %f\t%ld\n",j4,(a5-a4)); 
	printf("workfunction:\t %f\t%ld\n",j8,(a9-a8));
	printf("Min:\t\t %f\t%ld\n", j3, (a4-a3));
	printf("have a nice day!\n");
	return 1;
}