Homework 5: Paper Reading & Critique

Sanjay Rajopadhye

The goal of this assignment is to give you practice in reading, studying, analyzing and critiquing research papers. You will do this on he classic 1974 paper, Lamport's, "Parallel Execution of DO Loops."

Although the paper is classic, it is not very easy to follow. In the Thursday lecture, I first presented some of the highlights of the paper. I also gave you a specific strategy to read the paper for a first, detailed tchnical pass. It requires a lot of jumping around, asks you to ignore many things, and make many simplifications, and walks through one part of one of the main results of the paper (1-D wavefront schedules). As I went along I posed a number of questions for you to ponder and address when you re-read the paper.

Your assignment is to

• Make a first technical pass reading through the paper (following either my proposed path or any other path you find convenient). Write a brief summary of the main results you discover in this pass. I will use this summary to evaluate your writing.
• Make additional pass(es) through the paper, each time trying to generalize your understanding, by posing hypothetical questions like "what if it wasn't the outermost index that was missing, but some other one," or "what if the dependences in the paper wer not the way Lamport defines them, but rather the true data-flow dependences as extracted by Feautrier's analysis." Each such question will require you to make hypotheses, construct examples, and then reread the paper to understand whether/how Lamport solves the problem. If Lamport does not, how would you solve it.
• Write the results of your improved understanding. This must be in the form of a careful critique [note: critique involves criticism, but is not a synonym for it]. You must give credit where it is due, make allowances for results that were not known at that time, think of how the work influenced later work, etc.

  Michelle's CS 653 has guidelines and an example review of a classic tiling paper.