Differences

This shows you the differences between two versions of the page.

--- ppsolutions [2009/03/06 14:24] – Add partly solution for assignment 3. moritz
+++ ppsolutions [2009/05/31 20:06] (current) – Links to eth changed to eth:eth moritz
@@ Line 1: / Line 1: @@
 ====== Solutions for assignments in Parallele Programmierung. ======
-See [[ETH]]. [[ParallelPrefix]]
+See [[eth:ETH]]. [[ParallelPrefix]]
 ===== Assignment 1 =====
@@ Line 150: / Line 150: @@
 }
 </code>
+===== Assignment 4 =====
+<code java>
+package hw04;
+public class MTMergeSort {
+    /**
+     * A sorter runnable. This will create as many sub threads as passed by the
+     * threads parameter. If it is an odd number, one half will be sorted using
+     * a thread, the other will be sorted by this object.
+     *
+     * @author Moritz Hoffmann
+     *
+     */
+    private final class Sorter implements Runnable {
+        private final int l, r;
+        private final Thread left, right;
+        private final int middle;
+        private final SeqMergeSort sorter;
+        Sorter(int left, int right, int threads, SeqMergeSort sorter) {
+            this.sorter = sorter;
+            threads = threads - 1;
+            l = left;
+            r = right;
+            middle = (l + r) / 2;
+            if (threads > 1) {
+                // construct both left and right threads
+                final int thalf = threads / 2;
+                this.left = new Thread(new Sorter(l, middle, threads - thalf,
+                    sorter));
+                this.right = new Thread(
+                    new Sorter(middle + 1, r, thalf, sorter));
+            } else if (threads == 1) {
+                // construct only left thread, right part will be sorted by
+                // this.
+                this.left = new Thread(new Sorter(l, middle, 0, sorter));
+                this.right = null;
+            } else {
+                this.left = this.right = null;
+            }
+        }
+        public void run() {
+            // System.out.println("Running " + Thread.currentThread().getId());
+            if (this.left == null && this.right == null) {
+                // sort here
+                sorter.mergesort(l, r);
+            } else if (this.left != null && this.right == null) {
+                // let left sort in background
+                this.left.start();
+                // sort here
+                sorter.mergesort(middle + 1, r);
+                try {
+                    // wait for left to finish.
+                    this.left.join();
+                } catch (InterruptedException e) {
+                    e.printStackTrace();
+                }
+                // merge the results together.
+                sorter.merge(l, middle, middle + 1, r);
+            } else {
+                // sort both left and right in a separate thread.
+                left.start();
+                right.start();
+                try {
+                    left.join();
+                } catch (InterruptedException e) {
+                    e.printStackTrace();
+                }
+                try {
+                    right.join();
+                } catch (InterruptedException e) {
+                    e.printStackTrace();
+                }
+                // merge the results together.
+                sorter.merge(l, middle, middle + 1, r);
+            }
+            // System.out.println("Returning " +
+            // Thread.currentThread().getId());
+        }
+    }
+    private final int[] to_sort;
+    private final int total_sort_threads;
+    public MTMergeSort(int[] to_sort, int no_threads) {
+        this.to_sort = to_sort;
+        this.total_sort_threads = no_threads;
+    }
+    public void sort() {
+        // Your code here to perform multithreaded merge sort
+        // You should use SeqMergeSort.sort() and SeqMergeSort.merge()
+        // for sorting and merging, respectively.
+        // total number of sorting threads = this.total_sort_threads
+        // The shared sorter instance.
+        SeqMergeSort mergesort = new SeqMergeSort(to_sort);
+        // construct a new sorter instance.
+        Sorter s = new Sorter(0, to_sort.length - 1, total_sort_threads,
+            mergesort);
+        // call it synchronously as it can use the main thread as well.
+        long t = System.nanoTime();
+        s.run();
+        System.out.println((double) (System.nanoTime() - t) / 1000000 + "[ms]");
+    }
+}
+</code>