import java.util.*; import java.util.concurrent.*; import java.util.concurrent.locks.*; import java.util.concurrent.atomic.*; import easyIO.*; class Oppgave7{ // Administration, common routines and output int [] a; int numThreads; int n; int numIter; String fil; Out ut; /** sort double-array a to find median */ double median(double a[]) { int i,k; double t; for (k = 1 ; k < a.length; k++) { t = a[k] ; i = k; while ((a[i-1] ) > t ) { a[i] = a[i-1]; if (--i == 0) break; } a[i] = t; } // end k return a[a.length/2]; } // end median synchronized void println(String s) { ut = new Out(fil, true); System.out.println(s); ut.outln(s); ut.close(); } public static void main (String [] args) { if ( args.length < 3 ) { System.out.println("use: >java Oblig4 "); } else { new Oppgave7().doTest(args); } } // end main void doTest (String [] args) { // initiate n = Integer.parseInt(args[0]); numIter = Integer.parseInt(args[1]); fil = args[2]; Random r = new Random(1337); double [] seqTime = new double [numIter]; double [] seqTime2 = new double [numIter]; double [] parTime = new double [numIter]; double [] parTime2 = new double [numIter]; double [] qckTime = new double [numIter]; for (int j = 0; j < numIter; j++) { long t ; // ***************** Parallel Radix ****************** a= new int[n]; // oekende lengde med oekende numThreadsint[] b = new int [n]; for (int i =0; i< a.length;i++){ a[i] = r.nextInt(a.length); // random fill >=0 } t = System.nanoTime(); // start timer new ParaRadix().sort(a); t = (System.nanoTime()-t); parTime[j] = t/1000000.0; testA(a,"ParallellRadix "); System.out.println("Run no: "+j+", num cores:"+ numThreads + ", numThreads:" + numThreads); System.out.println(" Parallel Radix sorting in : "+ parTime[j]+ " millisec. " ); // ***************** Parallel Atomic Radix ****************** a= new int[n]; // oekende lengde med oekende numThreadsint[] b = new int [n]; for (int i =0; i< a.length;i++){ a[i] = r.nextInt(a.length); // random fill >=0 } t = System.nanoTime(); // start timer new ParaAtomicRadix().paraRadix(a); parTime2[j] = (System.nanoTime()-t)/1000000.0; testA(a,"ParallellAtomic "); // System.out.println("Run no: "+j+", num cores:"+ numThreads + ", numThreads:" + numThreads); System.out.println(" Parallel Atomic sort in : "+ parTime2[j]+ " millisec. " ); // ***************** Sequential Radix ****************** for (int i =0; i< a.length;i++){ a[i] = r.nextInt(a.length); // random fill >=0 } t = System.nanoTime(); new SeqRadix().radix2(a); seqTime[j] =(System.nanoTime()-t)/1000000.0; testA(a,"Sequential Radix "); System.out.println(" Sequential sorting in : "+ seqTime[j]+ " millisec."); // ***************** AtomicSequential Radix ****************** for (int i =0; i< a.length;i++){ a[i] = r.nextInt(a.length); // random fill >=0 } t = System.nanoTime(); new SeqAtomicRadix().radix2(a); seqTime2[j] =(System.nanoTime()-t)/1000000.0; testA(a,"AtomicSequential"); System.out.println(" Sequential atomic in : "+ seqTime2[j]+ " millisec."); // *************** compare with Arrays.sort (quicksort)**************** for (int i =0; i< a.length;i++){ a[i] = r.nextInt(a.length); // random fill >=0 } t = System.nanoTime(); Arrays.sort(a); qckTime[j] =(System.nanoTime()-t)/1000000.0; testA(a,"Arrays.sort "); System.out.println(" Quicksort sequential in : "+ qckTime[j]+ " millisec."); } // end for j println( "\nn= "+Format.align(n,10)+ "\nMedian Sequential Radix time:"+Format.align(median(seqTime),10,3)+ "\nMedian Seq Atomic time:" + Format.align(median(seqTime2),10,3)+ "\nMedian Quick seq time:" + Format.align(median(qckTime),10,3)+ "\nMedian Radix parallel time:" + Format.align(median(parTime),10,3)+ "\nMedian Atomic parallel time:" + Format.align(median(parTime2),10,3)+ ",\n Speedup Atom :"+ Format.align(median(seqTime2)/median(parTime2),7,3)+ ",\n Speedup Radix:"+ Format.align(median(seqTime)/median(parTime),7,3)+ "\n Speedup: SeqQuicksort/ParaRadix:"+ Format.align(median(qckTime)/median(parTime),7,3)+ "\n Speedup:SeqQuicksort/AtomicParaRadix:"+ Format.align(median(qckTime)/median(parTime2),7,3)); } // doTest void testA (int [] a, String s) { for (int i = 1; i < a.length; i++) { if (a[i-1] > a[i] ) { System.out.println ("FEIL::" + s + ", a["+(i-1) + "]: "+ a[i-1]+" > a["+i+"]:"+a[i]); In n = new In(); String l = n.inLine(); return; } // } // end for i }// end testA } // end class Oblig4 // **************************************** ParaRadix ****************************************** class ParaRadix{ int [] a,b; int n ; int numThreads; int[]localMax ; CyclicBarrier sync; int allCount[][]; void sort(int [] a) { this.a =a; n = a.length; b = new int [a.length]; numThreads = Runtime.getRuntime().availableProcessors(); localMax = new int[numThreads]; Thread[] tt = new Thread[numThreads]; sync = new CyclicBarrier(numThreads); allCount= new int[numThreads][]; // start Radix threads for (int i = 0; i< numThreads; i++){ tt[i]= new Thread(new Para(i)); tt[i].start(); } for (int i = 0; i< numThreads; i++){ try{ tt[i].join(); }catch (Exception e) { return;} } } class Para implements Runnable{ int ind; Para(int i) { ind =i;} // constructor int [] localCount; int myMax ; int left, right; int bit1, bit2; void findLocalMax(){ int num= (a.length/numThreads); // antall elementer per traad left = num*ind; myMax = a[left]; right= left +num; if (ind == numThreads -1) right = a.length; for (int i = left+1; i < right; i++) { if (a[i] > myMax) myMax = a[i]; } localMax[ind] =myMax; } // end FindLocalMax void paraRadix(int [] a, int [] b) { // 2 digit radixSort: a[] int numBit = 2, n =a.length; while (myMax >= (1<> shift) & mask]++; } allCount[ind] = localCount; try{ // start all threads ---------------- Sync 2 and 4 ------------------- sync.await(); } catch (Exception e) {return;} localCount = new int[localCount.length]; // c) Add up in 'count' - accumulated values in NEW localCount for (int val = 0; val < mask+1; val++) { for (int i = 0; i < ind; i++) { sumC += allCount[i][val]; } localCount [val] = sumC; for (int i = ind; i < numThreads; i++) { sumC += allCount[i][val]; } } // no need to sync between c) and d) - only local variables // d) move numbers in sorted order a to b for (int i = left; i < right; i++) { b[localCount[(a[i]>>shift) & mask]++] = a[i]; } }// end paraRadixSort public void run() { // Her er det som kjoeres i parallell: findLocalMax(); try{ // start all treads ----------- Sync 1 ---------------- sync.await(); } catch (Exception e) {return;} // all threads calculate the same max for (int i = 0; i < numThreads; i++) if (myMax < localMax[i]) myMax = localMax[i]; paraRadix(a,b); } // end run } // end class Para } // end class ParaRadix // **************************************** SeqRadix ****************************************** class SeqRadix{ static final int INSERT_LIM = 100, ONE_BIT = 8000; void radix2(int [] a) { if ( a.length < INSERT_LIM ) innstikkSort(a); else { // 2 digit radixSort: a[] int max = a[0], numBit = 2, n =a.length; // a) finn max verdi i a[] for (int i = 1 ; i < n ; i++) if (a[i] > max) max = a[i]; while (max >= (1<> shift) & mask]++; } // c) Add up in 'count' - accumulated values for (int i = 0; i <= mask; i++) { j = count[i]; count[i] = acumVal; acumVal += j; } // d) move numbers in sorted order a to b for (int i = 0; i < n; i++) { b[count[(a[i]>>shift) & mask]++] = a[i]; } }// end radixSort void innstikkSort(int a[]) {//,int l, int r) int i, t, r = a.length-1; for (int k = 0 ; k < r ; k++){ t = a[k+1]; i = k; while (i >= 0 && a[i] > t) { a[i+1] = a[i]; i--;} a[i+1] = t; } // end for k } // end innstikk } // end class SeqRadix // ********************************* ParaAtomicRadix ************************** class ParaAtomicRadix{ CyclicBarrier trSync ; int [] a, b; int numThreads; ReentrantLock lock = new ReentrantLock(); AtomicIntegerArray count; int n,bit1,bit2; int numIter,numBit =2; int allMax =0; Thread[] tr ; void updateMax(int m) { lock.lock(); try{ if (m > allMax) allMax = m; }finally { lock.unlock();} } // end updateMax ParaAtomicRadix() { numThreads = Runtime.getRuntime().availableProcessors(); trSync = new CyclicBarrier(numThreads); } // end constructor void paraRadix(int[] a) { // called from main-tread this.a = a; this.n = a.length; b = new int[a.length]; tr = new Thread[numThreads]; //printArr(a, "Input a:", 0, a.length); for (int i = 0; i< numThreads; i++) { (tr[i] = new Arbeider(i)).start(); } //--- completed whan return for (int i = 0; i< numThreads; i++) try{ tr[i].join(); }catch (Exception e) { return;} //printArr(a, "Etter siffer2 a:", 0, a.length); } // end paraRadix class Arbeider extends Thread { int left, right, myMax,ind; Arbeider(int in) { ind = in; int num= (a.length/numThreads); // antall elementer per traad left = num*ind; right= left+num; if (ind == numThreads-1) right = a.length; } // end konstruktor Arbeider void paraAtomicRadixSort ( int [] a, int [] b, int maskLen, int shift){ // called from run int acumVal = 0, j, n = a.length; int mask = (1<> shift) & mask); } try{ // sync all treads ------------- Sync 3 & 7-------------------- trSync.await(); } catch (Exception e) {return;} // System.out.println("c ind:"+ind); // c) Add up in 'count' - accumulated values - done in main-tr if (ind == 0) { // printAtomic(count, "MaskLen:"+maskLen+", count Post:", 0, count.length() ); // Add up in 'count' - accumulated values digit 2 for (int i = 0; i <= mask; i++) { j = count.get(i); count.set(i,acumVal); acumVal += j; } } // thread 0 // System.out.println("D ind:"+ind); try{ // sync all treads ------------- Sync 4 %8 -------------------- trSync.await(); } catch (Exception e) {return;} // System.out.println("E ind:"+ind); // d) move numbers in sorted order a to b if (ind == 0) { for (int i = 0; i < a.length; i++) { b[count.getAndIncrement((a[i]>>shift) & mask)] = a[i]; } } // System.out.println("F ind:"+ind); }// end atomicRadixSort public void run() { myMax = a[left]; for (int i = left+1; i < right; i++) { if (a[i] > myMax) myMax = a[i]; } updateMax(myMax); // loop a) try{ // sync all treads ------------- Sync 1 -------------------- trSync.await(); } catch (Exception e) {return;} if (ind == 0) { while (allMax >= (1L< max) max = a[i]; while (max >= (1<> shift) & mask); } // c) Add up in 'count' - accumulated values for (int i = 0; i <= mask; i++) { j = count.get(i); count.set(i,acumVal); acumVal += j; } // d) move numbers in sorted order a to b for (int i = 0; i < n; i++) { b[count.getAndIncrement((a[i]>>shift) & mask)] = a[i]; } }// end atomicRadixSort } // end class SeqAtomicRadix