User Tools

Site Tools


ppsolutions

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
ppsolutions [2009/02/26 17:19] moritzppsolutions [2009/05/31 22:06] (current) – Links to eth changed to eth:eth moritz
Line 1: Line 1:
 ====== Solutions for assignments in Parallele Programmierung. ====== ====== Solutions for assignments in Parallele Programmierung. ======
-See [[ETH]]. [[ParallelPrefix]]+See [[eth:ETH]]. [[ParallelPrefix]]
 ===== Assignment 1 ===== ===== 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> </code>
  
ppsolutions.1235665191.txt.gz · Last modified: 2009/02/26 17:19 by moritz

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki