 Computer Science Department |
 |
 |
 |
 |
 |
 |
 |
15-410 Homework 2
This homework assignment is due Friday, December 6th at 23:59:59. As we intend to make solutions available on the web site immediately thereafter, . Late days are not available for this assignment.
Homework must be submitted (online) in either PostScript or PDF format (not:
Microsoft Word, Word Perfect, Apple Works, LaTeX,
XyWrite,
WordStar,
etc.).
A plain text file (.text or .txt) is also acceptable, though it must conform to Unix
expectations,
meaning lines of no more than 120 characters separated by newline characters
(note that this is not the Windows convention,
and MacOS has two different conventions).
Except as otherwise directed (in the crypto question), turn
in your answers as
.../$USER/hw2/$USER.pdf,
.../$USER/hw2/$USER.ps,
or
.../$USER/hw2/$USER.text.
If you use another filename,
there is some risk that your solutions will not be credited to you.
Please try not to submit your homework into your book-report
directory or the other way around.
As usual, you may discuss this assignment with others, but you must then go off by yourself to write up the solution.
Question 1 - Public Key Practicum
As you go through the steps of working on this question, try to think carefully about what each step is accomplishing in terms of underlying cryptography primitives.
Follow the directions in gpg.html to generate
a PGP key ring,
containing public and private keys
for digital signature and encryption purposes.
Do not turn the key ring in to your
hw2 directory! Instead, follow the directions on how
to export the public key information from the key ring into a file,
hw2/$USER.asc. Then create a secret message for the course
staff, in hw2/$USER.secret.asc.
Question 2 - "Good Fences Make Good Neighbors"
Recall from the
"Parallelism 3" lecture
("Parallelism: Scheduling and Memory Consistency Models")
that the Intel instruction set includes various
"fence" operations
(MFENCE, LFENCE, and SFENCE)
which enable programmers to force certain
memory ordering behaviors on parallel machines.
Also recall the code below, known as "Peterson's Solution" to the two-process mutual-exclusion problem (we refer to this as "Taking turns when necessary" in the "Synchronization 1" lecture).
boolean want[2] = {false, false};
int turn = 0;
want[i] = true;
turn = j;
while (want[j] && turn == j)
continue;
...critical section...
want[i] = false;
Part A
For the code shown above, insert the minimum set of
MFENCE operations needed for the code to behave
correctly on a parallel machine with a relaxed memory consistency
model.
Explain your answer. For example, include a comment with each
MFENCE operation that explains why it's there.
If you prefer to denote the MFENCE operation
as a call to a
wrapper function declared as
void mfence(void), that
is permissible.
Part B
For the original code shown above (i.e., the version without any fences),
insert the minimum set of
LFENCE and SFENCE operations (but not MFENCE
operations) needed for the code to behave correctly on a parallel machine with a
relaxed memory consistency model.
Again, explain your answer. Also again, you may assume the existence of
wrappers called lfence() and sfence().
Helpful Hint
By the way, if you think you are having AFS permission problems,
try running the program located at
% /afs/cs.cmu.edu/academic/class/15410-f13/pub/access_hw2
[Last modified Tuesday December 03, 2013]