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
(i.e., all processes must be scheduled at the same time on all the
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.
What is your scheduling criteria?
Are you trying to maximize total processor utilization?
Average turn around time?
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?
How do you pick the next program to run?
How do you limit the amount of resources consumed by the program?
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
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
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
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.
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
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
The introduction should motivate the rest of the discussion and outline
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
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
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.