CS 736 - Paper Assignment #1

(Due: Monday, October 3)


The goal of this assignment is to design a scheduler for parallel programs running on a cluster of UNIX workstations (COW). The COW can have 100 or more workstations.

Each node in the COW is a fast workstation with multiple processors (the processors share memory); each processor has a clock speed of about 100 megahertz (assume one instruction executed per clock cycle). Each node has 64 MBytes of RAM and a fast network interface. Using the network, nodes can send data at 150 MBytes/second; end-to-end latency (for small messages) is about 100 microseconds. The nodes run only parallel programs and operating system functions; they are not used for regular computing.

Processes in a parallel program must be gang-scheduled or co-scheduled (i.e., all processes must be scheduled at the same time on all the nodes); if the processes are not gang scheduled, delays in one process multiply across all the other processes (because of synchronization). Parallel programs might be small, requiring 4 or 5 nodes, or as large as the whole cluster. Demand for nodes might change during the life of the program.

Follow is a list of questions that will help guide your design. Obviously, you do not have time to address fully all these points. Pick a core set of issues and concentrate on them.

  1. What is your scheduling criteria? Are you trying to maximize total processor utilization? Average turn around time?
  2. How will you schedule the processors? Will you give each program a partition of nodes that it keeps for the life of the programs? (space sharing) Or will the programs share nodes? (time sharing) Or some combination?
  3. How do you pick the next program to run?
  4. How do you limit the amount of resources consumed by the program?
  5. How will you evaluate your design decisions? Can you use simulation or modeling? How will you get data for simulation traces or for parameters to a model or simulation?
  6. How will your scheduling mechanisms be implemented? If you are time sharing, how will you cause a synchronous context switch? Where is the point of control for the COW? How will you start a parallel program? How do you monitor its status and completion?

If you use ideas from any other system or published paper, you MUST be careful to correctly attribute and cite work done by others.


The entire paper should be at most 6 pages, using 10 point font on 16 point vertical spacing single-sided, minimum .75" margins. The paper must contain the following parts:

The title should be descriptive and fit in one line across the page. Interesting titles are acceptable, but avoid overly cute ones.
This is the paper in brief. It is not a description of the paper. It should state the basic contents and conclusions of the paper. It is an advertisement that will draw the reader to your paper, without being misleading. It should be complete enough to understand what will be covered in the paper. Avoid phrases such as "The paper describes...." This is a technical paper and not a mystery novel; don't be afraid of giving away the ending.
This is the main part of the paper. It should include an introduction that prepares the reader for the remainder of the paper. Assume that the reader is knowledgeable about Working Set and operating systems. The introduction should motivate the rest of the discussion and outline the approach. The main part of the paper should be split into reasonable sections. The last part of the body is the conclusion. This is a discussion of what the reader should have learned from the paper. You can repeat things stated earlier in the paper, but only to the extent that they contribute to the final discussion.
You must cite each paper that you have referenced. This section appears at the end of the paper.
A paper without figures, graphs, or diagrams is boring. A rule of thumb is one figure for each 3 or 4 pages. These figures should (typically) take up only a small portion of a page. Your paper must have figures.

Do not redescribe the assignment; address the issues described above. The paper must be written using correct English grammar. There should be no spelling mistakes. A paper that is difficult to read or has poor grammar will be returned ungraded.