import java.util.*; import java.util.concurrent.*; import java.util.concurrent.atomic.*; import java.util.concurrent.locks.*; import easyIO.*; class Oppgave4{ int [][] a; long [] radSum; int n, antT; CyclicBarrier sync; public static void main (String [] args) { if ( args.length < 1 ) { System.out.println("use: >java Oppg4 "); } else { new Oppgave4().doTest(args); } } // end main long sumRad (int [] a ) { long sum =0; for (int j = 0 ; j < a.length; j++) sum += a[j]; return sum; } // end sumRad void doTest (String [] args) { // initiate n = Integer.parseInt(args[0]); antT = Runtime.getRuntime().availableProcessors(); sync = new CyclicBarrier(antT); a = new int[n][n]; radSum = new long[n]; Random r = new Random(1337); long tid ; int k; // ***************** Sekvensiell RadSort ****************** int sum =0; // -- init a[][] ----- for (int i =0; i< a.length;i++){ for (int j =0; j < n; j++) { a[i][j] = r.nextInt(n);// random fill } } // end initarray tid = System.nanoTime(); // start timer for (int i =0; i< a.length;i++){ radSum[i] = sumRad(a[i]); } // end initarray quicksortSek( a, radSum,0,n-1); double tt = (System.nanoTime()-tid)/1000000.0; testRS(radSum, "Sekv "); System.out.println("n: "+n+", num cores:"+ antT ); System.out.println(" Sequental sorting in : "+ tt+ " ms. " ); // ***************** Parallell RadSort ****************** for (int i =0; i< a.length;i++){ radSum[i] = 0; } // end initarray // a) regn ut radsum i parallell tid = System.nanoTime(); // start timer Thread [ ] tr = new Thread[antT]; for (int i =0; i< antT;i++){ (tr[i] = new Thread(new Arbeider(i))).start();; } // end initarray try{ for (int i =0; i< antT;i++) tr[i].join(); }catch(Exception e) {return;} // sorter i parallell // finn level = parallellisering i toppen av treet int level = 0; while ( (antT >> level) > 0 ) level++; quicksortPara( a, radSum, 0,n-1, level) ; double ttt = (System.nanoTime()-tid)/1000000.0; testRS(radSum, "Para "); System.out.println("n: "+n+", num cores:"+ antT + ", level:"+level ); System.out.println(" Parallel sorting in: "+ ttt+ " ms., speedup: " +Format.align (tt/ttt, 5,2) ); } // end doTest void testRS(long [] rs, String s) { for (int i =1; i < rs.length; i++) if (rs[i-1] > rs[i]) { System.out.println("ERROR:" + s+ ", at i ="+i); } } // end testRS // Parallell Kvikksort uten insertSort void quicksortPara(int[][] a, long [] rs, int left, int right, int level) { int piv = partition (a,rs, left, right); // del i to int piv2 = piv-1; long pivotVal = rs[piv]; while (piv2 > left && rs[piv2] == pivotVal) { piv2--; // skip like elementer i midten } if (level-- > 0){ Thread t1= new Thread (new Arbeider2(a,rs,left, piv2, level)), t2 =new Thread (new Arbeider2(a,rs,piv+1, right, level)); t1.start(); t2.start(); try{ t1.join(); t2.join(); }catch (Exception e) {return;} } else { if ( piv2-left > 0) quicksortSek(a,rs, left, piv2); if ( right-piv > 0) quicksortSek(a, rs, piv + 1, right); } } // end quicksortSek // sekvensiell Kvikksort uten insertSort void quicksortSek(int[][] a, long [] rs, int left, int right) { int piv = partition (a,rs, left, right); // del i to int piv2 = piv-1; long pivotVal = rs[piv]; while (piv2 > left && rs[piv2] == pivotVal) { piv2--; // skip like elementer i midten } if ( piv2-left > 0) quicksortSek(a,rs, left, piv2); if ( right-piv > 0) quicksortSek(a, rs, piv + 1, right); } // end quicksortSek // del opp a[] i to: smaa og storre int partition (int [][]a,long[] rs, int left, int right) { long pivVal = rs[(left + right) / 2]; int index = left; // plasser pivot-element helt til høyre swap(a,rs, (left + right) / 2, right); for (int i = left; i < right; i++) { if (rs[i] <= pivVal) { swap(a, rs, i, index); index++; } } swap(a, rs,index, right); // sett pivot tilbake return index; } // end partition void swap(int [][] a, long [] rs, int l, int r) { int []temp1 = a[l]; long temp2 = rs[l]; a[l] = a[r]; rs[l] = rs[r]; a[r] = temp1; rs[r] = temp2; } // end swap class Arbeider2 implements Runnable { int[][] a; long [] rs; int left, right, level; Arbeider2 (int[][] a, long [] rs, int left, int right, int level) { this.a =a; this.rs = rs; this.left = left; this.right = right; this.level =level; } public void run( ) { // System.out.println("Arbeider2, level:"+level); quicksortPara(a, rs, left, right, level); } // end run } // end indre klasse Arbeider2 class Arbeider implements Runnable { int ind; // lokale data og metoder B int part, left,right; Arbeider ( int in) { ind = in; part = n/antT; left = ind*part; if (ind == antT-1) right = n; else right = left + part; } public void run( ) { // kalles når tråden er startet for (int i = left; i < right; i++) radSum[i] = sumRad(a[i]); } // end run } // end indre klasse Arbeider } // end Oppg.4