Robust/src/Benchmarks/oooJava/mergesort/BMergeSort4.java

   1 /**\r
   2  * 4-way split version of merge sort\r
   3  */\r
   4 \r
   5 public class MergeSort4 extends MergeSort {\r
   6   \r
   7   public  boolean validationTest;\r
   8 \r
   9   public static void main(String[] args) {\r
  10     int problemSize = 4194304;\r
  11     int parallelBranch=32;\r
  12     \r
  13     MergeSort4 sort = new MergeSort4();\r
  14     \r
  15     if (args.length > 0) {\r
  16       problemSize = Integer.parseInt(args[0]);\r
  17     }\r
  18     if (args.length > 1) {\r
  19       parallelBranch = Integer.parseInt(args[1]);\r
  20     }\r
  21     if (args.length > 2){\r
  22      sort.validationTest=true;\r
  23     }\r
  24     sort.run(problemSize,parallelBranch);\r
  25   }\r
  26 \r
  27   public MergeSort4() {\r
  28     super();\r
  29     validationTest=false;\r
  30   }\r
  31 \r
  32   public void runWorkAndTest() {\r
  33     sese run{\r
  34       long startT=System.currentTimeMillis();\r
  35       int output[]=sort(input, 0, input.length);\r
  36       long endT=System.currentTimeMillis();\r
  37       System.out.println("running time="+(endT-startT));\r
  38     }\r
  39     if(validationTest){\r
  40       sese test{\r
  41         checkSorted(output);\r
  42       }\r
  43     }\r
  44   }\r
  45 \r
  46   public int[] serializedSort(int A[], int low, int high) {\r
  47 \r
  48     int length = high - low;\r
  49 \r
  50     if (length <= QUICK_SIZE) {\r
  51       int[] R = new int[length];\r
  52       int max = R.length;\r
  53       int j = low;\r
  54       for (int i = 0; i < max; i++) {\r
  55           R[i] = A[j++];\r
  56       }\r
  57       quickSort(R, 0, R.length - 1);\r
  58       return R;\r
  59     } else {\r
  60 \r
  61       int q = length / 4;\r
  62       int idxs0 = q + low;\r
  63       int idxs1 = (2 * q) + low;\r
  64       int idxs2 = (3 * q) + low;\r
  65 \r
  66       int[] A_quarters0 = serializedSort(A, low, idxs0);\r
  67       int[] A_quarters1 = serializedSort(A, idxs0, idxs1);\r
  68       int[] A_quarters2 = serializedSort(A, idxs1, idxs2);\r
  69       int[] A_quarters3 = serializedSort(A, idxs2, idxs2 + q);\r
  70 \r
  71       int[] R = new int[high - low];\r
  72 \r
  73       merge(A_quarters0, A_quarters1, A_quarters2, A_quarters3, R);\r
  74       return R;\r
  75     }\r
  76   }\r
  77 \r
  78   public int[] sort(int A[], int low, int high) {\r
  79     \r
  80     int length=high-low;\r
  81     \r
  82     if (length <= SERIALIZED_CUT_OFF) {\r
  83       return serializedSort(A, low, high);\r
  84     } else {\r
  85       if (length <= QUICK_SIZE) {\r
  86         int[] R = new int[length];\r
  87         int max = R.length;\r
  88         int j = low;\r
  89         for (int i = 0; i < max; i++) {\r
  90             R[i] = A[j++];\r
  91         }\r
  92         quickSort(R, 0, R.length-1);\r
  93         return R;\r
  94       } else {\r
  95         \r
  96         int q=length/4;\r
  97         int idxs0 = q+low;\r
  98         int idxs1 = (2 * q)+low;\r
  99         int idxs2 = (3 * q)+low;\r
 100 \r
 101         sese p1{\r
 102           int[] A_quarters0 = sort(A, low, idxs0);\r
 103         }\r
 104         sese p2{\r
 105           int[] A_quarters1 = sort(A, idxs0, idxs1);\r
 106         }\r
 107         sese p3{\r
 108           int[] A_quarters2 = sort(A, idxs1, idxs2);\r
 109         }\r
 110         // don't spawn off sese for last one...\r
 111         int[] A_quarters3 = sort(A, idxs2, idxs2+q);\r
 112 \r
 113         int[] R = new int[high - low];\r
 114 \r
 115         merge(A_quarters0, A_quarters1, A_quarters2, A_quarters3, R);\r
 116         return R;\r
 117       }\r
 118     }\r
 119   }\r
 120 \r
 121   public static void merge(int[] a1, int[] a2, int[] a3, int[] a4, int[] a) {\r
 122     int i1 = 0;\r
 123     int i2 = 0;\r
 124     int i3 = 0;\r
 125     int i4 = 0;\r
 126     int alength = a.length;\r
 127     int v1 = a1[0];\r
 128     int v2 = a2[0];\r
 129     int v3 = a3[0];\r
 130     int v4 = a4[0];\r
 131     int v1m = a1.length;\r
 132     int v2m = a2.length;\r
 133     int v3m = a3.length;\r
 134     int v4m = a4.length;\r
 135     for (int i = 0; i < alength; i++) {\r
 136       if (v1 < v2) {\r
 137         if (v1 < v3) {\r
 138           if (v1 < v4) {\r
 139             a[i] = v1;\r
 140             // v1 smallest\r
 141             if (i1 < v1m) {\r
 142               v1 = a1[i1++];\r
 143             } else {\r
 144               v1 = 2147483647;\r
 145             }\r
 146           } else {\r
 147             a[i] = v4;\r
 148             // v4 smalles\r
 149             if (i4 < v4m) {\r
 150               v4 = a4[i4++];\r
 151             } else {\r
 152               v4 = 2147483647;\r
 153             }\r
 154           }\r
 155         } else {\r
 156           if (v3 < v4) {\r
 157             a[i] = v3;\r
 158             // v3 smallest\r
 159             if (i3 < v3m) {\r
 160               v3 = a3[i3++];\r
 161             } else {\r
 162               v3 = 2147483647;\r
 163             }\r
 164           } else {\r
 165             a[i] = v4;\r
 166             // v4 smallest\r
 167             if (i4 < v4m) {\r
 168               v4 = a4[i4++];\r
 169             } else {\r
 170               v4 = 2147483647;\r
 171             }\r
 172           }\r
 173         }\r
 174       } else {\r
 175         if (v2 < v3) {\r
 176           if (v2 < v4) {\r
 177             a[i] = v2;\r
 178             // v2 smallest\r
 179             if (i2 < v2m) {\r
 180               v2 = a2[i2++];\r
 181             } else {\r
 182               v2 = 2147483647;\r
 183             }\r
 184           } else {\r
 185             a[i] = v4;\r
 186             // v4 smallest\r
 187             if (i4 < v4m) {\r
 188               v4 = a4[i4++];\r
 189             } else {\r
 190               v4 = 2147483647;\r
 191             }\r
 192           }\r
 193         } else {\r
 194           if (v3 < v4) {\r
 195             a[i] = v3;\r
 196             // v3 smallest\r
 197             if (i3 < v3m) {\r
 198               v3 = a3[i3++];\r
 199             } else {\r
 200               v3 = 2147483647;\r
 201             }\r
 202           } else {\r
 203             a[i] = v4;\r
 204             // v4 smallest\r
 205             if (i4 < v4m) {\r
 206               v4 = a4[i4++];\r
 207             } else {\r
 208               v4 = 2147483647;\r
 209             }\r
 210           }\r
 211         }\r
 212       }\r
 213     }\r
 214   }\r
 215 \r
 216 }\r