CSEP 524, Spring 2015: Homework 3
Due: Tuesday, April 21 by 5:00 pm.
Please use the dropbox linked from the CSEP 524 web page to submit your homework online. Any common format like text, pdf, doc/docx is fine.
- Read MapReduce: Simplified Data Processing on Large Clusters,
by Jeffrey Dean and Sanjay Ghemawat.
Write a short review and summary of the paper (between a half and a full page, using a reasonable font size). What do you think of MapReduce as a way to structure
parallel computations? What are some of the pros and cons? Please also propose one or more discussion questions.
- Look over the course final project web page, and propose a final project topic.
List some of the resources that you might use (e.g., papers, tutorials, software, etc). Also let me know your presentation date preference, and any conflicts you have.
- Write Peril-L psuedocode for a non-bitonic (i.e., merging sorted lists, not bitonic lists) Parallel Merging based sort. You may assume a function that computes a nodes'
partner at each stage, or, for extra credit you
may write the Peril-L code to compute partners based on some network (e.g., the Batcher Odd-Even Mergesort network - see wikipedia).
Your Peril-L code may assume that P (the number of processors) is a power of 2, and that N (the total data to sort) is evenly divisible by P. You may also assume that you
have a fast local sorting routine (call it localSortInPlace(array, size)) that sorts an array that is local to the node (or that has been made local via
localize(), as described in Chapter 4 of your text). You may choose the datatype for the elements to be sorted.
- As discussed in class, if you prefer you may instead write this in a "real" language with support for parallelism. If you choose this option, include logs showing inputs, runs and sorted outputs. You will also need to implement the assumed functions mentioned above (although the local sort can be done via a library call in most languages).