CSE.240b Programming Assignment 1
|
Due: May 9 (you may request an extension but it is best to finish it by this date)
The goal of this assignment is to get comfortable with the DataStar machines, and some general hacking.
Please browse the SDSC DataStar Userguide so that you understand
what
information is available.
Errata:
May 02, 2006 7:00 pm
Typo in Dekker's fixed.
May 02, 2006 7:00 pm
According to Saturnino, what is given as Dekker's algorithm is apparently Peterson's algorithm:
{Peterson, G. L. Myths about the mutual exclusion problem. Information Processing Letters 12, 3 (13 June 1981), 115--116.}
Dekker's is more complicated. (Serves me right for trusting those old MIT lecture notes!)
Running on the DataStar machines.
CPU Time
Each student has been allocated 100 SUs of CPU time; it is up to you to
manage this time and make sure you do not run over. 1 SU is equal to
either one-half to one CPU-hours, depending on the priority of the machine
or job queue you use. You can type:
reslist -a csd366
to see how much time you have left. Note that when you submit to the
batch queues, you are actually
being billed for all 8 of the processors
on the machine.
Types of nodes
There are several types of datastar nodes. These are enumerated
in SDSC DataStar Userguide: Running Jobs.
dslogin.sdsc.edu
This machine is for editing, compiling, running very short programs,
and submitting jobs to the batch nodes.
batch nodes
These machines are for running compute-intensive programs, and for timing the runtime with
accuracy. All official timing runs for the class must be run on these machines.
You can submit jobs to the "Normal" or "High" job queues, which dispatches to one of 265
8-processor machines. Once a job has been submitted to the job queue, it will wait in the
queue until one of the 8-processor machines is available and the job will be run. Your program
has the whole machine to itself. The output will be directed to a file
LL_out.XXXXX.
You should receive an email telling you when the job has been launched.
dsdirect.sdsc.edu
These machines are for running,
testing and debugging short compute intensive jobs. These
machines are shared machines, which means timing numbers will not be accurate.
Provided Code
For this project, some helper code has been provided for the assignment in:
/rmount/users02/ucsd/mbtaylor/prog1
You can use cp to copy it to your local directory.
This code is provided to help you with parts of the assignment.
I recommend you read through the code (including the Makefile, but not the file run-script.template, which is specific
to the DataStar system) and make sure you understand all of it.
(Use man pages and the web to look things up.
Note: some of the unix man pages are missing on the DataStar machines, you may want to try a linux machine if you don't
find the function.)
Unless you are a big hacker, you will learn advanced features of make,
POSIX, etc by reading and understanding the code. Almost everything included
demonstrates some useful feature or programming idiom.
This code includes:
Makefile
This file contains some example rules for building
your code with xlc, the IBM C compiler,
and gcc, the GNU C
compiler. xlc probably
generates better code, but gcc may be easier
and less buggy (especially at high optimization levels) to use. The default rule actually
builds the code on both gcc and
xlc (the names end in the compiler used to create them;
e.g., binary.xlc or binary.gcc)
The Makefile
also has a rule which allows you to submit programs to the batch queue by typing:
gmake binary_name.submit
e.g.,
gmake binary.xlc.submit
run-script.template
This file contains the configuration settings for submitting jobs to the batch nodes. The
Makefile
fills in some of its fields with a sed
script in order to submit jobs. You can refer to the DataStar
LoadLeveler
guide to learn how to modify this. (Keep in mind that if you modify this without renaming it,
it will affect the behaviour of the .submit rule.)
helper.c, helper.h
This contains helper code for timing sections of your programs. Contains
get_processor_freq() for determining
the speed of the processor, and diff_cycles(), for computing the number of cycles between two calls to read_real_time().
objdump
Executable file (from GNU binutils) that allows you to disassemble binaries. You will write a rule
in the Makefile that will invoke this to disassemble a binary -- .e.g.,
gmake binary.xlc.dis
gmake binary.gcc.dis
Aside: You can also look at the assembly generated by the C compiler (-S)
using a pattern rule in the Makefile.
This usually has more information about local-labels than the output of objdump; however in some cases,
it doesn't tell you what actually was generated in the end. For instance, xlc -O5
does intra-procedural analysis at link time which is only reflected in the object dump. Here is an example of generating
assembly using the makefile pattern rule:
gmake <.c file prefix>.gcc.s
gmake <.c file prefix>.xlc.s
e.g.,
gmake helper.gcc.s
main.c
Some sample code that performs timing, uses inline asm,
and creates POSIX threads.
The Assignment
Collaboration Policy:
For parts I and II of this assignment, you may not post code on the forum. However, you may describe the problems you are having
abstractly in text, or inquire/suggest as to what function, macro or instruction you should use to overcome the problem. You may also supply weblinks
for others to use to address an issue.
For part III, you can post anything as long it does not give away anything for parts I and II.
For parts I, II, and III, you may also discuss your assignment with classmates one-on-one, but try to tell people where
to find answers as opposed to telling them the answer. Also please acknowledge their help on your assignment.
Deliverables: In the following parts of the assignment, certain parts are marked as "Deliverables".
These are the parts to
be printed out and submitted. Please keep these concise and do not include excess material. Excessively unclear writeups
will not be given full credit.
I. Add a pattern rule to Makefile that invokes objdump
as described in the above objdump section.
For example
if the user has a binary named foo, then the user should
be able to type:
gmake foo.dis
and Makefile will automatically generate a new foo.dis, if the Makefile (and thus the compilation
flags)
or the source binary (or the sources it depends on) has changed since the last foo.dis was created.
Deliverable:
The lines that you added to implement this rule.
II. Using the following pseudo-code for Dekker's algorithm:
(note: c1 and c2 start out as 0, and turn as 1.)
thread_1_critical()
{
c1 = 1;
turn = 1;
L:
if c2==1 && turn==1
then goto L;
< critical section >
c1 = 0;
}
thread_2_critical()
{
c2 = 1;
turn = 2;
L:
if c1==1 && turn==2
then goto L;
< critical section >
c2 = 0;
}
IIa. Come up with a critical section that demonstrates that Dekker's algorithm fails to appropriately synchronize data between
two threads. Write the program in C, compiling with gcc and c, running with two threads on two processors on the Power4 batch queue machines.
You should modify main.c with the new code.
Make sure that the two threads are actually running simultaneously for a significant period of time (e.g., many seconds), and not just alternating.
Deliverable:
A copy of the code. Make it as simple, readable, and small as it can be. Also, include a short description of
how the critical section exposes the failure of mutual exclusion.
IIb. Add the appropriate inline sync, lwsync
or isync instructions to (IIa) to make the implementation of Dekker's correct.
You will also need the volatile keyword.
Refer to von Praun's Deconstructing Redundant Memory Synchronization
(ISCA Workshop on Duplicating, Deconstructing, and Debunking "WDDD", June 2005) paper for the approximate execution time of the instructions.
Use the disassembly rules to verify that the barrier instructions still are being found in the assembly source. You may find that the disassembler uses different names. You can verify that the instructions are correct by using the gmake .dis rule to see the actual bits that make up the instructions, and looking them up in the PowerPC manual.
Your implementation must minimize the execution time due to synchronization, without being incorrect. For the purposes of
this assignment, you do not need to measure the execution time, rather, just sum the total cost of synchronization instructions
in the loop body.
Deliverables:
1. The loops, with synchronization instructions.
2. Include a discussion of why each instruction was the minimum sufficient instruction required.
3. For first two of the following 4 cases, include the part of the .dis (or .xlc.s or .gcc.s) file corresponding to Dekker's algorithm and the critical section,
with annotations as to which line of C the disassembled code corresponds to.
Give only the code for the parts
corresponding to the mutual exclusion and critical section part of a single thread. (If this is more than 150 instructions per function, just pick the most relevant 150 instructions to do for a given piece of code.)
(To figure out how to do this, you may have to experiment with
simpler pieces of code and refer to the PowerPC manuals for instruction mneumonics.)
The 4 cases are:
i) gcc with the flags given in the supplied Makefile.
ii) xlc with the flags given in the supplied Makefile.
iii) gcc, with no optimization.
iv) gcc with the flags given in the supplied Makefile, but with no synchronization instructions
or volatile keywords. What happened to the code in this circumstance?
4. Explain what the differences are of the compiler output between the four cases listed about. Which one of the four cases is the easiest to reverse-engineer and why? Which do you think is the most correct and has the best performance?
(You may want to keep this in mind for future assignments.)
5. Does your implementation of Dekker's algorithm work with xlc -O5?
If not, why not?
IIc. Implement mutual exclusion for the same critical section using load-reserve and store-conditional.
Running the same number of
iterations, determine the respective performance of the two mutual exclusion implementations (Dekker's versus locks with load-reserve and store-conditional).
Deliverable: Measure the relative performance. Explain the results.
III. Pick a micro-architectural mechanism in the Power4 and write a piece of code that exposes its existence, through
some form of timing anamoly. Make sure to post on the forum to reserve your anomaly. At most one other person is allowed to reserve
an anomaly that has already been previously reserved. This mirrors the scientific process where people verify other people's experiments.
(I will generally be much more impressed if you propose a new anomaly.) In some cases,
it may be easiest to expose an anomaly with assembly language. In other cases, it may be easier to do this with a C program. If you
use C, you will have to figure out the correct flags for the compiler (and which compiler.) You probably will want
to disassemble the C to verify that what you expected is being generated.
Deliverable: A complete description of the experiment, including a summary of the mechanism you are trying to detect,
the reasoning behind the experiment, the code, the data collected, and the explanation of the data.
This is the
most significant part of the assignment.
Since this assignment is newly created, please do not hesitate to post for clarifications on the assignment, subject to
the restriction that you should not give away any answers. Students are free to respond to these clarification requests.
Resources
The SDSC DataStar Userguide contains
a wealth of information about using and programming DataStar.
The GNU Make manual may be useful to
understand the Makefile used in the provided code.
Power 4 Manuals: Book 1, Book 2, Book 3.