/* Skeleton's heuristics for double objective functions */

/*--------------------------------------------------------
Created by Veronika Rehn - Veronika.Rehn@ens-lyon.fr
Using Skeleton's heuristics 
created by Anne Benoit - Anne.Benoit@ens-lyon.fr

Created: March 2007
----------------------------------------------------------
This is a template for skeleton mapping. 
The application and platform parameters must
be directly coded in this file.
-----------------------------------------------------------*/

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

#define DEBUG 1
#define MEGADEBUG 0
#define MAXINT 1000000
#define STARTDIC 10
#define PREC 0.0001
#define MAXDOUBLE   1.7976931348623158e+308
#define INCREASE 20.0

int getBestPos(double pp[], int bestCut, double globalBest) {
  double best=MAXDOUBLE;
  int i;
  int bestPos=-1;
  for (i=bestCut*4;i<bestCut*4+3;i++)
    if ((pp[i+1]<best) && (pp[i+1]<globalBest)) {
      bestPos=i+1;
      best=pp[i+1];
    }
  return bestPos;
}

double getMaxP(double p1, double p2, double p3) {
  double max=-1;
  if (p1>max) max=p1;
  if (p2>max) max=p2;
  if (p3>max) max=p3;
  //printf("max out of (%f, %f, %f) = %f\n",p1,p2,p3,max);
  return max;
}


int main(int argc, char *argv[]) {

  int i,ii,j,jj,k,kk;  
  char fname[40];
  char per_fname[40];
  char lat_fname[40];
  int nbheur=6;
  
  //----- For the result plots ------//
  // FILE *plot[nbheur];

  //----- Generating the platforms and the applications -------//
  int nbapp=4; //50; stages
  int nbtree=50;//50;
  //  double fixp=3.80; //fixed period

  int tr=10; //testrange

  double fixedperiod[tr][nbapp];
  double fixedlatency[tr][nbapp];
   

   
//------- 5 stages -------------
  fixedperiod[0][0]=9.0;
  fixedperiod[1][0]=9.3;
  fixedperiod[2][0]=9.7;
  fixedperiod[3][0]=10.0;
  fixedperiod[4][0]=10.3;
  fixedperiod[5][0]=10.7;
  fixedperiod[6][0]=11.0;
 fixedperiod[7][0]=11.3;
 fixedperiod[8][0]=11.7;
 fixedperiod[9][0]=12.0;
 fixedlatency[0][0]=9.0;
 fixedlatency[1][0]=9.7;
 fixedlatency[2][0]=10.3;
 fixedlatency[3][0]=11.0;
 fixedlatency[4][0]=11.7;
 fixedlatency[5][0]=12.3;
 fixedlatency[6][0]=13.0;
 fixedlatency[7][0]=13.7;
 fixedlatency[8][0]=14.3;
 fixedlatency[9][0]=20.0;
 
 //------- 10 stages ---------------
  fixedperiod[0][1]=10;
  fixedperiod[1][1]=11;
  fixedperiod[2][1]=12;
  fixedperiod[3][1]=13;
  fixedperiod[4][1]=14;
  fixedperiod[5][1]=15;
  fixedperiod[6][1]=16;
  fixedperiod[7][1]=17;
  fixedperiod[8][1]=18;
  fixedperiod[9][1]=29;
 fixedlatency[0][1]=13.0;
 fixedlatency[1][1]=15.0;
 fixedlatency[2][1]=17.0;
 fixedlatency[3][1]=19.0;
 fixedlatency[4][1]=21.0;
 fixedlatency[5][1]=23.0;
 fixedlatency[6][1]=25.0;
 fixedlatency[7][1]=27.0;
 fixedlatency[8][1]=29.0;
 fixedlatency[9][1]=31.0;
 
 //------- 20 stages ---------------
 fixedperiod[0][2]=10.0;
 fixedperiod[1][2]=11.0;
 fixedperiod[2][2]=12.0;
 fixedperiod[3][2]=13.0;
 fixedperiod[4][2]=14.0;
 fixedperiod[5][2]=15.0;
 fixedperiod[6][2]=16.0;
 fixedperiod[7][2]=17.0;
 fixedperiod[8][2]=18.0;
 fixedperiod[9][2]=19.0;
 fixedlatency[0][2]=20.0;
 fixedlatency[1][2]=21.0;
 fixedlatency[2][2]=22.0;
 fixedlatency[3][2]=23.0;
 fixedlatency[4][2]=24.0;
 fixedlatency[5][2]=25.0;
 fixedlatency[6][2]=27.0;
 fixedlatency[7][2]=29.0;
 fixedlatency[8][2]=32.0;
 fixedlatency[9][2]=35.0;
 
//------- 40 stages ---------------
 fixedperiod[0][3]=15.0;
 fixedperiod[1][3]=16.0;
 fixedperiod[2][3]=17.0;
 fixedperiod[3][3]=18.0;
 fixedperiod[4][3]=19.0;
 fixedperiod[5][3]=20.0;
 fixedperiod[6][3]=21.0;
 fixedperiod[7][3]=22.0;
 fixedperiod[8][3]=23.0;
 fixedperiod[9][3]=24.0;
 fixedlatency[0][3]=32.0;
 fixedlatency[1][3]=34.0;
 fixedlatency[2][3]=36.0;
 fixedlatency[3][3]=38.0;
 fixedlatency[4][3]=40.0;
 fixedlatency[5][3]=42.0;
 fixedlatency[6][3]=44.0;
 fixedlatency[7][3]=46.0;
 fixedlatency[8][3]=48.0;
 fixedlatency[9][3]=50.0;
 

  double fixp,fixl;

  int nbproc[nbapp], nbstage[nbapp], maxproc=0, maxstage=0;
  FILE *idf[nbapp];
  
  int tree;
  double totperiod[tr][nbheur][nbapp];
  double totlatency[tr][nbheur][nbapp];
  
  double latency[tr][nbheur][nbapp];
  
  int n,p,l,ll,nbint;
  int maxproc2;
  double maxperiod, maxp, max1, max2, maxs;
  double ss;

  int maxsta;
  double kkk, kkmax, kkmin;

  int heuristic;
  
  int z;

 
  //fprintf(stderr,"permier boucle; totperiod, totlatency etc initialized;\n");
  for (i=0; i<tr; i++)
    for (j=0; j<nbheur; j++) {
      for (k=0; k<nbapp; k++) {
	totperiod[i][j][k] = 0;
	totlatency[i][j][k] = 0;
	latency[i][j][k] = 0;
      }
    }
 
  // Looping over nbtree platforms for each kind of app, and average for the plots
  for (tree=0; tree<nbtree; tree++) {
    
 /*    // platform k */
/*     if(DEBUG) */
/*       for (k=0; k<nbapp; k++) { */
/* 	for (j=0;j<tr;j++) { */
/* 	  sprintf(fname,"applis/appli-%.2d-%.2d-%.2d.txt",k,tree,j); */
/* 	  idf[j][k] = fopen (fname,"w"); */
/* 	} */
    
    for (k=0; k<nbapp; k++) {
      nbproc[k]=10;//5;
      if (nbproc[k]>maxproc) maxproc=nbproc[k];
    }
    
    double B[nbapp], s[nbapp][maxproc];
    
      for (k=0; k<nbapp; k++)
        B[k]=10;
      for (j=0; j<maxproc; j++) {
        ss=random()%20 + 1;
        for (k=0; k<nbapp; k++)
          s[k][j]=ss;
      }

    /*   // appli k */
/*       for (k=0; k<nbapp; k++) { */
/*         nbstage[k]=k+1;//11; */
/*         if (nbstage[k]>maxstage) maxstage=nbstage[k]; */
/*       } */
    
    // appli k
     /*  nbstage[0]=10; */
/*       maxstage=nbstage[0]; */
      nbstage[0]=5;
      nbstage[1]=10;
      nbstage[2]=20;
      nbstage[3]=40;
      maxstage=nbstage[3];
  
    
    
 
    /*   // appli k */
    /*   for (k=0; k<nbapp; k++) { */
    /*     nbstage[k]=8; */
    /*     if (nbstage[k]>maxstage) maxstage=nbstage[k]; */
    /*   } */
    
    
    double w[nbapp][maxstage], d[nbapp][maxstage+1];
    
      for (k=0; k<nbapp; k++) {
        for (i=0; i<nbstage[k]; i++)
          w[k][i]=(random()%20 + 1);
        for (i=0; i<nbstage[k]+1; i++) {
          d[k][i]= random()%100 + 1; //10;
	  //d[k][i]=random()%20 + 1;
        }
        //d[k][0]=0.0001;
        //d[k][nbstage[k]+1]=0.0001;
      }
    
/*     for (k=0; k<nbapp; k++) { */
/*       w[k][0]=8; */
/*       w[k][1]=17; */
/*       w[k][2]=18; */
/*       w[k][3]=14; */
/*       w[k][4]=7; */
/*       w[k][5]=6; */
/*       w[k][6]=7; */
/*       w[k][7]=4; */
/*       w[k][8]=20; */
/*       w[k][9]=5; */
/*       w[k][10]=9; */
      
/*       d[k][0]= 12; */
/*       d[k][1]= 13; */
/*       d[k][2]= 10; */
/*       d[k][3]= 4; */
/*       d[k][4]= 20; */
/*       d[k][5]= 11; */
/*       d[k][6]= 9; */
/*       d[k][7]= 9; */
/*       d[k][8]= 16; */
/*       d[k][9]= 1; */
/*       d[k][10]=10; */
/*       d[k][11]=17; */
      
/*     } */
    
/*     // Printing platform parameters in the file */
/*       if (DEBUG) { */
/* 	for (k=0; k<nbapp; k++) { */
/* 	  for (z=0;z<tr;z++) { */
	    
/* 	    fprintf(idf[k], "*** Platform and application %d ***\nnbproc=%d, nbstage=%d\n", */
/* 		    k, nbproc[k], nbstage[k]); */
/* 	    fprintf(idf[k], "B=%f\n", B[k]); */
/* 	    for (j=0; j<nbproc[k]; j++) */
/* 	      fprintf(idf[k], "s[%d]= %f  ", j, s[k][j]); */
/* 	    fprintf(idf[k], "\n"); */
/* 	    for (i=0; i<nbstage[k]; i++) */
/* 	      fprintf(idf[k], "w[%d]= %f  ", i, w[k][i]); */
/* 	    fprintf(idf[k], "\n"); */
/* 	    for (i=0; i<nbstage[k]+1; i++) */
/* 	      fprintf(idf[k], "d[%d]= %f  ", i, d[k][i]); */
/* 	    fprintf(idf[k], "\n\n"); */
/* 	  } */
/* 	} */
/*       } */
    
    for (k=0; k<nbapp; k++) {
      printf("k=%d\n",k);
      n=nbstage[k]; p=nbproc[k];

      for (z=0;z<tr;z++) { // looping over the different fixed latencies and periodf
	if (DEBUG) {
	  sprintf(fname,"applis/appli-%.2d-%.2d-%.2d.txt",k,tree,z); 
	  idf[k] = fopen (fname,"w");  
	  fprintf(idf[k], "*** Platform and application %d ***\nnbproc=%d, nbstage=%d\n",
		  k, nbproc[k], nbstage[k]);
	  fprintf(idf[k], "B=%f\n", B[k]);
	  for (j=0; j<nbproc[k]; j++)
	    fprintf(idf[k], "s[%d]= %f  ", j, s[k][j]);
	  fprintf(idf[k], "\n");
	  for (i=0; i<nbstage[k]; i++)
	    fprintf(idf[k], "w[%d]= %f  ", i, w[k][i]);
	  fprintf(idf[k], "\n");
	  for (i=0; i<nbstage[k]+1; i++)
	    fprintf(idf[k], "d[%d]= %f  ", i, d[k][i]);
	  fprintf(idf[k], "\n\n");
	}

	fixp=fixedperiod[z][k];
	fixl=fixedlatency[z][k];
	
      
      fprintf(idf[k], "fixp=%f ,fixl=%f ", fixp,fixl);

      
      // Simple heuristics: 1 stage per proc, or l=[n/p] if n>p (nbstage>nbproc)
      l = n/p;
      if (n%p !=0) l++;
      
      nbint = n/l;
      if (n%l !=0) nbint++;
      
      if (DEBUG) fprintf(idf[k],"l=%d, nbint=%d\n", l, nbint);
      
      int usedproc[p];
      
      printf("hello appli=%d platform=%d\n",k,tree);
      
      
      //************ part I: min latence with fixed period  *************************
      
      // *********** Heuristic 1: Splitting bicritaire to diminuate ************
      // ***********              period until period is reached    ************
      // *********** uses Splitting heuristic by Anne Benoit        ************
      heuristic=0;
      int start[p], end[p];
      double per[p], pp[24];
      for(j=0; j<p; j++) {
	usedproc[j]=0;
	per[j]=-1;
      }
      maxperiod=-1; kk=1;
      
      if (MEGADEBUG) {   
	printf("\nPLATFORM:\n");
	printf("nb stages: %d,n=%d, nb procs: %d, p=%d\n",nbstage[k],n,nbproc[k],p);
	printf("links:");
	for(j=0;j<n+1;j++)
	  printf("\t%lf",d[k][j]);
	
	printf("\nstage time n=%d:",n);
	for(j=0;j<n;j++)
	  printf("\t%lf",w[k][j]);
	
	printf("\nproc speed:");
	for(j=0;j<p;j++)
	  printf("\t%lf",s[k][j]);
	printf("\n");
      }
      
      
      while (kk) {
	// find fastest proc
	maxproc=-1; maxs=-1;
	
	for (j=0; j<p; j++)
	  if ((s[k][j]>maxs)&&(usedproc[j]==0)) {
	    maxproc=j; maxs=s[k][j];
	  }
	if (DEBUG) printf("fastest proc: %d, speed %f\n", maxproc, maxs);
	
	if (maxperiod==-1) {
	  // First time in the loop: start[p]=0 and end[p]=n-1;
	  start[maxproc]=0; end[maxproc]=n-1; usedproc[maxproc]=1;
	  // compute the corresponding period
	  per[maxproc] = (d[k][0]+d[k][n])/B[k];
	  for (i=0; i<n; i++) per[maxproc] += w[k][i]/maxs;
	  maxperiod=0;
	  //latence corresponds to the period of the fastest proc as it is the only chosen proc
	  latency[z][heuristic][k]=per[maxproc];
	  if (DEBUG) printf("init: all on fastest proc: %d, p=%f, l=%f\n",maxproc,per[maxproc], latency[z][heuristic][k]);
	  //for (i=0;i<6;i++) lat[i]=per[maxproc];
	}
	else if (maxproc!=-1) {
	  // Find the proc with the biggest period that we can split (to put on maxproc)
	  maxproc2=-1; maxp=0;
	  for (j=0; j<p; j++)
	    if ((per[j]>maxp) && (end[j]-start[j]!=0) && (per[j]>fixp)){
	      maxp=per[j]; maxproc2=j;
	    }
	  if (maxproc2!=-1) {
	    //printf("Spliting maxproc2=%d\n", maxproc2);
	    // Find l where to cut the interval to min the max of the 2 resultant periods
	    ll=-1;
	    for (l=start[maxproc2]; l<end[maxproc2]; l++) {
	      // Case 1: start..l on maxproc2 and l..end on maxproc
	      pp[1]=(d[k][start[maxproc2]]+d[k][l+1])/B[k];
	      for(j=start[maxproc2]; j<=l; j++) pp[1]+=w[k][j]/s[k][maxproc2];
	      pp[2]=(d[k][l+1]+d[k][end[maxproc2]+1])/B[k];
	      for(j=l+1; j<=end[maxproc2]; j++) pp[2]+=w[k][j]/s[k][maxproc];
	      if (pp[2]>pp[1]) pp[0]=pp[2]; else pp[0]=pp[1];
	      
	      // Case 2: start..l on maxproc  and l..end on maxproc2
	      pp[4]=(d[k][start[maxproc2]]+d[k][l+1])/B[k];
	      for(j=start[maxproc2]; j<=l; j++) pp[4]+=w[k][j]/s[k][maxproc];
	      pp[5]=(d[k][l+1]+d[k][end[maxproc2]+1])/B[k];
	      for(j=l+1; j<=end[maxproc2]; j++) pp[5]+=w[k][j]/s[k][maxproc2];
	      if (pp[4]>pp[5]) pp[3]=pp[4]; else pp[3]=pp[5];
	      
	      //if (k==3)
	      //printf("l=%d -- pp: 0=%f, 1=%f, 2=%f, 3=%f, 4=%f, 5=%f, maxp=%f\n",l,pp[0],pp[1],pp[2],pp[3],pp[4],pp[5],maxp);
	      
	      // Find out if this l is better, and for which configuration
	      if ((pp[0] < maxp)&&(pp[0]<pp[3])) {
		ll=l; jj=1; max1=pp[1]; max2=pp[2]; maxp=pp[0];
	      }
	      else if (pp[3]<maxp) {
		ll=l; jj=2; max1=pp[4]; max2=pp[5]; maxp=pp[3];
	      }
	    }
	    if (ll!=-1) {
	      // Perform the best cut
	      //printf("k=%d: cut with ll=%d\n",k,ll);
	      usedproc[maxproc]=1;
	      if (jj==1) { 
		if (MEGADEBUG) printf("lat before split %f,",	latency[z][heuristic][k]);
		latency[z][heuristic][k]-=per[maxproc2]; 
		end[maxproc]=end[maxproc2];
		end[maxproc2]=ll;
		start[maxproc]=ll+1;
		per[maxproc2]=max1; per[maxproc]=max2;
		latency[z][heuristic][k]+=(per[maxproc]+per[maxproc2]-(d[k][ll+1]/B[k]));
		if (MEGADEBUG) printf("lat after split %f\n",	latency[z][heuristic][k]); 
		for (j=0; j<p; j++)
		  if (usedproc[j]) {
		    if (MEGADEBUG) printf("proc %d for interval %d-%d: period %f\n",
					  j, start[j], end[j], per[j]);
		  }
		
		
	      }
	      else {
		if (MEGADEBUG) printf("lat before split %f,",	latency[z][heuristic][k]);
		latency[z][heuristic][k]-=per[maxproc2];
		start[maxproc]=start[maxproc2];
		end[maxproc]=ll;
		start[maxproc2]=ll+1;
		per[maxproc]=max1; per[maxproc2]=max2;
		latency[z][heuristic][k]+=(per[maxproc]+per[maxproc2]-(d[k][ll+1]/B[k]));  
		if (MEGADEBUG) printf("lat after split %f\n",	latency[z][heuristic][k]); 
		for (j=0; j<p; j++)
		  if (usedproc[j]) {
		    if (MEGADEBUG) printf("proc %d for interval %d-%d: period %f\n",
					  j, start[j], end[j], per[j]);
		  }
	      }
	      if (MEGADEBUG) printf("splitting interval: old proc: %d, p=%f, new proc: %d, p=%f, l=%f\n",
				    maxproc2,per[maxproc2], maxproc,per[maxproc], latency[z][heuristic][k]);
	    }
	    else {//Nothing more we can do...
	      //printf("no best place where to split\n");
	      kk=0;
	    }
	  }
	  else {//Nothing more we can do...
	    //printf("no interval where to split\n");
	    kk=0;
	  }
	}
	else  {//Nothing more we can do...
	  //printf("no more free proc\n");
	  kk=0;
	}
      }
      
      for (j=0; j<p; j++)
	if (usedproc[j]) {
	  if (DEBUG) fprintf(idf[k],"H1: choosing proc %d for interval %d-%d: period %f\n",
			     j, start[j], end[j], per[j]);
	  //printf("j=%d, p=%d, maxperiod=%d, per[j]=%d, latency=%d\n",j,p,maxperiod,per[j],latency[heuristic][k]);
	  if (per[j] > maxperiod) maxperiod=per[j];
	}
      if (DEBUG) fprintf(idf[k],"H1: maxperiod=%f\n\n", maxperiod);
      if (DEBUG) fprintf(idf[k],"H1: latence=%f\n\n", latency[z][heuristic][k]);
      if (DEBUG) if (maxperiod>fixp) fprintf(idf[k],"H1: FIXED PERIOD NOT REACHED!!\n\n");
      //fprintf(plot[heuristic], "%d %f\n", n, maxperiod);
      totperiod[z][heuristic][k]+=maxperiod;
      totlatency[z][heuristic][k]+=latency[z][heuristic][k];
      
      printf("\nheuristic 2a starts, fixedp=%f\n",fixp);
      
      // *********** Heuristic 2a: 3-Exploration mono-criterion: ************
      // ***********               searching for pair c1, c2     ************
      // ***********               that increases the less L     ************
      heuristic=1;
      
      double newlatency; //global temporary latency
      double llat[6]; //temporary latency in 3explo-step
      // double ratio[6]; //ratio
      
      int maxproc1;
      double maxs1,minlat,mind,max3;
      double llat1,llat2;
      int bestcut=-1;;
      int c1,c2,loop;
      
      
    for(j=0; j<p; j++) {
      usedproc[j]=0;
      // per[j]=-1;
      //  llat[j]=0;
      start[j]=0; end[j]=0; per[j]=0;
    }
  
    maxperiod=-1; kk=1;
    loop=0;
    while(kk) {
      loop++;
    if (MEGADEBUG) printf("\n--------------------\nloop: %d\n-------------------------\n\n",loop);
      if(loop==50)kk=0;

      maxproc=-1; maxs=-1;
      maxproc1=-1; maxs1=-1;
      //find fastest proc (maxproc)
      for (j=0; j<p; j++)
	if ((s[k][j]>maxs)&&(usedproc[j]==0)) {
	  maxproc=j; maxs=s[k][j];
	}
      //if(maxproc==-1)kk=0;
      
      //find second fastest proc (maxproc1)
      for (j=0; j<p; j++){
	//	printf("searching for maxproc1\n");
	//printf("s[k][%d]=%f, maxs1=%f, usedproc[%d]=%d, maxproc=%d,\n",j,s[k][j],maxs1,j,usedproc[j],maxproc);
	if ((s[k][j]>maxs1)&&(usedproc[j]==0)&& (maxproc!=j)) {
	  //printf("found one: %d\n",j);
	  maxproc1=j; maxs1=s[k][j];
	}
      }
      if (MEGADEBUG) printf("maxproc %d\n",maxproc);
      if(maxperiod==-1) {
	// First time in the loop: start[p]=0 and end[p]=n-1;
	start[maxproc]=0; end[maxproc]=n-1; usedproc[maxproc]=1;
	// compute the corresponding period
	per[maxproc] = (d[k][0]+d[k][n])/B[k];
	for (i=0; i<n; i++) per[maxproc] += w[k][i]/maxs;
	maxperiod=0;
	//latence corresponds to the period of the fastest proc as it is the only chosen proc
	//lowerbound!!
	latency[z][heuristic][k]=per[maxproc];
	if (MEGADEBUG) printf("init: all on fastest proc: %d, p=%f, l=%f\n",maxproc,per[maxproc], latency[z][heuristic][k]);
	if(per[maxproc] <= fixp) {
	  kk=0;
	  if (MEGADEBUG) printf("fixed period already reached, proc %d, p=l=%f\n",maxproc,per[maxproc]);
	}
      }
      else if (maxproc!=-1) {
 if (MEGADEBUG)	printf("maxproc!=-1, entering to split\n");
	//search for proc with maxperiod (maxproc2) to split
	maxproc2=-1; maxp=0;
	for (j=0; j<p; j++)
	  if ((per[j]>maxp) && (end[j]-start[j]!=0) && (per[j]>fixp)){
	    maxp=per[j]; maxproc2=j;
	  }
	
 if (MEGADEBUG)	printf("maxproc=%d, maxproc1=%d, macproc2=%d to split\n",maxproc,maxproc1,maxproc2);

	if (maxp > fixp) {
	  minlat=MAXDOUBLE;
	  
	  //	c1=-1; c2=-1;
	  ll=-1;
	  if((maxproc1!=-1) && ((end[maxproc2]-start[maxproc2])>1)) {
	    // 2 procs are free, and interval can be cut in 3 parts
	    for (ii=start[maxproc2];ii<end[maxproc2]-1;ii++) {
	      for (jj=ii+1,ii<jj;jj<end[maxproc2];jj++) {
		 if (MEGADEBUG) printf("ii=%d, jj=%d\n",ii,jj);
		// Case 1: start..ii on maxproc2 and ii+1..jj on maxproc1 and jj+1..end maxproc
		pp[1]=(d[k][start[maxproc2]]+d[k][ii+1])/B[k];
		for(j=start[maxproc2]; j<=ii; j++) pp[1]+=w[k][j]/s[k][maxproc2];
		pp[2]=(d[k][ii+1]+d[k][jj+1])/B[k];
		for(j=ii+1; j<=jj; j++) pp[2]+=w[k][j]/s[k][maxproc1];
		pp[3]=(d[k][jj+1]+d[k][end[maxproc2]+1])/B[k];
		for(j=jj+1; j<=end[maxproc2]; j++) pp[3]+=w[k][j]/s[k][maxproc];
		llat[0]=latency[z][heuristic][k]-per[maxproc2]+pp[1]+pp[2]+pp[3]-(d[k][ii+1]/B[k])-(d[k][jj+1]/B[k]);
		pp[0]=getMaxP(pp[1],pp[2],pp[3]);
	 if (MEGADEBUG)	printf("%f, %f, %f\n",pp[1],pp[2],pp[3]);

		// Case 2: start..ii on maxproc2  and ii+1..jj on maxproc and jj+1..end on maxproc1
		pp[5]=(d[k][start[maxproc2]]+d[k][ii+1])/B[k];
		for(j=start[maxproc2]; j<=ii; j++) pp[5]+=w[k][j]/s[k][maxproc2];
		pp[6]=(d[k][ii+1]+d[k][jj+1])/B[k];
		for(j=ii+1; j<=jj; j++) pp[6]+=w[k][j]/s[k][maxproc];
		pp[7]=(d[k][jj+1]+d[k][end[maxproc2]+1])/B[k];
		for(j=jj+1; j<=end[maxproc2]; j++) pp[7]+=w[k][j]/s[k][maxproc1];
		llat[1]=latency[z][heuristic][k]-per[maxproc2]+pp[5]+pp[6]+pp[7]-(d[k][ii+1]/B[k])-(d[k][jj+1]/B[k]);
	 if (MEGADEBUG)	printf("%f, %f, %f\n",pp[5],pp[6],pp[7]);
		pp[4]=getMaxP(pp[5],pp[6],pp[7]);

		// Case 3: start..ii on maxproc1  and ii+1..jj on maxproc and jj+1..end on maxproc2
		pp[9]=(d[k][start[maxproc2]]+d[k][ii+1])/B[k];
		for(j=start[maxproc2]; j<=ii; j++) pp[9]+=w[k][j]/s[k][maxproc1];
		pp[10]=(d[k][ii+1]+d[k][jj+1])/B[k];
		for(j=ii+1; j<=jj; j++) pp[10]+=w[k][j]/s[k][maxproc];
		pp[11]=(d[k][jj+1]+d[k][end[maxproc2]+1])/B[k];
		for(j=jj+1; j<=end[maxproc2]; j++) pp[11]+=w[k][j]/s[k][maxproc2];
		llat[2]=latency[z][heuristic][k]-per[maxproc2]+pp[9]+pp[10]+pp[11]-(d[k][ii+1]/B[k])-(d[k][jj+1]/B[k]);
	 if (MEGADEBUG)	printf("%f, %f, %f\n",pp[9],pp[10],pp[11]);
		pp[8]=getMaxP(pp[9],pp[10],pp[11]);

		// Case 4: start..ii on maxproc1  and ii+1..jj on maxproc2 and jj+1..end on maxproc
		pp[13]=(d[k][start[maxproc2]]+d[k][ii+1])/B[k];
		for(j=start[maxproc2]; j<=ii; j++) pp[13]+=w[k][j]/s[k][maxproc1];
		pp[14]=(d[k][ii+1]+d[k][jj+1])/B[k];
		for(j=ii+1; j<=jj; j++) pp[14]+=w[k][j]/s[k][maxproc2];
		pp[15]=(d[k][jj+1]+d[k][end[maxproc2]+1])/B[k];
		for(j=jj+1; j<=end[maxproc2]; j++) pp[15]+=w[k][j]/s[k][maxproc];
		llat[3]=latency[z][heuristic][k]-per[maxproc2]+pp[13]+pp[14]+pp[15]-(d[k][ii+1]/B[k])-(d[k][jj+1]/B[k]);
	 if (MEGADEBUG)	printf("%f, %f, %f\n",pp[13],pp[14],pp[15]);
		pp[12]=getMaxP(pp[13],pp[14],pp[15]);

		// Case 5: start..ii on maxproc  and ii+1..jj on maxproc1 and jj+1..end on maxproc2
		pp[17]=(d[k][start[maxproc2]]+d[k][ii+1])/B[k];
		for(j=start[maxproc2]; j<=ii; j++) pp[17]+=w[k][j]/s[k][maxproc];
		pp[18]=(d[k][ii+1]+d[k][jj+1])/B[k];
		for(j=ii+1; j<=jj; j++) pp[18]+=w[k][j]/s[k][maxproc1];
		pp[19]=(d[k][jj+1]+d[k][end[maxproc2]+1])/B[k];
		for(j=jj+1; j<=end[maxproc2]; j++) pp[19]+=w[k][j]/s[k][maxproc2];
		llat[4]=latency[z][heuristic][k]-per[maxproc2]+pp[17]+pp[18]+pp[19]-(d[k][ii+1]/B[k])-(d[k][jj+1]/B[k]);
	 if (MEGADEBUG)	printf("%f, %f, %f\n",pp[17],pp[18],pp[19]);
		pp[16]=getMaxP(pp[17],pp[18],pp[19]);
		
		// Case 6: start..ii on maxproc  and ii+1..jj on maxproc2 and jj+1..end on maxproc1
		pp[21]=(d[k][start[maxproc2]]+d[k][ii+1])/B[k];
		for(j=start[maxproc2]; j<=ii; j++) pp[21]+=w[k][j]/s[k][maxproc];
		pp[22]=(d[k][ii+1]+d[k][jj+1])/B[k];
		for(j=ii+1; j<=jj; j++) pp[22]+=w[k][j]/s[k][maxproc2];
		pp[23]=(d[k][jj+1]+d[k][end[maxproc2]+1])/B[k];
		for(j=jj+1; j<=end[maxproc2]; j++) pp[23]+=w[k][j]/s[k][maxproc1];
		llat[5]=latency[z][heuristic][k]-per[maxproc2]+pp[21]+pp[22]+pp[23]-(d[k][ii+1]/B[k])-(d[k][jj+1]/B[k]);
	 if (MEGADEBUG)	printf("%f, %f, %f\n",pp[21],pp[22],pp[23]);
		pp[20]=getMaxP(pp[21],pp[22],pp[23]);

		for(j=0;j<6;j++)
	 if (MEGADEBUG)	  printf("llat[%d]=%f\n",j,llat[j]);
		//double minlat=-1;
		double tmpperiod=-1;
		int cut=-1;
		for(j=0;j<6;j++){
		  //printf("llat[%d]=%f, minlat=%f\n",j,llat[j],minlat);
		  if ((llat[j]<=minlat)) {
		    //printf("inif\n");
		    minlat=llat[j];
		    tmpperiod=pp[j*4];
		    bestcut=j;
		    cut=0;
		  }
		}
		//	if (DEBUG) printf("bestcut: %d, minlat=%f,tempp=%f\n",bestcut,minlat,tmpperiod);
		
		if(cut!=-1) { //we found a pair c1,c2 wich increases les the global latency

 		  ll=bestcut; c1=ii; c2=jj; max1=pp[bestcut*4+1]; max2=pp[bestcut*4+2]; max3=pp[bestcut*4+3]; newlatency=minlat;
		  if (MEGADEBUG) printf("bestcut=%d, cut1=%d, cut2=%d, max1=%f, max2=%f, max3=%f\n",ll,c1+1,c2+1,max1,max2,max3);
		  if(getMaxP(max1,max2,max3)>=maxp) {
		    kk=0;
		    printf("period not diminuated even with cuts");
		  }
		}
	      }
	    }
	    if (MEGADEBUG) printf("\nperform the best cut avec cut1=%d, cut2=%d, p1=%f, p2=%f, p3=%f, lat=%f\n",c1+1,c2+1,max1,max2,max3,newlatency);
	    if (DEBUG) fprintf(idf[k],"H2b: interval1 %d-%d, interval2 %d-%d, interval3 %d-%d\n",start[maxproc2],c1,c1+1,c2,c2+1,end[maxproc2]);
	    if(c1>c2)printf("\n!!!!!!!!!!!!!!!!!!!!!ATTENTION!!!!!!!!!!!!!!!!\nc1 > c2");
	    if(ll!=-1) {
	      usedproc[maxproc]=1;
	      usedproc[maxproc1]=1;
	      //Perform the best cut
	      switch(ll) {
	      case 0: latency[z][heuristic][k]=newlatency;
		end[maxproc]=end[maxproc2];
		end[maxproc2]=c1; end[maxproc1]=c2;
		start[maxproc1]=c1+1; start[maxproc]=c2+1;
		per[maxproc2]=max1; per[maxproc1]=max2;	per[maxproc]=max3;
		break;
	      case 1: latency[z][heuristic][k]=newlatency;
		end[maxproc1]=end[maxproc2];
		end[maxproc2]=c1;
		end[maxproc]=c2;
		start[maxproc]=c1+1; start[maxproc1]=c2+1;
		per[maxproc2]=max1; per[maxproc]=max2; per[maxproc1]=max3;
		break;
	      case 2: latency[z][heuristic][k]=newlatency;
		end[maxproc1]=c1;
		end[maxproc]=c2;
		start[maxproc]=c1+1; start[maxproc1]=start[maxproc2]; start[maxproc2]=c2+1;
		per[maxproc1]=max1; per[maxproc]=max2; per[maxproc2]=max3;
		break;
	      case 3: latency[z][heuristic][k]=newlatency;
		end[maxproc1]=c1;
		end[maxproc]=end[maxproc2]; end[maxproc2]=c2;
		start[maxproc1]=start[maxproc2]; start[maxproc2]=c1+1; start[maxproc]=c2+1;
		per[maxproc1]=max1; per[maxproc2]=max2; per[maxproc]=max3;
		break;
	      case 4:latency[z][heuristic][k]=newlatency;
		end[maxproc]=c1;
		end[maxproc1]=c2;
		start[maxproc]=start[maxproc2]; start[maxproc1]=c1+1; start[maxproc2]=c2+1;
		per[maxproc]=max1; per[maxproc1]=max2; per[maxproc2]=max3;
		break;
	      case 5:latency[z][heuristic][k]=newlatency;
		end[maxproc1]=end[maxproc2];
		end[maxproc]=c1;
		end[maxproc2]=c2;
		start[maxproc]=start[maxproc2]; start[maxproc2]=c1+1; start[maxproc1]=c2+1;
		per[maxproc]=max1; per[maxproc2]=max2; per[maxproc1]=max3;
		break;
		//default:
		//continue;
	      }
	    } // no possible pair c1,c2 was found
	    else {
	      kk=0;
	      printf("attention! no possible cut was found!\n");
	      
	    }
	    
	  }
	  else {
	    //only 1 proc is free, or interval < 3, so we do only 1 cut
	    //search for fastest comm
	    printf("only 1 proc is free, or interval < 3, so we do only 1 cut\n");
	    // Find the proc with the biggest period that we can split (to put on maxproc)
	    maxproc2=-1; maxp=0;
	    for (j=0; j<p; j++)
	      if ((per[j]>maxp) && (end[j]-start[j]!=0) && (per[j]>fixp)){
		maxp=per[j]; maxproc2=j;
	      }

	if (MEGADEBUG) printf("maxproc2 to split: %d to put on maxproc %d\n",maxproc2,maxproc);
 
	    if ((maxproc!=-1)) {
	      bestcut=-1;
	      mind=MAXDOUBLE;	printf("start[maxproc2]=%d,end[maxproc2]=%d\n",start[maxproc2],end[maxproc2]);
	      for (j=start[maxproc2]+1;j<=end[maxproc2];j++){
		printf("j=%d\n",j);
		if (d[k][j]<mind) {
		  bestcut=j;
		  mind=d[k][j];
		}
	      }
	     if (MEGADEBUG) printf("bestcut=%d\n",bestcut);
	      if (bestcut!=-1) {
		//perform bestcut
		double llat1,llat2;
		// Case 1: start..bestcut on maxproc2 and bestcut..end on maxproc
		pp[1]=(d[k][start[maxproc2]]+d[k][bestcut])/B[k];
		for(j=start[maxproc2]; j<bestcut; j++) pp[1]+=w[k][j]/s[k][maxproc2];
		pp[2]=(d[k][bestcut]+d[k][end[maxproc2]+1])/B[k];
		for(j=bestcut; j<=end[maxproc2]; j++) pp[2]+=w[k][j]/s[k][maxproc];
		if (pp[2]>pp[1]) pp[0]=pp[2]; else pp[0]=pp[1];
		llat1=latency[z][heuristic][k]-per[maxproc2]+pp[1]+pp[2]-(d[k][bestcut]/B[k]);
		// Case 2: start..bestcut on maxproc  and bestcut..end on maxproc2
		pp[4]=(d[k][start[maxproc2]]+d[k][bestcut])/B[k];
		for(j=start[maxproc2]; j<bestcut; j++) pp[4]+=w[k][j]/s[k][maxproc];
		pp[5]=(d[k][bestcut]+d[k][end[maxproc2]+1])/B[k];
		for(j=bestcut; j<=end[maxproc2]; j++) pp[5]+=w[k][j]/s[k][maxproc2];
		if (pp[4]>pp[5]) pp[3]=pp[4]; else pp[3]=pp[5];
		llat2=latency[z][heuristic][k]-per[maxproc2]+pp[4]+pp[5]-(d[k][bestcut]/B[k]);
		//	    if (k==3)
		// printf("l=%d -- pp: 0=%f, 1=%f, 2=%f, 3=%f, 4=%f, 5=%f\n",l,pp[0],pp[1],pp[2],pp[3],pp[4],pp[5]);
		 
		// Find out if this cut increases p max, and for which configuration latency is the best
		if (llat1<llat2) {
		  ll=bestcut; jj=1; max1=pp[1]; max2=pp[2]; maxp=pp[0];
		}
		else  {
		  ll=bestcut; jj=2; max1=pp[4]; max2=pp[5]; maxp=pp[3];
		}
		if (MEGADEBUG) printf("bestcut=%d, max1=%f, max2=%f\n",bestcut,max1,max2);
		//perform cut
		usedproc[maxproc]=1;
		if (jj==1) {
		  latency[z][heuristic][k]=llat1;
		  end[maxproc]=end[maxproc2];
		  end[maxproc2]=bestcut-1;
		  start[maxproc]=bestcut;
		  per[maxproc2]=max1; per[maxproc]=max2;
		}
		else {
		  latency[z][heuristic][k]=llat2;
		  end[maxproc2]=bestcut-1;
		  start[maxproc]=start[maxproc2];
		  start[maxproc2]=bestcut;
		  per[maxproc]=max1; per[maxproc2]=max2;
		  
		}
		
	      } else { // no possible cut was found
		kk=0;
		printf("no possible cut was found\n");
	      }
	    
	    } else { //no more proc free
	      kk=0;
	      printf("no more proc free\n");
	    }
	  
	  }
	} else { //maxp <= fixp, we do not need to split anymore
	  kk=0;	printf("maxp <= fixp, we do not need to split anymore\n");
	}
      } else { //no more proc free
	kk=0;
	printf("no more proc free\n");
      }
    }
	   

    for (j=0; j<p; j++)
      if (usedproc[j]) {
	if (DEBUG) fprintf(idf[k],"H2a: choosing proc %d for interval %d-%d: period %f\n",
		j, start[j], end[j], per[j]);
	printf("j=%d, p=%d, maxperiod=%f, per[j]=%f, latency=%f\n",j,p,maxperiod,per[j],latency[z][heuristic][k]);
		if (per[j] > maxperiod) maxperiod=per[j];
      }
    if (DEBUG) fprintf(idf[k],"H2a: maxperiod=%f\n\n", maxperiod);
    if (DEBUG) fprintf(idf[k],"H2a: latence=%f\n\n", latency[z][heuristic][k]);
    if (DEBUG) if (maxperiod>fixp) fprintf(idf[k],"H2a: FIXED PERIOD NOT REACHED!!\n\n");
    //fprintf(plot[heuristic], "%d %f\n", n, maxperiod);
    totperiod[z][heuristic][k]+=maxperiod;
    totlatency[z][heuristic][k]+=latency[z][heuristic][k];
	
    // *********** Heuristic 2b: 3-Exploration bi-criterion:       ************
    // ***********               searching for pair c1, c2         ************
    // ***********               that has best ratio on profit l/p ************
      heuristic=2;
      double gain[6];
      double maxgain,globalgain;
      //    double llat1,llat2;
     
    for(j=0; j<p; j++) {
      usedproc[j]=0;
      // per[j]=-1;
      //  llat[j]=0;
      start[j]=0; end[j]=0; per[j]=0;
    }
  
    maxperiod=-1; kk=1;
    loop=0;
    while(kk) {
      loop++;
     if (MEGADEBUG)  printf("\n--------------------\nloop: %d\n-------------------------\n\n",loop);
      if(loop==50)kk=0;

      maxproc=-1; maxs=-1;
      maxproc1=-1; maxs1=-1;
      //find fastest proc (maxproc)
      for (j=0; j<p; j++)
	if ((s[k][j]>maxs)&&(usedproc[j]==0)) {
	  maxproc=j; maxs=s[k][j];
	}
      //if(maxproc==-1)kk=0;
      
      //find second fastest proc (maxproc1)
      for (j=0; j<p; j++){
	//	printf("searching for maxproc1\n");
	//printf("s[k][%d]=%f, maxs1=%f, usedproc[%d]=%d, maxproc=%d,\n",j,s[k][j],maxs1,j,usedproc[j],maxproc);
	if ((s[k][j]>maxs1)&&(usedproc[j]==0)&& (maxproc!=j)) {
	  //printf("found one: %d\n",j);
	  maxproc1=j; maxs1=s[k][j];
	}
      }
     if (MEGADEBUG) printf("maxproc %d\n",maxproc);
      if(maxperiod==-1) {
	// First time in the loop: start[p]=0 and end[p]=n-1;
	start[maxproc]=0; end[maxproc]=n-1; usedproc[maxproc]=1;
	// compute the corresponding period
	per[maxproc] = (d[k][0]+d[k][n])/B[k];
	for (i=0; i<n; i++) per[maxproc] += w[k][i]/maxs;
	maxperiod=0;
	//latence corresponds to the period of the fastest proc as it is the only chosen proc
	//lowerbound!!
	latency[z][heuristic][k]=per[maxproc];
	if (MEGADEBUG) printf("init: all on fastest proc: %d, p=%f, l=%f\n",maxproc,per[maxproc], latency[z][heuristic][k]);
	if(per[maxproc] <= fixp) {
	  kk=0;
	  if (MEGADEBUG) printf("fixed period already reached, proc %d, p=l=%f\n",maxproc,per[maxproc]);
	}
      }
      else if (maxproc!=-1) {
if (MEGADEBUG)	printf("maxproc!=-1, entering to split\n");
	//search for proc with maxperiod (maxproc2) to split
	maxproc2=-1; maxp=0;
	for (j=0; j<p; j++)
	  if ((per[j]>maxp) && (end[j]-start[j]!=0) && (per[j]>fixp)){
	    maxp=per[j]; maxproc2=j;
	  }
	
if (MEGADEBUG)	printf("maxproc=%d, maxproc1=%d, macproc2=%d to split\n",maxproc,maxproc1,maxproc2);

	if (maxp > fixp) {
	  globalgain=MAXDOUBLE;
	  
	  //	c1=-1; c2=-1;
	  ll=-1;
	  if((maxproc1!=-1) && ((end[maxproc2]-start[maxproc2])>1)) {
	    // 2 procs are free, and interval can be cut in 3 parts
	    for (ii=start[maxproc2];ii<end[maxproc2]-1;ii++) {
	      for (jj=ii+1,ii<jj;jj<end[maxproc2];jj++) {
	if (MEGADEBUG) printf("ii=%d, jj=%d\n",ii,jj);
		// Case 1: start..ii on maxproc2 and ii+1..jj on maxproc1 and jj+1..end maxproc
		pp[1]=(d[k][start[maxproc2]]+d[k][ii+1])/B[k];
		for(j=start[maxproc2]; j<=ii; j++) pp[1]+=w[k][j]/s[k][maxproc2];
		pp[2]=(d[k][ii+1]+d[k][jj+1])/B[k];
		for(j=ii+1; j<=jj; j++) pp[2]+=w[k][j]/s[k][maxproc1];
		pp[3]=(d[k][jj+1]+d[k][end[maxproc2]+1])/B[k];
		for(j=jj+1; j<=end[maxproc2]; j++) pp[3]+=w[k][j]/s[k][maxproc];
		llat[0]=latency[z][heuristic][k]-per[maxproc2]+pp[1]+pp[2]+pp[3]-(d[k][ii+1]/B[k])-(d[k][jj+1]/B[k]);
		pp[0]=getMaxP(pp[1],pp[2],pp[3]);
		gain[0]=(llat[0]-latency[z][heuristic][k])/(maxp-pp[0]);

		// Case 2: start..ii on maxproc2  and ii+1..jj on maxproc and jj+1..end on maxproc1
		pp[5]=(d[k][start[maxproc2]]+d[k][ii+1])/B[k];
		for(j=start[maxproc2]; j<=ii; j++) pp[5]+=w[k][j]/s[k][maxproc2];
		pp[6]=(d[k][ii+1]+d[k][jj+1])/B[k];
		for(j=ii+1; j<=jj; j++) pp[6]+=w[k][j]/s[k][maxproc];
		pp[7]=(d[k][jj+1]+d[k][end[maxproc2]+1])/B[k];
		for(j=jj+1; j<=end[maxproc2]; j++) pp[7]+=w[k][j]/s[k][maxproc1];
		llat[1]=latency[z][heuristic][k]-per[maxproc2]+pp[5]+pp[6]+pp[7]-(d[k][ii+1]/B[k])-(d[k][jj+1]/B[k]);
		pp[4]=getMaxP(pp[5],pp[6],pp[7]);
		gain[1]=(llat[1]-latency[z][heuristic][k])/(maxp-pp[4]);
		
		// Case 3: start..ii on maxproc1  and ii+1..jj on maxproc and jj+1..end on maxproc2
		pp[9]=(d[k][start[maxproc2]]+d[k][ii+1])/B[k];
		for(j=start[maxproc2]; j<=ii; j++) pp[9]+=w[k][j]/s[k][maxproc1];
		pp[10]=(d[k][ii+1]+d[k][jj+1])/B[k];
		for(j=ii+1; j<=jj; j++) pp[10]+=w[k][j]/s[k][maxproc];
		pp[11]=(d[k][jj+1]+d[k][end[maxproc2]+1])/B[k];
		for(j=jj+1; j<=end[maxproc2]; j++) pp[11]+=w[k][j]/s[k][maxproc2];
		llat[2]=latency[z][heuristic][k]-per[maxproc2]+pp[9]+pp[10]+pp[11]-(d[k][ii+1]/B[k])-(d[k][jj+1]/B[k]);
		pp[8]=getMaxP(pp[9],pp[10],pp[11]);
		gain[2]=(llat[2]-latency[z][heuristic][k])/(maxp-pp[8]);
		
		// Case 4: start..ii on maxproc1  and ii+1..jj on maxproc2 and jj+1..end on maxproc
		pp[13]=(d[k][start[maxproc2]]+d[k][ii+1])/B[k];
		for(j=start[maxproc2]; j<=ii; j++) pp[13]+=w[k][j]/s[k][maxproc1];
		pp[14]=(d[k][ii+1]+d[k][jj+1])/B[k];
		for(j=ii+1; j<=jj; j++) pp[14]+=w[k][j]/s[k][maxproc2];
		pp[15]=(d[k][jj+1]+d[k][end[maxproc2]+1])/B[k];
		for(j=jj+1; j<=end[maxproc2]; j++) pp[15]+=w[k][j]/s[k][maxproc];
		llat[3]=latency[z][heuristic][k]-per[maxproc2]+pp[13]+pp[14]+pp[15]-(d[k][ii+1]/B[k])-(d[k][jj+1]/B[k]);
		pp[12]=getMaxP(pp[13],pp[14],pp[15]);
		gain[3]=(llat[3]-latency[z][heuristic][k])/(maxp-pp[12]);

		// Case 5: start..ii on maxproc  and ii+1..jj on maxproc1 and jj+1..end on maxproc2
		pp[17]=(d[k][start[maxproc2]]+d[k][ii+1])/B[k];
		for(j=start[maxproc2]; j<=ii; j++) pp[17]+=w[k][j]/s[k][maxproc];
		pp[18]=(d[k][ii+1]+d[k][jj+1])/B[k];
		for(j=ii+1; j<=jj; j++) pp[18]+=w[k][j]/s[k][maxproc1];
		pp[19]=(d[k][jj+1]+d[k][end[maxproc2]+1])/B[k];
		for(j=jj+1; j<=end[maxproc2]; j++) pp[19]+=w[k][j]/s[k][maxproc2];
		llat[4]=latency[z][heuristic][k]-per[maxproc2]+pp[17]+pp[18]+pp[19]-(d[k][ii+1]/B[k])-(d[k][jj+1]/B[k]);
		pp[16]=getMaxP(pp[17],pp[18],pp[19]);
		gain[4]=(llat[4]-latency[z][heuristic][k])/(maxp-pp[16]);
		
		// Case 6: start..ii on maxproc  and ii+1..jj on maxproc2 and jj+1..end on maxproc1
		pp[21]=(d[k][start[maxproc2]]+d[k][ii+1])/B[k];
		for(j=start[maxproc2]; j<=ii; j++) pp[21]+=w[k][j]/s[k][maxproc];
		pp[22]=(d[k][ii+1]+d[k][jj+1])/B[k];
		for(j=ii+1; j<=jj; j++) pp[22]+=w[k][j]/s[k][maxproc2];
		pp[23]=(d[k][jj+1]+d[k][end[maxproc2]+1])/B[k];
		for(j=jj+1; j<=end[maxproc2]; j++) pp[23]+=w[k][j]/s[k][maxproc1];
		llat[5]=latency[z][heuristic][k]-per[maxproc2]+pp[21]+pp[22]+pp[23]-(d[k][ii+1]/B[k])-(d[k][jj+1]/B[k]);
		pp[20]=getMaxP(pp[21],pp[22],pp[23]);
		gain[5]=(llat[5]-latency[z][heuristic][k])/(maxp-pp[20]);

		maxgain=MAXDOUBLE;
		double tmpperiod=-1;
		int cut=-1;
		for(j=0;j<6;j++){
		  if (MEGADEBUG) printf("gain[%d]=%f, old globalgain=%f llat[%d]=%f, p[%d]=%f\n",j,gain[j],globalgain,j,llat[j],j*4,pp[j*4]);
		  if ((gain[j]<=maxgain) && (gain[j]>0) && (gain[j]<globalgain)) {
		    //printf("inif\n");
		    maxgain=gain[j];
		    globalgain=gain[j];
		    minlat=llat[j];
		    tmpperiod=pp[j*4];
		    bestcut=j;
		    cut=0;
		  }
		}
		//	if (DEBUG) printf("bestcut: %d, minlat=%f,tempp=%f\n",bestcut,minlat,tmpperiod);
		
		if(cut!=-1) { //we found a pair c1,c2 wich has the best gain deltaL/deltaP;
		  //		  ll=bestcut; c1=ii; c2=jj; max1=pp[bestcut*4+1]; max2=pp[bestcut*4+2]; max3=pp[bestcut*4+3]; newlatency=minlat;
		  ll=bestcut; c1=ii; c2=jj; max1=pp[bestcut*4+1]; max2=pp[bestcut*4+2]; max3=pp[bestcut*4+3]; newlatency=minlat;
		  if (DEBUG) printf("ll=%d, cut1=%d, cut2=%d, max1=pp[%d]=%f, max2=pp[%d]=%f, max3=pp[%d]=%f\n",bestcut,c1+1,c2+1,bestcut*4+1,max1,bestcut*4+2,max2,bestcut*4+3,max3);
		  if(getMaxP(max1,max2,max3)>=maxp) {
		    kk=0;
		    printf("period not diminuated even with cuts");
		  }
		}
	      }
	    }
	    if (MEGADEBUG) printf("\nperform the best cut avec c1=%d, c2=%d, p1=%f, p2=%f, p3=%f, lat=%f\n",c1,c2,max1,max2,max3,newlatency);
	    if (DEBUG) fprintf(idf[k],"H2b: interval1 %d-%d, interval2 %d-%d, interval3 %d-%d\n",start[maxproc2],c1,c1+1,c2,c2+1,end[maxproc2]);
	    if(c1>c2)printf("\n!!!!!!!!!!!!!!!!!!!!!ATTENTION!!!!!!!!!!!!!!!!\nc1 > c2");
	    if(ll!=-1) {
	      usedproc[maxproc]=1;
	      usedproc[maxproc1]=1;
	      //Perform the best cut
	      switch(ll) {
	      case 0: latency[z][heuristic][k]=newlatency;
		end[maxproc]=end[maxproc2];
		end[maxproc2]=c1; end[maxproc1]=c2;
		start[maxproc1]=c1+1; start[maxproc]=c2+1;
		per[maxproc2]=max1; per[maxproc1]=max2;	per[maxproc]=max3;
		break;
	      case 1: latency[z][heuristic][k]=newlatency;
		end[maxproc1]=end[maxproc2];
		end[maxproc2]=c1;
		end[maxproc]=c2;
		start[maxproc]=c1+1; start[maxproc1]=c2+1;
		per[maxproc2]=max1; per[maxproc]=max2; per[maxproc1]=max3;
		break;
	      case 2: latency[z][heuristic][k]=newlatency;
		end[maxproc1]=c1;
		end[maxproc]=c2;
		start[maxproc]=c1+1; start[maxproc1]=start[maxproc2]; start[maxproc2]=c2+1;
		per[maxproc1]=max1; per[maxproc]=max2; per[maxproc2]=max3;
		break;
	      case 3: latency[z][heuristic][k]=newlatency;
		end[maxproc1]=c1;
		end[maxproc]=end[maxproc2]; end[maxproc2]=c2;
		start[maxproc1]=start[maxproc2]; start[maxproc2]=c1+1; start[maxproc]=c2+1;
		per[maxproc1]=max1; per[maxproc2]=max2; per[maxproc]=max3;
		break;
	      case 4:latency[z][heuristic][k]=newlatency;
		end[maxproc]=c1;
		end[maxproc1]=c2;
		start[maxproc]=start[maxproc2]; start[maxproc1]=c1+1; start[maxproc2]=c2+1;
		per[maxproc]=max1; per[maxproc1]=max2; per[maxproc2]=max3;
		break;
	      case 5:latency[z][heuristic][k]=newlatency;
		end[maxproc1]=end[maxproc2];
		end[maxproc]=c1;
		end[maxproc2]=c2;
		start[maxproc]=start[maxproc2]; start[maxproc2]=c1+1; start[maxproc1]=c2+1;
		per[maxproc]=max1; per[maxproc2]=max2; per[maxproc1]=max3;
		break;
		//default:
		//continue;
	      }
	    } // no possible pair c1,c2 was found
	    else {
	      kk=0;
	      printf("attention! no possible cut was found!\n");
	      
	    }
	    
	  }
	  else {
	    //only 1 proc is free, or interval < 3, so we do only 1 cut
	    //search for fastest comm
	     printf("\nonly 1 proc is free, or interval < 3, so we do only 1 cut\n");
	    // Find the proc with the biggest period that we can split (to put on maxproc)
	    maxproc2=-1; maxp=0;
	    for (j=0; j<p; j++)
	      if ((per[j]>maxp) && (end[j]-start[j]!=0) && (per[j]>fixp)){
		maxp=per[j]; maxproc2=j;
	      }
	    
	    if (MEGADEBUG) printf("maxproc2 to split: %d to put on maxproc %d\n",maxproc2,maxproc);

	    if ((maxproc!=-1)) {
	      bestcut=-1;
	      mind=MAXDOUBLE;
	      for (j=start[maxproc2]+1;j<=end[maxproc2];j++)
		if (d[k][j]<mind) {
		  bestcut=j;
		  mind=d[k][j];
		}
	      
	      if (bestcut!=-1) {
		//perform bestcut
		
		// Case 1: start..bestcut on maxproc2 and bestcut..end on maxproc
		pp[1]=(d[k][start[maxproc2]]+d[k][bestcut])/B[k];
		for(j=start[maxproc2]; j<bestcut; j++) pp[1]+=w[k][j]/s[k][maxproc2];
		pp[2]=(d[k][bestcut]+d[k][end[maxproc2]+1])/B[k];
		for(j=bestcut; j<=end[maxproc2]; j++) pp[2]+=w[k][j]/s[k][maxproc];
		if (pp[2]>pp[1]) pp[0]=pp[2]; else pp[0]=pp[1];
		llat1=latency[z][heuristic][k]-per[maxproc2]+pp[1]+pp[2]-(d[k][bestcut]/B[k]);
		// Case 2: start..bestcut on maxproc  and bestcut..end on maxproc2
		pp[4]=(d[k][start[maxproc2]]+d[k][bestcut])/B[k];
		for(j=start[maxproc2]; j<bestcut; j++) pp[4]+=w[k][j]/s[k][maxproc];
		pp[5]=(d[k][bestcut]+d[k][end[maxproc2]+1])/B[k];
		for(j=bestcut; j<=end[maxproc2]; j++) pp[5]+=w[k][j]/s[k][maxproc2];
		if (pp[4]>pp[5]) pp[3]=pp[4]; else pp[3]=pp[5];
		llat2=latency[z][heuristic][k]-per[maxproc2]+pp[4]+pp[5]-(d[k][bestcut]/B[k]);
		//	    if (k==3)
		// printf("l=%d -- pp: 0=%f, 1=%f, 2=%f, 3=%f, 4=%f, 5=%f\n",l,pp[0],pp[1],pp[2],pp[3],pp[4],pp[5]);
		 
		// Find out if this cut increases p max, and for which configuration latency is the best
		if (llat1<llat2) {
		  ll=bestcut; jj=1; max1=pp[1]; max2=pp[2];
		  if(pp[0]>maxp) maxp=pp[0];
		}
		else {
		  ll=bestcut; jj=2; max1=pp[4]; max2=pp[5];
		  if(pp[3]>maxp) maxp=pp[3];
		}
		if (DEBUG) printf("bestcut=%d, max1=%f, max2=%f\n",bestcut,max1,max2);
		//perform cut
		usedproc[maxproc]=1;
		if (jj==1) {
		  latency[z][heuristic][k]=llat1;
		  end[maxproc]=end[maxproc2];
		  end[maxproc2]=bestcut-1;
		  start[maxproc]=bestcut;
		  per[maxproc2]=max1; per[maxproc]=max2;
		}
		else {
		  latency[z][heuristic][k]=llat2;
		  end[maxproc2]=bestcut-1;
		  start[maxproc]=start[maxproc2];
		  start[maxproc2]=bestcut;
		  per[maxproc]=max1; per[maxproc2]=max2;
		  
		}
		
	      } else { // no possible cut was found
		kk=0;
	      }
	    
	    } else { //no more proc free
	      kk=0;
	    }
	  
	  }
	} else { //maxp <= fixp, we do not need to split anymore
	  kk=0;
	}
      } else { //no more proc free
	kk=0;
	printf("no more proc free\n");
      }
    }
	   

    for (j=0; j<p; j++)
      if (usedproc[j]) {
	if (DEBUG) fprintf(idf[k],"H2b: choosing proc %d for interval %d-%d: period %f\n",
		j, start[j], end[j], per[j]);
	printf("j=%d, p=%d, maxperiod=%f, per[j]=%f, latency=%f\n",j,p,maxperiod,per[j],latency[z][heuristic][k]);
		if (per[j] > maxperiod) maxperiod=per[j];
      }
    if (DEBUG) fprintf(idf[k],"H2b: maxperiod=%f\n\n", maxperiod);
    if (DEBUG) fprintf(idf[k],"H2b: latence=%f\n\n", latency[z][heuristic][k]);
    if (DEBUG) if (maxperiod>fixp) fprintf(idf[k],"H2b: FIXED PERIOD NOT REACHED!!\n\n");
    //fprintf(plot[heuristic], "%d %f\n", n, maxperiod);
    totperiod[z][heuristic][k]+=maxperiod;
    totlatency[z][heuristic][k]+=latency[z][heuristic][k];
   

    /************* Heuristic 3: Splitting bicritaire        ************/
    /*************              Binary search over latency  ************/
    /*************              increase (fraction Lopt/L)  ************/
    heuristic=3;
    printf("\n\n-----------------------------------------------------------------\n");
    printf("heuristic 3\n");
    printf("-----------------------------------------------------------------\n");

    kkmax=STARTDIC;
    
      int cutcomm[n+1], actend,actproc,nextproc,lll,jjj,proc;
      double lopt;
      double kkremain;
      double nexts,tmplatency,latence,globalmaxp; 
      double ratio1,ratio2,minratio;
      
      int oldStart[p], oldEnd[p],oldUsedproc[p]; //storing old values
      double oldMaxp, oldLatency, oldPer[p];
  
    if (MEGADEBUG) {
    printf("\nPLATFORM:\n");
    printf("nb stages: %d,n=%d, nb procs: %d, p=%d\n",nbstage[k],n,nbproc[k],p);
    printf("links:");
    for(j=0;j<n+1;j++)
      printf("\t%lf",d[k][j]);
    
    printf("\nstage time n=%d:",n);
    for(j=0;j<n;j++)
      printf("\t%lf",w[k][j]);
     
    printf("\nproc speed:");
    for(j=0;j<p;j++)
      printf("\t%lf",s[k][j]);
    printf("\n");
    }

    for(j=0; j<p; j++) {
      usedproc[j]=0;
      start[j]=0; end[j]=0; per[j]=0;
    }
    
  
    for (j=0; j<n+1; j++) cutcomm[j]=0;
    
    //find fastest proc (maxproc)
    for (j=0; j<p; j++)
      if ((s[k][j]>maxs)&&(usedproc[j]==0)) {
	maxproc=j; maxs=s[k][j];
      }
    
    // all stages on fastest proc
    start[maxproc]=0; end[maxproc]=n-1; usedproc[maxproc]=1;
    per[maxproc]=(d[k][0]+d[k][n])/B[k];
    for (i=0; i<n; i++) per[maxproc] += w[k][i]/maxs;
    if (MEGADEBUG) printf("fastest proc: %d, all stages matched on it, lopt=%f\n",maxproc,per[maxproc]);
    //compute Lopt
    lopt=per[maxproc];
    
    // kkmin=lopt;
    // kkmax=lopt+INCREASE;
    kkmin=0.0;
    kkmax=INCREASE;
    int solfound=0;
    int breaknow=0;
    while (kkmax-kkmin > PREC) {
      //kkk=(kkmax-kkmin)/2;
      kkk=kkmin+(kkmax-kkmin)/2;
      kkremain=kkk;
      if (MEGADEBUG) printf("-------------------------------\ndichotomy with kkk=%f, kkmax=%f; kkmin=%f\n", kkk, kkmax, kkmin);
      ll=1; // currently there is a solution
      lll=-1;
      // Initialising
      maxsta=0; // starting stage
      for(j=0; j<p; j++)
	if(j!=maxproc) {
	  usedproc[j]=0;
	  start[j]=-1; end[j]=-1; per[j]=-1;
	} else {
	  usedproc[j]=1;
	  start[j]=0; end[j]=n-1; per[j]=lopt;
	}
      globalmaxp=0;
       for (j=0; j<n+1; j++) cutcomm[j]=0;
      maxp=per[maxproc];
      tmplatency=maxp;
      
      


      //************************ start find solution ******************************************
  
      loop=0;
      while (kkremain>0) {
	loop++;
	nexts=-1;
	nextproc=-1;
	minratio=MAXDOUBLE;
	for (j=0; j<p; j++)
	  if ((s[k][j]>nexts)&&(usedproc[j]==0)) {
	    nextproc=j; nexts=s[k][j];
	  }
	
 if (MEGADEBUG)	printf("\nLOOP %d:\n-------\n",loop);
 if (MEGADEBUG)	printf("nextproc=%d\n",nextproc);
 if (MEGADEBUG)	printf("kkremain when entering the loop: %f, tmplatency %f, maxp %f\n",kkremain,tmplatency,maxp);
	//bestratio=-1;
	bestcut=-1;
	//	config=-1;

	//looking for link to cut where d[link] <= remaining latency increase and which max gain=delatL/deltaP
	for (ii=1;ii<n;ii++) {
	  if (MEGADEBUG) printf("\nii=%d\n",ii);
	  if ((d[k][ii]<=kkremain) && (cutcomm[ii]==0)) {
	    if (MEGADEBUG) printf("link ii=%d: %lf is smaller than kkremain=%f, cutcomm %d\n",ii,d[k][ii],kkremain,cutcomm[ii]);
	    //find proc on which interval with act link is matched
	    actend=MAXINT;
	    actproc=-1;
	    for (jj=0;jj<p;jj++) {
	      if (MEGADEBUG)  printf("link ii=%d, proc jj=%d, actend=%d, start[jj]=%d, end[jj]=%d\n", ii,jj,actend,start[jj],end[jj]);
	      if ((end[jj]>=ii) && (start[jj]<=ii)) {
		actend=end[jj];
		actproc=jj;
	      }
	    }
	    if (MEGADEBUG) printf("link ii=%d, actproc=%d, start=%d, end=%d\n", ii,actproc,start[actproc],end[actproc]);
	    
	    //splitting interval on actproc?
	    // Case 1: start..ii-1 on actproc  and ii..end on nextproc
	    pp[1]=(d[k][start[actproc]]+d[k][nextproc])/B[k];
	    for(j=start[actproc]; j<ii; j++) pp[1]+=w[k][j]/s[k][actproc];
	    pp[2]=(d[k][nextproc]+d[k][end[actproc]+1])/B[k];
	    for(j=ii; j<=end[actproc]; j++) pp[2]+=w[k][j]/s[k][nextproc];
	    if (pp[2]>pp[1]) pp[0]=pp[2]; else pp[0]=pp[1];
	    llat1=tmplatency-per[actproc]+pp[1]+pp[2]-(d[k][ii]/B[k]);
	    ratio1=(llat1-tmplatency)/(per[actproc]-pp[0]);
	    
	    // Case 2: start..ii-1 on nextproc  and ii..end on actproc
	    pp[4]=(d[k][start[actproc]]+d[k][ii])/B[k];
	    for(j=start[actproc]; j<ii; j++) pp[4]+=w[k][j]/s[k][nextproc];
	    pp[5]=(d[k][ii]+d[k][end[actproc]+1])/B[k];
	    for(j=ii; j<=end[actproc]; j++) pp[5]+=w[k][j]/s[k][actproc];
	    if (pp[4]>pp[5]) pp[3]=pp[4]; else pp[3]=pp[5];
	    llat2=tmplatency-per[actproc]+pp[4]+pp[5]-(d[k][ii]/B[k]);
	    ratio2=(llat2-tmplatency)/(per[actproc]-pp[3]);
	    
	    if (((ratio1<ratio2) || (ratio2<0))  && (ratio1<minratio) && (ratio1>0)) {
	      lll=ii; proc=actproc, jjj=1; minratio=ratio1; latence=llat1; max1=pp[1]; max2=pp[2]; maxp=pp[0];
	    } else if ((ratio2<minratio) && (ratio2>0)) {
	      lll=ii; proc=actproc, jjj=2; minratio=ratio2; latence=llat2; max1=pp[4]; max2=pp[5]; maxp=pp[3];
	    }
	     
	    
	   if (MEGADEBUG)  printf("act: link=%d with ratio1=%f, llat1=%f and pp1=%f, ratio2=%f, llat2=%f and pp2=%f\n",
		   ii,ratio1,llat1,pp[0],ratio2,llat2,pp[3]);
	  if (MEGADEBUG)   printf("act best: link=%d with ratio=%f, l=%f and maxp=%f, tmplatency=%f\n",lll,minratio,latence,maxp,tmplatency);
	  }
	}
	
	if (lll!=-1) {
	 if (MEGADEBUG)  printf("latence %f, tmplatency %f, resulting kkremain %f\n",latence,tmplatency,kkremain);
	  kkremain=kkremain-(latence-tmplatency);
	 if (MEGADEBUG)  printf("possible increase after split: %f, %d\nactproc %d, nextproc %d, cutcomm %d\n",kkremain,kkremain>0,proc,nextproc,lll);
	 if (MEGADEBUG)  printf("start actproc=%d, end=%d\n",start[proc],end[proc]);
	  // Perform the best cut
	  //printf("k=%d: cut with ll=%d\n",k,ll);
	  usedproc[nextproc]=1;
	  usedproc[actproc]=1;
	  cutcomm[lll]=1;
	  if (maxp>globalmaxp) globalmaxp=maxp;
	  if (jjj==1) {
	    tmplatency-=per[proc];
	    end[nextproc]=end[proc];
	    end[proc]=lll-1;
	    start[nextproc]=lll;
	    per[proc]=max1; per[nextproc]=max2;
	    //tmplatency=per[nextproc]+per[proc]-(d[k][lll]/B[k]);
	    tmplatency=latence;
	  }
	  else {
	    tmplatency-=per[proc];
	    start[nextproc]=start[proc];
	      end[nextproc]=lll-1;
	      start[proc]=lll;
	      per[nextproc]=max1; per[proc]=max2;
	      // tmplatency=per[nextproc]+per[proc]-(d[k][lll]/B[k]);
	      tmplatency=latence;
	  }
	  if (DEBUG) printf("splitting interval: actproc: %d, p=%f, next proc: %d, p=%f, l=%f\n",
			    proc,per[proc], nextproc,per[nextproc], tmplatency);
	  
	  for (j=0;j<p;j++) {
	    if (usedproc[j]!=0) {
	      //printf("proc %d owns stages %d-%d\n",j,start[j],end[j]);
	    }
	  }
	  lll=-1;
	  if(kkremain==0) {
	    printf("remain=0; leaving loop\n");
	    break;
	  }
	}
	else {//Nothing more we can do...
	  printf("no best place where to split\n");
	  kkremain=0;
	}
	if(loop==p-1) {
	  printf("all procs are affected, quitting while\n");
	  break;
	}
	 
      }
      //********************* end find solution *****************************


      //****************** solution found ?? yes: ll=1,  ********************
      //****************** no, fixp not reached: ll=0    ********************

      maxperiod=-1;
      for (j=0; j<p; j++)
	if (usedproc[j]) {
	  if (per[j] > maxperiod) maxperiod=per[j];
	}
      
      if (maxperiod>fixp) {
	ll=0;
	printf("this was not a valid solution, globalmaxp %f, fixp %f\n",maxperiod,fixp);
      } else {latency[z][heuristic][k]=tmplatency; maxp=maxperiod;}
      
      
      // Loop on the dichotomy
      if (ll){
	solfound=1;
	printf("sol found, kkmax=kkk, maxp=%f\n",maxp);
	kkmax=kkk;
	
	printf("\n***************************\nsol found=1; old sol = sol;\n**********************************\n");
	for (j=0; j<p; j++) {
	  oldStart[j]=start[j];
	  oldEnd[j]=end[j];
	  oldUsedproc[j]=usedproc[j];
	  oldPer[j]=per[j];
      	}
	oldMaxp=maxperiod; oldLatency=tmplatency;
      } else {
	printf("no sol found, kkmin=kkk\n");
	kkmin=kkk;
	printf("\n***************************\nif sol found, sol=old sol; solfound=%d\n***********************************\n",solfound);
	if(solfound==1) {
	  printf("\n in solfound==1 \n");
	  for (j=0; j<p; j++) {
	    start[j]=oldStart[j];
	    end[j]=oldEnd[j];
	    usedproc[j]=oldUsedproc[j];
	    per[j]=oldPer[j];
	  }
	  printf("breaking?\n");
	  breaknow=1;
	  //break;
	}
	printf("oldMaxp %f, oldLatency %f\n",oldMaxp, oldLatency);
	maxperiod=oldMaxp; latency[z][heuristic][k]=oldLatency;
      }
      if(breaknow==1) {
	printf("has to break now\n");
	break;
      }
       printf("did not break?\n");
    }
    
    printf("solfound %d, breaknow %d, maxp %f, lat %f\n",solfound, breaknow, maxperiod, latency[z][heuristic][k]);

    if (kkmax>=STARTDIC) {
      printf("INCREASE DIC START\n");
    }
    
    if (DEBUG) fprintf(idf[k],"H3: maxincrease=%f\n\n", kkmax);
    //fprintf(plot[heuristic], "%d %f\n", n, maxperiod);
    //totperiod[heuristic][k]+=kkmax;
      
    for (j=0; j<p; j++)
      if (usedproc[j]) {
	if (DEBUG) fprintf(idf[k],"H3: choosing proc %d for interval %d-%d: period %f\n",
		j, start[j], end[j], per[j]);
	printf("j=%d, p=%d, maxperiod=%f, per[j]=%f, latence=%f\n",j,p,maxperiod,per[j],latency[z][heuristic][k]);
		if (per[j] > maxperiod) maxperiod=per[j];
      }
    if (DEBUG) fprintf(idf[k],"H3: maxperiod=%f\n", maxperiod);
    if (DEBUG) fprintf(idf[k],"H3: latence=%f\n\n", latency[z][heuristic][k]);
    if (DEBUG) if (maxperiod>fixp) fprintf(idf[k],"H3: FIXED PERIOD NOT REACHED!!\n\n");
    if (DEBUG) if (solfound!=1) fprintf(idf[k],"H3: NO SOL FOUND!! maxperiod=%f, lat=%f\n\n",maxperiod,latency[z][heuristic][k]);
    //fprintf(plot[heuristic], "%d %f\n", n, maxperiod);
    totperiod[z][heuristic][k]+=maxperiod;
          totlatency[z][heuristic][k]+=latency[z][heuristic][k];



	  /*************************   part II: min period with fixed latency *******************************/
 
	  
/* 	  Heuristic 4: Splitting to diminuate period */
/* 	               while latency is not exceeded */
/* 	  uses Splitting heuristic by Anne Benoit */
    heuristic=4;
    //  int start[p], end[p];
    //   double per[p], pp[6];
    //  double tmplatency;
    printf("\nheuristic 4 starts\n\n");
    for(j=0; j<p; j++) {
      usedproc[j]=0;
      per[j]=-1;
      start[j]=0; end[j]=0;per[j]=0;
    }
    maxperiod=-1; kk=1;

    while (kk) {
      // find fastest proc
      maxproc=-1; maxs=-1;
      
      for (j=0; j<p; j++)
	if ((s[k][j]>maxs)&&(usedproc[j]==0)) {
	  maxproc=j; maxs=s[k][j];
	}
      //printf("fastest proc: %d, speed %f\n", maxproc, maxs);
      
      if (maxperiod==-1) {
	// First time in the loop: start[p]=0 and end[p]=n-1;
	start[maxproc]=0; end[maxproc]=n-1; usedproc[maxproc]=1;
	// compute the corresponding period
	per[maxproc] = (d[k][0]+d[k][n])/B[k];
	for (i=0; i<n; i++) per[maxproc] += w[k][i]/maxs;
	maxperiod=0;
/* 	latence corresponds to the period of the fastest proc as it is the only chosen proc */
	latency[z][heuristic][k]=per[maxproc]; 
      }
      else if (maxproc!=-1) {
	// Find the proc with the biggest period that we can split (to put on maxproc)
	maxproc2=-1; maxp=0;
	for (j=0; j<p; j++)
	  if ((per[j]>maxp) && (end[j]-start[j]!=0)){
	    maxp=per[j]; maxproc2=j;
	  }
	if (maxproc2!=-1) {
	  //printf("Spliting maxproc2=%d\n", maxproc2);
	  // Find l where to cut the interval to min the max of the 2 resultant periods
	  ll=-1;
	  for (l=start[maxproc2]; l<end[maxproc2]; l++) {
	    // Case 1: start..l on maxproc2 and l..end on maxproc
	    pp[1]=(d[k][start[maxproc2]]+d[k][l+1])/B[k];
	    for(j=start[maxproc2]; j<=l; j++) pp[1]+=w[k][j]/s[k][maxproc2];
	    pp[2]=(d[k][l+1]+d[k][end[maxproc2]+1])/B[k];
	    for(j=l+1; j<=end[maxproc2]; j++) pp[2]+=w[k][j]/s[k][maxproc];
	    if (pp[2]>pp[1]) pp[0]=pp[2]; else pp[0]=pp[1];
	    
	    // Case 2: start..l on maxproc  and l..end on maxproc2
	    pp[4]=(d[k][start[maxproc2]]+d[k][l+1])/B[k];
	    for(j=start[maxproc2]; j<=l; j++) pp[4]+=w[k][j]/s[k][maxproc];
	    pp[5]=(d[k][l+1]+d[k][end[maxproc2]+1])/B[k];
	    for(j=l+1; j<=end[maxproc2]; j++) pp[5]+=w[k][j]/s[k][maxproc2];
	    if (pp[4]>pp[5]) pp[3]=pp[4]; else pp[3]=pp[5];
	    
	    //	    if (k==3)
	    // printf("l=%d -- pp: 0=%f, 1=%f, 2=%f, 3=%f, 4=%f, 5=%f\n",l,pp[0],pp[1],pp[2],pp[3],pp[4],pp[5]);

	    // Find out if this l is better, and for which configuration
	    if ((pp[0] < maxp)&&(pp[0]<pp[3])) {
	      ll=l; jj=1; max1=pp[1]; max2=pp[2]; maxp=pp[0];
	    }
	    else if (pp[3]<maxp) {
	      ll=l; jj=2; max1=pp[4]; max2=pp[5]; maxp=pp[3];
	    }
	  }
	  if (ll!=-1) {      // fehler: per[maxproc]
	    tmplatency=latency[z][heuristic][k]-per[maxproc2]+max1+max2-(d[k][ll+1]/B[k]);
	    if (tmplatency<=fixl) {
	      // Perform the best cut
	      //printf("k=%d: cut with ll=%d\n",k,ll);
	      usedproc[maxproc]=1;
	      if (jj==1) {
		latency[z][heuristic][k]-=per[maxproc2];
		end[maxproc]=end[maxproc2];
		end[maxproc2]=ll;
		start[maxproc]=ll+1;
		per[maxproc2]=max1; per[maxproc]=max2;
		latency[z][heuristic][k]+=per[maxproc2]+per[maxproc]-(d[k][ll+1]/B[k]);
	      }
	      else {
		latency[z][heuristic][k]-=per[maxproc2];
		start[maxproc]=start[maxproc2];
		end[maxproc]=ll;
		start[maxproc2]=ll+1;
		per[maxproc]=max1; per[maxproc2]=max2;
		latency[z][heuristic][k]+=per[maxproc]+per[maxproc2]-(d[k][ll+1]/B[k]);
	      }
	    }
	    else {//Nothing more we can do...
	      //printf("fixed latency is reached\n");
	      kk=0;
	    }
	  }
	  else {//Nothing more we can do...
	    //printf("no best place where to split\n");
	    kk=0;
	  }
	}
	else {//Nothing more we can do...
	  //printf("no interval where to split\n");
	  kk=0;
	}
      }
      else  {//Nothing more we can do...
	//printf("no more free proc\n");
	kk=0;
      }
    }

    for (j=0; j<p; j++)
      if (usedproc[j]) {
	if (DEBUG) fprintf(idf[k],"H4: choosing proc %d for interval %d-%d: period %f\n",
		j, start[j], end[j], per[j]);
	printf("j=%d, p=%d, maxperiod=%f, per[j]=%f\n",j,p,maxperiod,per[j]);
		if (per[j] > maxperiod) maxperiod=per[j];
      }
    if (DEBUG) fprintf(idf[k],"H4: maxperiod=%f\n\n", maxperiod);
    if (DEBUG) fprintf(idf[k],"H4: latence=%f\n\n", latency[z][heuristic][k]);
    if (DEBUG) if (maxperiod>fixp) fprintf(idf[k],"H4: FIXED PERIOD NOT REACHED!!\n\n");
    //fprintf(plot[heuristic], "%d %f\n", n, maxperiod);
    totperiod[z][heuristic][k]+=maxperiod;
    totlatency[z][heuristic][k]+=latency[z][heuristic][k];




    /************* Heuristic 5: Splitting bicritaire                 ************/
    /*************              min period with fixed latency.       ************/
    /*************              Permitted latency increase is knwon  ************/
    /*************              increase = L - Lopt                  ************/
      heuristic=5;
      //heuristic=1;
      printf("\n\n-----------------------------------------------------------------\n");
      printf("heuristic 5\n");
      printf("-----------------------------------------------------------------\n");
      
      //  kkmax=STARTDIC;
      
      if (MEGADEBUG) {
	printf("\nPLATFORM:\n");
	printf("nb stages: %d,n=%d, nb procs: %d, p=%d\n",nbstage[k],n,nbproc[k],p);
	printf("links:");
	for(j=0;j<n+1;j++)
	  printf("\t%lf",d[k][j]);
	
	printf("\nstage time n=%d:",n);
	for(j=0;j<n;j++)
	  printf("\t%lf",w[k][j]);
	
	printf("\nproc speed:");
	for(j=0;j<p;j++)
	  printf("\t%lf",s[k][j]);
	printf("\n");
      }
      
      for(j=0; j<p; j++) {
	usedproc[j]=0;
	start[j]=0; end[j]=0; per[j]=0;
      }
      
      
      for (j=0; j<n+1; j++) cutcomm[j]=0;
      
      //find fastest proc (maxproc)
      for (j=0; j<p; j++)
	if ((s[k][j]>maxs)&&(usedproc[j]==0)) {
	  maxproc=j; maxs=s[k][j];
	}
      
      // all stages on fastest proc
      start[maxproc]=0; end[maxproc]=n-1; usedproc[maxproc]=1;
      per[maxproc]=(d[k][0]+d[k][n])/B[k];
      for (i=0; i<n; i++) per[maxproc] += w[k][i]/maxs;
      
      latency[z][heuristic][k]=per[maxproc]; 
      
      if (MEGADEBUG) printf("fastest proc: %d, all stages matched on it, lopt=%f\n",maxproc,per[maxproc]);
      //compute Lopt
      lopt=per[maxproc];
        double p_lopt;
      p_lopt=lopt;

      //compute allowed increase of the latency
      kkremain=fixl-lopt;
      
      if (MEGADEBUG) printf("kkremain: %f\n",kkremain);
      
      maxp=per[maxproc];
      tmplatency=maxp;
      
      
      
      
      //************************ start find solution ******************************************
      
      loop=0;
      while (kkremain>0) {
	loop++;
	nexts=-1;
	nextproc=-1;
	minratio=MAXDOUBLE;
	for (j=0; j<p; j++)
	  if ((s[k][j]>nexts)&&(usedproc[j]==0)) {
	    nextproc=j; nexts=s[k][j];
	  }
	
	if (MEGADEBUG)	printf("\nLOOP %d:\n-------\n",loop);
	if (MEGADEBUG)	printf("nextproc=%d\n",nextproc);
	if (MEGADEBUG)	printf("kkremain when entering the loop: %f, tmplatency %f, maxp %f\n",kkremain,tmplatency,maxp);
	//bestratio=-1;
	bestcut=-1;
	//	config=-1;
	
	for (ii=1;ii<n;ii++) {
	  if (MEGADEBUG) printf("\nii=%d\n",ii);
	  if ((d[k][ii]<=kkremain) && (cutcomm[ii]==0)) {
	    if (MEGADEBUG) printf("link ii=%d: %lf is smaller than kkremain=%f, cutcomm %d\n",ii,d[k][ii],kkremain,cutcomm[ii]);
	    //find proc on which interval with act link is matched
	    actend=MAXINT;
	    actproc=-1;
	    for (jj=0;jj<p;jj++) {
	      if (MEGADEBUG)  printf("link ii=%d, proc jj=%d, actend=%d, start[jj]=%d, end[jj]=%d\n", ii,jj,actend,start[jj],end[jj]);
	      if ((end[jj]>=ii) && (start[jj]<=ii)) {
		actend=end[jj];
		actproc=jj;
	      }
	    }
	    if (MEGADEBUG) printf("link ii=%d, actproc=%d, start=%d, end=%d\n", ii,actproc,start[actproc],end[actproc]);
	    
	    //splitting interval on actproc?
	    // Case 1: start..ii-1 on actproc  and ii..end on nextproc
	    pp[1]=(d[k][start[actproc]]+d[k][nextproc])/B[k];
	    for(j=start[actproc]; j<ii; j++) pp[1]+=w[k][j]/s[k][actproc];
	    pp[2]=(d[k][nextproc]+d[k][end[actproc]+1])/B[k];
	    for(j=ii; j<=end[actproc]; j++) pp[2]+=w[k][j]/s[k][nextproc];
	    if (pp[2]>pp[1]) pp[0]=pp[2]; else pp[0]=pp[1];
	    llat1=tmplatency-per[actproc]+pp[1]+pp[2]-(d[k][ii]/B[k]);
	    ratio1=(llat1-tmplatency)/(per[actproc]-pp[0]);
	    
	    // Case 2: start..ii-1 on nextproc  and ii..end on actproc
	    pp[4]=(d[k][start[actproc]]+d[k][ii])/B[k];
	    for(j=start[actproc]; j<ii; j++) pp[4]+=w[k][j]/s[k][nextproc];
	    pp[5]=(d[k][ii]+d[k][end[actproc]+1])/B[k];
	    for(j=ii; j<=end[actproc]; j++) pp[5]+=w[k][j]/s[k][actproc];
	    if (pp[4]>pp[5]) pp[3]=pp[4]; else pp[3]=pp[5];
	    llat2=tmplatency-per[actproc]+pp[4]+pp[5]-(d[k][ii]/B[k]);
	    ratio2=(llat2-tmplatency)/(per[actproc]-pp[3]);
	    
	    if (((ratio1<ratio2) || (ratio2<0))  && (ratio1<minratio) && (ratio1>0)) {
	      lll=ii; proc=actproc, jjj=1; minratio=ratio1; latence=llat1; max1=pp[1]; max2=pp[2]; maxp=pp[0];
	    } else if ((ratio2<minratio) && (ratio2>0)) {
	      lll=ii; proc=actproc, jjj=2; minratio=ratio2; latence=llat2; max1=pp[4]; max2=pp[5]; maxp=pp[3];
	    }
	    
	    
	    if (MEGADEBUG)  printf("act: link=%d with ratio1=%f, llat1=%f and pp1=%f, ratio2=%f, llat2=%f and pp2=%f\n",
				   ii,ratio1,llat1,pp[0],ratio2,llat2,pp[3]);
	    if (MEGADEBUG)   printf("act best: link=%d with ratio=%f, l=%f and maxp=%f, tmplatency=%f\n",lll,minratio,latence,maxp,tmplatency);
	  }
	}
	
	if (lll!=-1) {
	  if (MEGADEBUG)  printf("latence %f, tmplatency %f, resulting kkremain %f\n",latence,tmplatency,kkremain);
	  kkremain=kkremain-(latence-tmplatency);
	  if (MEGADEBUG)  printf("possible increase after split: %f, %d\nactproc %d, nextproc %d, cutcomm %d\n",kkremain,kkremain>0,proc,nextproc,lll);
	  if (MEGADEBUG)  printf("start actproc=%d, end=%d\n",start[proc],end[proc]);
	  // Perform the best cut
	  //printf("k=%d: cut with ll=%d\n",k,ll);
	  usedproc[nextproc]=1;
	  usedproc[actproc]=1;
	  cutcomm[lll]=1;
	  if (maxp>globalmaxp) globalmaxp=maxp;
	  if (jjj==1) {
	    tmplatency-=per[proc];
	    end[nextproc]=end[proc];
	    end[proc]=lll-1;
	    start[nextproc]=lll;
	    per[proc]=max1; per[nextproc]=max2;
	    //tmplatency=per[nextproc]+per[proc]-(d[k][lll]/B[k]);
	    tmplatency=latence;
	  }
	  else {
	    tmplatency-=per[proc];
	    start[nextproc]=start[proc];
	    end[nextproc]=lll-1;
	    start[proc]=lll;
	    per[nextproc]=max1; per[proc]=max2;
	    // tmplatency=per[nextproc]+per[proc]-(d[k][lll]/B[k]);
	    tmplatency=latence;
	  }
	  if (MEGADEBUG) printf("splitting interval: actproc: %d, p=%f, next proc: %d, p=%f, l=%f\n",
			    proc,per[proc], nextproc,per[nextproc], tmplatency);
	  
	  for (j=0;j<p;j++) {
	    if (usedproc[j]!=0) {
	      printf("proc %d owns stages %d-%d\n",j,start[j],end[j]);
	    }
	  }
	  lll=-1;
	
	} else {
	  break;
	}


      }
      //********************* end find solution *****************************
      
      
      //****************** solution found ?? yes: ll=1,  ********************
      //****************** no, fixp not reached: ll=0    ********************
      
      maxperiod=-1;
      for (j=0; j<p; j++)
	if (usedproc[j]) {
	  if (per[j] > maxperiod) maxperiod=per[j];
	}
    
      if (tmplatency>fixl) {
	ll=0;
	printf("this was not a valid solution, tmplatency %f, fixl %f\n",tmplatency,fixl);
     	/* no solution found, when splitting, hence all stages stay on fastest proc */
	//	latency[z][heuristic][k]=lopt; maxp=p_lopt;
   
      for(j=0; j<p; j++) {
	usedproc[j]=0;
	start[j]=0; end[j]=0; per[j]=0;
      }
      
      
      for (j=0; j<n+1; j++) cutcomm[j]=0;
      
      //find fastest proc (maxproc)
      for (j=0; j<p; j++)
	if ((s[k][j]>maxs)&&(usedproc[j]==0)) {
	  maxproc=j; maxs=s[k][j];
	}
      
      // all stages on fastest proc
      start[maxproc]=0; end[maxproc]=n-1; usedproc[maxproc]=1;
      per[maxproc]=(d[k][0]+d[k][n])/B[k];
      for (i=0; i<n; i++) per[maxproc] += w[k][i]/maxs;	
      latency[z][heuristic][k]=per[maxproc]; 

      } else {latency[z][heuristic][k]=tmplatency; maxp=maxperiod;}
      
    
 
 
    
      if (MEGADEBUG ) printf("maxp %f, lat %f\n", maxperiod, latency[z][heuristic][k]);
    
    
      if (DEBUG) fprintf(idf[k],"H5: maxincrease=%f,kkremain=%f\n\n", fixl-lopt-kkremain,kkremain);
      if (DEBUG) fprintf(idf[k],"H5: lopt=%f, fixl=%f\n", lopt,fixl);
      //fprintf(plot[heuristic], "%d %f\n", n, maxperiod);
      //totperiod[heuristic][k]+=kkmax;
      
      for (j=0; j<p; j++)
	if (usedproc[j]) {
	  if (DEBUG) fprintf(idf[k],"H5: choosing proc %d for interval %d-%d: period %f\n",
			     j, start[j], end[j], per[j]);
	  if (MEGADEBUG )printf("j=%d, p=%d, maxperiod=%f, per[j]=%f, latence=%f\n",j,p,maxperiod,per[j],latency[z][heuristic][k]);
	  if (per[j] > maxperiod) maxperiod=per[j];
	}
      
      if (DEBUG) fprintf(idf[k],"H5: maxperiod=%f\n", maxperiod);
      if (DEBUG) fprintf(idf[k],"H5: latence=%f\n\n", latency[z][heuristic][k]);
      if (DEBUG) if (maxperiod>fixp) fprintf(idf[k],"H5: FIXED PERIOD NOT REACHED!!\n\n");
      //fprintf(plot[heuristic], "%d %f\n", n, maxperiod);
      totperiod[z][heuristic][k]+=maxperiod;
      totlatency[z][heuristic][k]+=latency[z][heuristic][k];
      
      fprintf(stderr,"\nbefore close\n\n");
    
      if (DEBUG) fclose(idf[k]);
      }
    }
    //printf("nach for uber k=nbapp, tree=%d\n\n",tree); 
  }
  //printf("nach for uber tree=nbtree\n\n");
  
  // Printing the plots
  for (i=0; i<nbheur; i++) {
    fprintf(stderr,"das soll einer verstehen\n");
   
   
    // sprintf(lat_fname,"applis/LatLB-%.2d",i+1);
    fprintf(stderr,"file name printed\n");
    FILE *periodFile;
    FILE *latencyFile;
    // FILE *appliFile;
    FILE *doubleObjFile;
    double lowerboundl,minl;
    double lowerboundp,minp;

    //  appliFile=fopen(appli_fname,"w");
    //plot[i] = fopen (fname,"w");
    fprintf(stderr,"file opened\n");
    for (k=0; k<nbapp; k++){
      sprintf(per_fname,"plots/PerLB-%.2d_%.2d",i+1,nbstage[k]);
      sprintf(lat_fname,"plots/LatLB-%.2d_%.2d",i+1,nbstage[k]);
      
      periodFile=fopen(per_fname,"w");
      latencyFile=fopen(lat_fname,"w");
      
      minp=totperiod[0][i][k]/nbtree;
      minl=totlatency[0][i][k]/nbtree;
	
      for(kk=0;kk<tr;kk++){
	if(minp>(totperiod[kk][i][k]/nbtree))
	  minp=totperiod[kk][i][k]/nbtree;


	if(minl>(totlatency[kk][i][k]/nbtree))
	  minl=totlatency[kk][i][k]/nbtree;

      }


      lowerboundl=0;
      lowerboundl=0;

      if (i<4) {
	printf("H%d:\n",i);
	printf("minp=%f, lbp=%f\n",minp,lowerboundp );
       
	for(kk=0;kk<tr;kk++) 
	  if(minp>(fixedperiod[kk][k]))
	    lowerboundp=fixedperiod[kk][k];
      }
      
	
      if (i>3) {
	for(kk=0;kk<tr;kk++)
	  if(minl>(fixedlatency[kk][k]))
	    lowerboundl=fixedlatency[kk][k];
      }

      //printf("totperiod[%d][%d]=%lf, nbtree=%d\n",i,k,totperiod[i][k],nbtree);
      sprintf(fname,"plots/Heuristic-%.2d_%.2d",i+1,nbstage[k]);
      doubleObjFile=fopen(fname,"a");

      //fprintf(plot[i], "%d %f\n", k+1, totperiod[i][k]/nbtree); 
      for (z=0;z<tr;z++) {
/* 	fprintf(periodFile, "%d %f %f\n", k+1, totperiod[z][i][k]/nbtree,fixedperiod[z][k]); */
/* 	fprintf(latencyFile, "%d %f %f\n", k+1, totlatency[z][i][k]/nbtree,fixedlatency[z][k]); */
	//  if( (k==4) || (k==9) || (k==19) || (k==39)) {
	fprintf(doubleObjFile, "%d %f %f %f %f\n", nbstage[k], totperiod[z][i][k]/nbtree, totlatency[z][i][k]/nbtree, fixedperiod[z][k], fixedlatency[z][k]);
	
	// }
	
      }
      if (i<4)
	fprintf(periodFile,"%d %f\n",0,lowerboundp);
      if(i>3)
	fprintf(latencyFile,"%d %f\n",0,lowerboundl);
      
      fclose(doubleObjFile);  
    }
    
    fprintf(stderr,"all is printed\n");
    fclose(periodFile);
    fclose(latencyFile);
   
    fprintf(stderr,"and closed again\n");
    //fclose(plot[i]);
  
  }
 /*  for(i=0;i<tr;i++){     */
/*       for(k=0;k<nbapp;k++){   */
/* 	printf("%f ",fixedperiod[i][k]); */
/*       } */
/*       printf("\n"); */
/*     } */
   
  return 0;
}