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.

  1. 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.

  2. 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.

  3. 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.