MSort


1   import EDU.oswego.cs.dl.util.concurrent.*;
2   import java.util.Random  ;
3   
4   /**
5    * Sample sort program adapted from a demo in
6    * <A HREF="http://supertech.lcs.mit.edu/cilk/"> Cilk</A> and
7    * <A HREF="http://www.cs.utexas.edu/users/hood/"> Hood</A>.
8    * 
9    **/
10  
11  class MSort {
12  
13    public static void main (String  [] args) {
14      try {
15        int n = 262144;
16        int p = 2;
17    
18        try {
19          p = Integer.parseInt(args[0]);
20          n = Integer.parseInt(args[1]);
21        }
22  
23        catch (Exception   e) {
24          System.out.println("Usage: java MSort <threads> <array size>");
25          return;
26        }
27  
28        int[] A = new int[n];
29  
30        // Fill in array A with random values.
31        Random   rng = new Random  ();
32        for (int i = 0; i < n; i++) A[i] = rng.nextInt();
33  
34        int[] workSpace = new int[n];
35  
36        FJTaskRunnerGroup g = new FJTaskRunnerGroup(p);
37        Sorter t = new Sorter(A, 0, workSpace, 0, n);
38        g.invoke(t);
39        g.stats();
40  
41        //      checkSorted(A, n);
42  
43      }
44      catch (InterruptedException   ex) {}
45    }
46  
47    static void checkSorted (int[] A, int n)  {
48      for (int i = 0; i < n - 1; i++) {
49        if (A[i] > A[i+1]) {
50          throw new Error  ("Unsorted at " + i + ": " + A[i] + " / " + A[i+1]);
51        }
52      }
53    }
54  
55    /* Threshold values */
56  
57    // Cutoff for when to do sequential versus parallel merges 
58    static final int MERGE_SIZE = 2048;
59  
60    // Cutoff for when to do sequential quicksort versus parallel mergesort
61    static final int QUICK_SIZE = 2048;
62  
63    // Cutoff for when to use insertion-sort instead of quicksort
64    static final int INSERTION_SIZE = 20;
65  
66  
67  
68    static class Sorter extends FJTask {
69      final int[] A;          // Input array.
70      final int aLo;          // offset into the part of array we deal with
71      final int[] W;          // workspace for merge
72      final int wLo;
73      final int n;            // Number of elements in (sub)arrays.
74  
75  
76      Sorter (int[] A, int aLo, int[] W, int wLo, int n) {
77        this.A = A;
78        this.aLo = aLo;
79        this.W = W;
80        this.wLo = wLo;
81        this.n = n;
82      }
83  
84      public void run()  {
85  
86        /*
87          Algorithm:
88          
89          IF array size is small, just use a sequential quicksort
90          
91          Otherwise:
92            Break array in half.
93            For each half,
94               break the half in half (i.e., quarters),
95                   sort the quarters
96                   merge them together
97            Finally, merge together the two halves.
98        */
99  
100       if (n <= QUICK_SIZE) {
101         qs();
102       }
103       else {
104 
105         int q = n/4;
106         
107         coInvoke(new Seq(new Par(new Sorter(A, aLo, 
108                                             W, wLo, 
109                                             q),
110                                  
111                                  new Sorter(A, aLo+q, 
112                                             W, wLo+q, 
113                                             q)
114                                  ),
115                          
116                          new Merger(A, aLo,   q, 
117                                     A, aLo+q, q,
118                                     W, wLo)
119                          ),
120 
121                  new Seq(new Par(new Sorter(A, aLo+q*2, 
122                                             W, wLo+q*2, 
123                                             q),
124                                  
125                                  new Sorter(A, aLo+q*3,
126                                             W, wLo+q*3,
127                                             n-q*3)
128                                  ),
129                          
130                          new Merger(A, aLo+q*2, q, 
131                                     A, aLo+q*3, n-q*3,
132                                     W, wLo+q*2)
133                          )
134                  );
135 
136         invoke(new Merger(W, wLo,     q*2, 
137                           W, wLo+q*2, n-q*2,
138                           A, aLo));
139 
140       }
141     }
142 
143 
144     /** Relay to quicksort within sync method to ensure memory barriers **/
145     synchronized void qs() {
146       quickSort(aLo, aLo+n-1);
147     }
148       
149     /** A standard sequential quicksort **/
150     void quickSort(int lo, int hi) {
151 
152       // If under threshold, use insertion sort
153       if (hi-lo+1l <= INSERTION_SIZE) {
154         for (int i = lo + 1; i <= hi; i++) {
155           int t = A[i];
156           int j = i - 1;
157           while (j >= lo && A[j] > t) {
158             A[j+1] = A[j];
159             --j;
160           }
161           A[j+1] = t;
162         }
163         return;
164       }
165 
166 
167       //  Use median-of-three(lo, mid, hi) to pick a partition. 
168       //  Also swap them into relative order while we are at it.
169       
170       int mid = (lo + hi) / 2;
171       
172       if (A[lo] > A[mid]) {
173         int t = A[lo]; A[lo] = A[mid]; A[mid] = t;
174       }
175       if (A[mid]> A[hi]) {
176         int t = A[mid]; A[mid] = A[hi]; A[hi] = t;
177 
178         if (A[lo]> A[mid]) {
179           t = A[lo]; A[lo] = A[mid]; A[mid] = t;
180         }
181 
182       }
183       
184       int left = lo+1;           // start one past lo since already handled lo
185       int right = hi-1;          // similarly
186       
187       int partition = A[mid];
188       
189       for (;;) {
190         
191         while (A[right] > partition) 
192           --right;
193         
194         while (left < right && A[left] <= partition) 
195           ++left;
196         
197         if (left < right) {
198           int t = A[left]; A[left] = A[right]; A[right] = t;
199           --right;
200         }
201         else break;
202         
203       }
204       
205       quickSort(lo,    left);
206       quickSort(left+1, hi);
207       
208     }
209 
210   }
211 
212 
213   static class Merger extends FJTask {
214 
215     final int[] A;           // First sorted array.
216     final int aLo;           // first index of A
217     final int aSize;         // number of elements
218 
219     final int[] B;           // Second sorted array.
220     final int bLo;
221     final int bSize;         
222 
223     final int[] out;         // Output array.
224     final int outLo;
225 
226     Merger (int[] A,   int aLo, int aSize,
227             int[] B,   int bLo, int bSize,
228             int[] out, int outLo) {
229 
230       this.out = out;
231       this.outLo = outLo;
232 
233       // A must be largest of the two for split. Might as well swap now.
234       if (aSize >= bSize) {
235         this.A = A;    this.aLo = aLo;    this.aSize = aSize;
236         this.B = B;    this.bLo = bLo;    this.bSize = bSize;
237       }
238       else {
239         this.A = B;    this.aLo = bLo;    this.aSize = bSize;
240         this.B = A;    this.bLo = aLo;    this.bSize = aSize;
241       }
242     }
243 
244     public void run() {
245 
246       /*
247         Algorithm:
248         If the arrays are small, then just sequentially merge.
249         
250         Otherwise:
251           Split A in half.
252           Find the greatest point in B less than the beginning
253              of the second half of A.
254           In parallel:
255                merge the left half of A with elements of B up to split point
256                merge the right half of A with elements of B past split point
257       */
258 
259       if (aSize <= MERGE_SIZE) {
260         merge();
261       }
262       else {
263 
264         int aHalf = aSize / 2;
265         int bSplit = findSplit(A[aLo + aHalf]);
266         
267         coInvoke(new Merger(A,   aLo, aHalf, 
268                             B,   bLo, bSplit, 
269                             out, outLo), 
270                  new Merger(A,   aLo+aHalf, aSize-aHalf,
271                             B,   bLo+bSplit, bSize-bSplit,
272                             out, outLo+aHalf+bSplit));
273       }
274     }
275 
276     /** find greatest point in B less than value. return 0-based offset **/
277     synchronized int findSplit(int value) {
278       int low = 0;
279       int high = bSize;
280       while (low < high) {
281         int middle = low + (high - low) / 2;
282         if (value <= B[bLo+middle])
283           high = middle;
284         else
285           low = middle + 1;
286       }
287       return high;
288     }
289 
290     /** A standard sequential merge **/
291     synchronized void merge() {
292       int a = aLo;
293       int aFence = aLo+aSize;
294       int b = bLo;
295       int bFence = bLo+bSize;
296       int k = outLo;
297 
298       while (a < aFence && b < bFence) {
299         if (A[a] < B[b]) 
300           out[k++] = A[a++];
301         else 
302           out[k++] = B[b++];
303       }
304 
305       while (a < aFence) out[k++] = A[a++];
306       while (b < bFence) out[k++] = B[b++];
307     }
308   }
309 
310 }
311
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags