Differences

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

--- ppsolutions [2009/02/26 10:28] – corect title 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]].
+See [[eth:ETH]]. [[ParallelPrefix]]
 ===== Assignment 1 =====
@@ Line 97: / Line 97: @@
         }
     }
+}
+</code>
+Bounded buffer for assignment 3:
+<code java>
+package hw03;
+public class BoundedBuffer implements Buffer {
+    private static final int SIZE = 5;
+    private final int[] buffer = new int[SIZE];
+    private int pos = -1;
+    public int read() throws BufferEmptyException {
+        return get();
+    }
+    public void write(int i) throws BufferFullException {
+        set(i);
+    }
+    private synchronized int get() {
+        while (pos == -1) {
+            try {
+                this.wait();
+            } catch (InterruptedException e) {
+                e.printStackTrace();
+            }
+        }
+        // the first element
+        int v = buffer[0];
+        System.arraycopy(buffer, 1, buffer, 0, pos);
+        pos = pos - 1;
+        this.notifyAll();
+        return v;
+    }
+    private synchronized void set(int v) {
+        System.out.println(pos);
+        while (pos >= SIZE - 1) {
+            try {
+                this.wait();
+            } catch (InterruptedException e) {
+                e.printStackTrace();
+            }
+        }
+        pos = pos + 1;
+        buffer[pos] = v;
+        this.notifyAll();
+    }
+}
+</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>