/*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, D. Sheldon, and F. Vahid.  Dynamic Tuning of Configurable Architectures: The AWW Online Algorithm. 
IEEE/ACM Int. Conf. on Hardware/Software Codesign and System Synthesis, (CODES/ISSS), Oct 2008. */

/* Simulator for AWW online algorithm
   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 10000000000000.0
#define TASKNO 5000                    //The number of task queue
#define CONFTYPE 40                    //The number of configuration type 
#define TASKTYPE 15                    //The number of task type

int task[TASKNO];
double config[CONFTYPE][TASKTYPE] =                            //Microblaze data set                   
{{135487961,    12696265,	17223565,	13204747,	66496392,	28930964,	43184,	47258348,	3991413,	12752273,	10183815,	277266743,	57740348,	1112286,	182860906},
{ 135487961,	12696265,	17223565,	13204747,	66496392,	27429200,	43184,	47258348,	3991413,	12555923,	10107013,	277266743,	57740348,	1112286,	182860906},
{ 135487961,	12696265,	17223565,	13204747,	66496392,	28930964,	43184,	47258348,	3991413,	12752273,	10183815,	277266743,	57740348,	1112286,	182860906},
{ 135487961,	12696265,	17223565,	13204747,	66496392,	27429200,	43184,	47258348,	3991413,	12555923,	10107013,	277266743,	57740348,	1112286,	182860906},
{ 135487961,	12696265,	17223565,	13204747,	66496392,	28930964,	43184,	47258348,	1684679,	12752273,	10183815,	277266743,	57740348,	1112286,	99344896},
{ 135487961,	12696265,	17223565,	13204747,	66496392,	27429200,	43184,	47258348,	1684679,	12555923,	10107013,	277266743,	57740348,	1112286,	99344896},
{ 135487961,	12696265,	17223565,	13204747,	66496392,	28930964,	43184,	47258348,	1684679,	12752273,	10183815,	277266743,	57740348,	1112286,	99344896},
{ 135487961,	12696265,	17223565,	13204747,	66496392,	27429200,	43184,	47258348,	1684679,	12555923,	10107013,	277266743,	57740348,	1112286,	99344896},
{ 82099649,	9905565,	8676124,	8585183,	29184392,	26539468,	37421,	16214848,	3942637,	12620108,	6242071,	266757343,	64135348,	620836,	177347116},
{ 82099649,	9905565,	8676124,	8585183,	29184392,	26487280,	37421,	16214848,	3942637,	12550478,	6234437,	266757343,	64135348,	620836,	177347116},
{ 82099649,	9905565,	8676124,	8585183,	29184392,	26539468,	37421,	16214848,	3942637,	12620108,	6242071,	266757343,	64135348,	620836,	177347116},
{82099649,	9905565,	8676124,	8585183,	29184392,	26487280,	37421,	16214848,	3942637,	12550478,	6234437,	266757343,	64135348,	620836,	177347116},
{82099649,	9905565,	8676124,	8585183,	29184392,	26539468,	37421,	16214848,	1635903,	12620108,	6242071,	266757343,	64135348,	620836,	94045816},
{82099649,	9905565,	8676124,	8585183,	29184392,	26487280,	37421,	16214848,	1635903,	12550478,	6234437,	266757343,	64135348,	620836,	94045816},
{82099649,	9905565,	8676124,	8585183,	29184392,	26539468,	37421,	16214848,	1635903,	12620108,	6242071,	266757343,	64135348,	620836,	94045816},
{82099649,	9905565,	8676124,	8585183,	29184392,	26487280,	37421,	16214848,	1635903,	12550478,	6234437,	266757343,	64135348,	620836,	94045816},
{ 96798326,	10818171,	16618525,	12904727,	48192392,	28021924,	39442,	42194098,	3161039,	12746828,	9255326,	91325279,	23821348,	970569,	150467731},
{ 96798326,	10818171,	16618525,	12904727,	48192392,	26520160,	39442,	42194098,	3161039,	12550478,	9171803,	91325279,	23821348,	970569,	150467731},
{ 96798326,	10818171,	16618525,	12904727,	48192392,	28021924,	39442,	42194098,	3161039,	12746828,	9255326,	91325279,	23821348,	970569,	150467731},
{ 96798326,	10818171,	16618525,	12904727,	48192392,	26520160,	39442,	42194098,	3161039,	12550478,	9171803,	91325279,	23821348,	970569,	150467731},
{ 96798326,	10818171,	16618525,	12904727,	48192392,	28021924,	39442,	42194098,	793335,	12746828,	9255326,	91325279,	23821348,	970569,	65545696},
{ 96798326,	10818171,	16618525,	12904727,	48192392,	26520160,	39442,	42194098,	793335,	12550478,	9171803,	91325279,	23821348,	970569,	65545696},
{ 96798326,	10818171,	16618525,	12904727,	48192392,	28021924,	39442,	42194098,	793335,	12746828,	9255326,	91325279,	23821348,	970569,	65545696},
{ 96798326,	10818171,	16618525,	12904727,	48192392,	26520160,	39442,	42194098,	793335,	12550478,	9171803,	91325279,	23821348,	970569,	65545696},
{49958882,	8046171,	8499496,	8543303,	29184392,	26539468,	37421,	16214848,	3154071,	12620108,	5436233,	86564879,	23821348,	544509,	150292651},
{49958882,	8046171,	8499496,	8543303,	29184392,	26487280,	37421,	16214848,	3154071,	12550478,	5428599,	86564879,	23821348,	544509,	150292651},
{49958882,	8046171,	8499496,	8543303,	29184392,	26539468,	37421,	16214848,	3154071,	12620108,	5436233,	86564879,	23821348,	544509,	150292651},
{49958882,	8046171,	8499496,	8543303,	29184392,	26487280,	37421,	16214848,	3154071,	12550478,	5428599,	86564879,	23821348,	544509,	150292651},
{49958882,	8046171,	8499496,	8543303,    29184392,	26539468,	37421,	16214848,	786367,	12620108,	5436233,	86564879,	23821348,	544509,	65370616},
{49958882,	8046171,	8499496,	8543303,	29184392,	26487280,	37421,	16214848,	786367,	12550478,	5428599,	86564879,	23821348,	544509,	65370616},
{49958882,	8046171,	8499496,	8543303,	29184392,	26539468,	37421,	16214848,	786367,	12620108,	5436233,	86564879,	23821348,	544509,	65370616},
{49958882,	8046171,    8499496,	8543303,	29184392,	26487280,	37421,	16214848,	786367,	12550478,	5428599,	86564879,	23821348,	544509,	65370616},
{ 23421349,	12696265,	1003873,	13204747,	66496392,	28930964,	43184,	47258348,	3991413,	12752273,	10249738,	277266743,	57740348,	1005097,	182860906},
{ 23421349,	12696265,	1003873,	13204747,	66496392,	27429200,	43184,	47258348,	3991413,	12555923,	10172936,	277266743,	57740348,	1005097,	182860906},
{ 23421349,	12696265,	1003873,	13204747,	66496392,	28930964,	43184,	47258348,	3991413,	12752273,	10249738,	277266743,	57740348,	1005097,	182860906},
{ 23421349,	12696265,	1003873,	13204747,	66496392,	27429200,	43184,	47258348,	3991413,	12555923,	10172936,	277266743,	57740348,	1005097,	182860906},
{ 23421349,	12696265,	1003873,	13204747,	66496392,	28930964,	43184,	47258348,	1684679,	12752273,	10249738,	277266743,	57740348,	1005097,	99344896},
{ 23421349,	12696265,	1003873,	13204747,	66496392,	27429200,	43184,	47258348,	1684679,	12555923,	10172936,	277266743,	57740348,	1005097,	99344896},
{ 23421349,	12696265,	1003873,	13204747,	66496392,	28930964,	43184,	47258348,	1684679,	12752273,	10249738,	277266743,	57740348,	1005097,	99344896},
{ 23421349,	12696265,	1003873,	13204747,	66496392,	27429200,	43184,	47258348,	1684679,	12555923,	10172936,	277266743,	57740348,	1005097,	99344896}
};

double t = 100000000 * 0.2;            //transfer overhead

//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
{
	int i, j, s, s1, move = 0;
	double total = 0;
	s = rand() % CONFTYPE;
	int sel[TASKTYPE];
	double min;
	for(i = 0; i < TASKTYPE; i++)
	{
		min = INF;
		for(j = 0; j < CONFTYPE; j++)
		{
			if(min > config[j][i])
			{	
				min = config[j][i];
				sel[i] = j;
			}
		}
	}

	for(i = 0; i < TASKNO; i++)
	{
	        s1 = sel[task[i]];
		if(s != s1)
		{
			move ++;
			total = total + config[s1][task[i]] + t;
			s = s1;
		}
		else
			total = total + config[s1][task[i]];
	}
	return total;
}

double simu_constant()                 //without reconfiguration
{
  double total=0;
  double min=INF;
  double cost;
  int mini,i,j;
  for(i=0;i<CONFTYPE;i++)  //find the best config
  {
    for(j=0,cost=0;j<TASKTYPE;j++)
    {
      cost+=config[i][j];
    }
    if(cost<min)
    {
      min=cost;
      mini=i;
    }
  }
  for(i=0;i<TASKNO;i++)
    total+=config[mini][task[i]];
  total+=t;
  return total;  
}

double simu_window(int k)              //windows algorithm with window size k 
{
	int i, j, s, s1 = 0, move = 0;
	double total = 0;
	double cost[CONFTYPE]; 
        for(i=0;i<CONFTYPE;i++)
          cost[i]=0;
	double min;
        double temp;
	s = rand() % CONFTYPE;
	for(i = 0; i < TASKNO; i++)
	{
		min = INF;
		for(j = 0; j < CONFTYPE; j++)
		{
                        if(k-i>0)
                          cost[j]=cost[j]+config[j][task[i]];
                        else
                          cost[j]=cost[j]-config[j][task[i-k]]+config[j][task[i]];  
		
                        
			if(s != j)
			  temp = cost[j]+t;
            		else 
              		  temp = cost[j];
			if(min > temp)
			{
				min = temp;
				s1 = j;
			}
		}
		if( s != s1)
		{
			move++;
			total = total + config[s1][task[i]] + t;
			s = s1;
		}
		else
			total += config[s1][task[i]];
	}
	return total;
}

double simu_window1(int k)             //windows1 algorithm with window size k
{
	int i, j, m, s, s1 = 0, move = 0;
	double total = 0;
	double cost; 
	double min;
	s = rand() % CONFTYPE;
	for(i = 0; i < TASKNO; i++)
	{
		min = INF;
		for(j = 0; j < CONFTYPE; 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 + config[j][task[i - m]];
			}
			if(s != j)
				cost = cost + t/5;
			if(min > cost)
			{
				min = cost;
				s1 = j;
			}
		}
		if( s != s1)
		{
			move++;
			total = total + config[s1][task[i]] + t;
			s = s1;
		}
		else
			total += config[s1][task[i]];
	}
	return total;
}

double simu_aww(int k)             //weight windows algorithm with window size k
{
	int i, j, s, s1 = 0, move = 0, c = 0;
	double sum = 0, a, b;
	double total = 0;
	double cost[CONFTYPE]; 
	double min;
        double temp;
	s = rand() % CONFTYPE;
	for(i = 0; i < CONFTYPE; i++)
	{
		for(j = 0; j < TASKTYPE; j++)
		{
			if(config[i][j] > t)
				c++;
		}
		cost[i]=0;
	}
    	b = CONFTYPE * TASKTYPE;
	a = (double)c / b;
	double p=pow((1-a),k-1);
	for(i = 0; i < TASKNO; i++)
	{
		min = INF;
		for(j = 0; j < CONFTYPE; j++)
		{	
			if(i<k)
				cost[j]=cost[j]*(1-a)+config[j][task[i]];
			else
				cost[j]=(cost[j]-config[j][task[i-k]]*p)*(1-a)+config[j][task[i]];
            		if(s!=j)
                		temp=cost[j]+t;
            		else 
                		temp=cost[j];
			if(min > temp)
			{
				min = temp;
				s1 = j;
			}
		}
		if( s != s1)
		{
			move++;
			total = total + config[s1][task[i]] + t;
			s = s1;
		}
		else
			total += config[s1][task[i]];
	}
	return total;
}

double simu_tww(int a)             //two way window algorithm
{
	int s, s1, i, j, k, ct, move = 0, max;
	int count[TASKTYPE][TASKTYPE];
	int pre[TASKNO];
	double cost, min, total = 0;
	s = rand() % CONFTYPE;         //initial state
	for(i = 0; i < TASKTYPE; i++)
	{
		for(j = 0; j < TASKTYPE; j++)
		{
			count[i][j] = 0;
		}
	}
	for(i = 0; i < TASKNO; i++)    //main loop
	{
		if(i != 0)
			count[task[i - 1]][task[i]] += 1;  //update count table
		pre[0] = task[i];
		for(j = 1; j < a; j++) //predict sequence
		{
			ct = pre[j - 1];
			for(k = 0, max = -1; k < TASKTYPE; k++)
			{
				if(count[ct][k] > max)
				{
					max = count[ct][k];
					pre[j] = k;
				}
			}
		}
         
		for(j = 0, min =INF; j < CONFTYPE; j++)  //choose a min cost state
		{
			cost = 0;
			for(k = 0; k < a && (i-k-1)>=0; k++)  //back
			{
				cost += config[j][task[i - k - 1]];
			}
			for(k = 0; k < a; k++)  //advance
			{
				cost += config[j][pre[k]];
			}
			if(s != j)
				cost += t;
			if(cost < min)
			{
				min = cost;
				s1 = j;
			}
		}

		if( s != s1)
		{
			move++;
			total = total + config[s1][task[i]] + t;
			s = s1;
		}
		else
			total += config[s1][task[i]];
	}
	return total;
}

double simu_optimal()                  //dynamic programming
{
	int s, s1, i, j, k, move = 0, k1;
	int trace[TASKNO][CONFTYPE];
	double min,min1;
	double least[CONFTYPE];
	double current[CONFTYPE];
	double total = 0; 
	double cost = 0;
  	for(i = 0; i < CONFTYPE; i++)  //initialize
	{
		least[i] = 0;
		current[i] = 0;
	}
        srand(time(NULL));
	s = rand() % CONFTYPE;         //initial state
	for(i = 0; i < TASKNO; i++)
	{
		min1 = INF;            //min j
		for(j = 0; j < CONFTYPE; j++)
		{
           		min = INF;     //min current[j]
			for(k = 0; k < CONFTYPE; k++)
			{
				if(k != j)   //transfer
					cost = least[k] + config[j][task[i]] + t;
				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 < CONFTYPE; 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;
		}
	}
	return current[s1];
}

double simu_marking(double a)
{
	int s, s1, i, j, k;
	double r = a;
	int move = 0;
	double total = 0;
	double counter[CONFTYPE];
	for(j = 0; j < CONFTYPE; j++)  //init
	{
		counter[j] = 0;
	}
	s = rand() % CONFTYPE;
	s1 = s;
	for(i = 0; i < TASKNO; i++)
	{
		for(j = 0, k = 0; j < CONFTYPE; j++)  //update counter
		{
			counter[j] += config[j][task[i]];
			if(counter[j] >= r)
				k++;
		}
		if(counter[s] >= r)    //select a new state
		{
			if(k == CONFTYPE)
			{
				for(j = 0; j < CONFTYPE; j++)  //new phase
				{
					counter[j] = 0;
				}
				s1 = rand() % CONFTYPE;
			}
			else
			{
				s1 = rand() % CONFTYPE;  //random a new phase
				while(counter[s1] > r)
					s1 = rand() % CONFTYPE;
			}
		}
		if(s != s1)
		{
			move++;
			total = total + config[s1][task[i]] + t;
			s = s1;
		}
		else
			total = total + config[s1][task[i]];
	}
	return total;
}

double simu_oddexponent()
{
	int s, s1, i, j, k, move = 0;
	double least[CONFTYPE];
	double current[CONFTYPE];
	double L[CONFTYPE];
	double p[CONFTYPE];
	double temp, sum, max;
	double min, min1;
	double total = 0; 
	double cost = 0;
    	for(i = 0; i < CONFTYPE; i++)  //initialize
	{
		least[i] = 0;
		current[i] = 0;
	}
	s = rand() % CONFTYPE;         //initial state
	for(i = 0; i < TASKNO; i++)
	{
		min1 = INF;            //min j
		for(j = 0; j < CONFTYPE; j++)
		{
           		min = INF;     //min current[j]
			for(k = 0; k < CONFTYPE; k++)
			{
				if(k != j)   //transfer
					cost = least[k] + config[j][task[i]] + t;
				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, sum = 0; j < CONFTYPE; j++)    //update table
		{
			least[j] = current[j];
			sum += least[j];
		}
		//above calculate loss of expert, below make online decision
		for(j = 0; j < CONFTYPE; j++)
		{
			L[j] = (double)least[j] / sum;
		}
		for(j = 0, temp = 0; j < CONFTYPE; j++)  //get probability of each one
		{
			for(k = 0, sum = 0; k < CONFTYPE; k++)
				sum = sum + (L[k] - L[j]) * (L[k] - L[j]) * (L[k] - L[j]);
			p[j] = 1.0 / (double)CONFTYPE + 1.0 / (double)CONFTYPE * sum;
			temp += p[j];
		}
		for(j = 0; j < CONFTYPE; j++)
		{
			p[j] = p[j] / temp;
		}
		//make choice

	        for(j = 0, max = 0; j < CONFTYPE ; j++)
		{
			if(max < p[j])
			{
				max = p[j];
				s1 = j;
			}
		}
		if(s != s1)
		{
			move++;
			total = total + config[s1][task[i]] + t;
			s = s1;
		}
		else
			total = total + config[s1][task[i]];
	}
	return total;
}

double simu_workfunction()
{
	int s, s1, i, j, k, move = 0;
   	double min, min1;
	double least[CONFTYPE];
	double current[CONFTYPE];
	double total = 0;
	double cost = 0;
    	for(i = 0; i < CONFTYPE; i++)   //initialize
	{
		least[i] = 0;
		current[i] = 0;
	}
	s = rand() % CONFTYPE;  //initial state
	for(i = 0; i < TASKNO; i++)
	{
		min1 = INF;  //min j
		for(j = 0; j < CONFTYPE; j++)
		{
            		min = INF;  //min current[j]
			for(k = 0; k < CONFTYPE; k++)
			{
				if(k != j)   //transfer
					cost = least[k] + config[j][task[i]] + t;
				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 < CONFTYPE; j++)    //update table
			least[j] = current[j];
		//above calculate loss of expert, below make online decision
        	for(j = 0, min = INF; j < CONFTYPE ; j++)
		{
			if(min > current[j])
			{
				min = current[j];
				s1 = j;
			}
		}

		if(s != s1)
		{
			move++;
			total = total + config[s1][task[i]] + t;
			s = s1;
		}
		else
			total = total + config[s1][task[i]];
	}
	return total;
}

int main()
{
        srand(time(NULL));
	double j1=0,j2=0,j3=0,j4=0,j5=0,j6=0,j7=0,j8=0,j9=0,j10=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;
//	randomtask();
	biastask(0.2, 0.8);
//     	periodtask(15);
        a1=clock();
        j1 = simu_greedy();
        a2=clock();
        j2 = simu_window(100);
        a3=clock();
        j3 = simu_window(10);
        a4=clock();
        j4 = simu_marking(t*20);
        a5=clock();
        j5 = simu_window1(10);
        a6=clock();
        j6 = simu_workfunction();
        a7=clock();
        j7 = simu_aww(100);
        a8=clock();
        j8 = simu_tww(100);
        a9=clock();
        j9 = simu_optimal();
        a10=clock();
        j10 = simu_constant();
        a11=clock();
        printf("algorithm\tperformance\t\ttime(us)\n");
        printf("greedy: \t%f\t%ld\n",j1,(a2-a1));
        printf("window100:\t%f\t%ld\n",j2,(a3-a2));
        printf("window10:\t%f\t%ld\n",j3,(a4-a3));
        printf("marking:\t%f\t%ld\n",j4,(a5-a4));
        printf("workfuntion:\t%f\t%ld\n",j6,(a7-a6));
        printf("aww:\t\t%f\t%ld\n",j7,(a8-a7));
        printf("tww:\t\t%f\t%ld\n",j8,(a9-a8));
        printf("optimal:\t%f\t%ld\n",j9,(a10-a9));
        printf("constant:\t%f\t%ld\n",j10,(a11-a10));
        printf("have a nice day!\n");
        return 1;
}