import java.util.*;
import java.util.concurrent.*;
import easyIO.*;

class Prefetch{
	static CyclicBarrier vent,ferdig ;
	static int [] a;
	static int antTr?der;
	static int antKjerner;
	static int[]lokalSum ;
	static int aLen, step;
	static int numIter;
	volatile boolean stop = false;
	static Prefetch p = new Prefetch();
	static String res;
	Random r;

	void intitier(int [] param, int step) {
		if ( vent == null) {
			 antKjerner = Runtime.getRuntime().availableProcessors();
			 antTr?der = antKjerner;
			 vent   = new CyclicBarrier(antTr?der+1); //+1, ogs? main
			 ferdig = new CyclicBarrier(antTr?der+1); //+1, ogs? main
			 lokalSum = new int [antTr?der];
			 a = param;
			 r = new Random(123456);

             // start threads
             for (int i = 0; i< antTr?der; i++)
		 		 new Thread(new Para(i, step)).start();
		 }
	} // end initier


	public static void main (String [] args) {
		if ( args.length != 4)	{
			System.out.println("use: >java Prefetch <length of array> <step 1,-1,9, -9> <num iterations> > <resultatfil>");
	    } else {
		    aLen = Integer.parseInt(args[0]);
		    step = Integer.parseInt(args[1]);
		    numIter = Integer.parseInt(args[2]);
		    res = args[3];
		    p = new Prefetch();
		    p.utf?rTest(aLen, step);

	    }
	 } // end main

	 void println(String s) {
		 System.out.println(s);
		 Out r = new Out(res,true);
		 r.outln(s);
		 r.close();
	 }// end println


    int SumSeq( int [] a, int step) {
		 int sum = 0;
		 int index  =0;

		 for (int i=0;i < a.length; i++){
			//index = Math.abs((index+step)%a.length ); // fast steg
			index = Math.abs((index+r.nextInt(step+1))%a.length) ;  // tilfeldig valg av steg: 0,..,step
			sum += a[index];
		  }
	      return sum;
	  }// end SumSeq



	void  utf?rTest (int n, int step) {
	    a= new int[n]; // ?kende lengde med ?kende antTr?der

	    int totalSum = -1;

		Random r = new Random(1337);
		for (int i =0; i< a.length;i++)
		   a[i] = Math.max(r.nextInt(10),0); // random fill >=0

		 double [] seqTime = new double [numIter];
		 double [] parTime = new double [numIter];


	     for (int j = 0; j < numIter; j++) {

			long t ;
			t = System.nanoTime();       // start klokke

			 // try findin max numIter times

			 totalSum = SumPara(a,step);

			 t = (System.nanoTime()-t);
			  parTime[j] = t/1000000.0;
             System.out.println("\n-Tester prefetch-mekanismen ved ? steppe i (1,-1,...) i en stor array");
			 System.out.println("Kj?ring:"+j+", ant kjerner:"+ antKjerner + ", antTr?der:"
			                      + antTr?der+", step:"+step);
			 System.out.println("Sum verdi parallell   i a:"+totalSum +
			 ", paa: "+  parTime[j]+ " ms. " );

			 // sammenlign med sekvensiell utf?ring av finnSum
			 t = System.nanoTime();

			 totalSum = SumSeq(a,step);

			 t = (System.nanoTime()-t);
			 seqTime[j] =t/1000000.0;

		     System.out.println("Sum verdi sekvensiell i a:"+totalSum +", paa: "+
		                 seqTime[j]+ " ms."+", step:"+step);
        } // end for j
        insertSort(seqTime, 0, numIter-1);
        insertSort(parTime, 0, numIter-1);

        println("\nMedian sequential time:"+seqTime[seqTime.length/2]+
        "ms., median parallel time:"+ parTime[seqTime.length/2]
        + "ms.,\n step:"+step+", Speedup:"+ Format.align(seqTime[seqTime.length/2 ]/parTime[parTime.length/2],6,2)
         +", n = "+n);

        stop = true;
        try{ // make all threads terminate
			 	vent.await();
	 	} catch (Exception e) {}

	 } // utf?r

	 int SumPara (int [] a, int step) {
		   // gj?r synkronisering for tr?dene
	 	   intitier (a, step);
	 	   int totalSum = 0;

	 	   try{ // start all treads
	 			vent.await();
	 		} catch (Exception e) {return 0;}

	 		try{ // wait for all treads to complete
	 			ferdig.await();
	 		} catch (Exception e) {return 0;}

	 		// finn den st?rste max fra alle tr?dene
	 		for (int i=0;i < antTr?der;i++)
	 		   totalSum += lokalSum[i];

	 	    return totalSum;

	} // end finnSum


	 class Para implements Runnable{
		   int ind;
		   int step;
		   Para(int i, int step) { ind =i; this.step = step; r = new Random(123+i); }// konstruktor
		   Random r ;

		  void FindMinSum(int ind, int step){
			 int ant= a.length/antTr?der;   // antall elementer per tr?d
			 int num = ant;
			 if (ind == antTr?der-1) num = ant + (a.length % antTr?der) ;
			 int start =  ant*ind;
			 int end    = start+num;
			 int index  =0;

			 int sum = 0;

			 for (int i=start;i < end; i++){
				index = Math.abs((index+step)%a.length) ;           // fast steg
				//index = Math.abs((index+r.nextInt(step+1))%a.length) ;  // tilfeldig valg av steg 0,..,step
				sum += a[index];
			  }

			  lokalSum[ind] =sum;  // lev?r svar

	      } // end FindLocalSum

	       public void run() { // Her er det som kj?res i parallell:

			   while (! stop) {

				   try {  // wait on all other threads + main
					   vent.await();
	         	   } catch (Exception e) {return;}

	         	   if (! stop) {

					  FindMinSum(ind,step);

					   try {  // wait on all other threads + main
						   ferdig.await();
					   } catch (Exception e) {return;}

				   }// end stop thread

			   } // while
			} // end run
     } // end class Para

	 /** sort double-array a to find median */
	 void insertSort(double a[],int left, int right) {
				int i,k;
				double t;

				for (k = left+1 ; k <= right; k++) {
					t = a[k] ;
					i = k;

					while ((a[i-1] ) > t ) {
						 a[i] = a[i-1];
						 if (--i == left) break;
					}
					a[i] = t;
				} // end k
	 } // end insertSort
}// END class Parallell