CS 213 Fall '99
Notes on Assignments and Exams

In the following, $coursedir refers to directory /afs/cs.cmu.edu/academic/class/15213-f99/

Final exam ( ps, pdf, solutions )

• Fall '98 (ps, pdf, solutions)
• Spring '99 (ps)

Lab 5 - Designing a Chat Client (ps, pdf)

L5 Important Facts

• 9 HOUR EXTENSION: L5 DUE AT 9:00 AM THURSDAY MORNING
• Check our list of references to get you started.
• A chat server is currently running on bass.cmcl.cs.cmu.edu with TCP port 4000 and UDP port 4000
• Signup sheets for demonstrations are outside Weh 7121. Click here for more information
  Demo Locations are as follows:
  Randy Bryant : Office, WeH 7128
  Dave 'O Halloran: Office, WeH 8125
  Khalil Amiri : Office, WeH 8114
  Sanjay Rao : CMCL Lab, WeH 3604 *** NOT IN OFFICE ***
  Jeff Pierce : Wean 5th floor Clusters *** NOT IN OFFICE ***
  Seggy Umboh : Wean 5th floor Clusters
  
  
• Check out the FAQ for useful information.
• Version 1.1 available in $coursedir/L5/L5.tar (11/19). 2 new options added in server: -f flushTime , -l logFile . The server deletes an entry for a client that has not sent a chat message for atleast flushTime period (expressed in minutes and must be >= 1), and logs accesses in logFile . Fixed a bug - the UDP port present in a client JOIN_REQUEST had to be converted to network order before a packet was sent. For other minor bug corrections, see comment header in server.c. A new version of the server is running on bass.cmcl.cs.cmu.edu with TCP port 4000, UDP port 4000 and flushtime 30 minutes

Errata

• Page 3: The syntax of QUIT_MSG was incorrect in the handout. It should actually read
  QUIT_MSG memberID
  where memberID is the ID assigned to the member
  The electronic version of the handout has been updated
  

Exam 2 ( ps, pdf, solutions )

Exam 2 will be held in Dougherty Hall, Room 2210 from 7:30--9:00 pm, Tuesday November 16. There will be no class during the regularly scheduled time that day. Coverage will include all of the lecture material, up through (and including) class 22 (Nov. 4). In addition, you will be expected to have really done all of the work required for homeworks H1a through H4, as well as labs L1 through L4.

Here are some logistical issues:

• The exam will be open book and open notes and handouts. You may bring any (printed) material you wish.
• You will write all of your answers on the exam. No blue books are required.

To help you get started, you will find some useful practice problems on last year's Exam 2 postscript or Adobe Acrobat, with solutions. Only the following problems overlap the material we've covered in the course so far: 3, 4 (already covered by Exam 1), 5, 6, 7. Also, there are some topics that you can expect to see on the exam that aren't covered by the old exam:

• Memory management. Allocation policies, implementing malloc and free, typical referencing errors.
• Processes. Fork, signal, wait, and exec.
• Code optimization. Machine independent and machine dependent optimization techniques.

Homework H4 - Address translation (No handin, for exam practice only) (ps, pdf)

Lab 4 - Optimizing Matrix Transpose (ps, pdf)

L4 Important Facts

• The peformance points for Part II were computed based on the geometric mean m of your speedups as follows:
  • m < 1.0: 0 points
  • 1.0 <= m < 3.0: 10*(m-1)*(m-1) points
  • 3.0 <= m: 40 points.
• The due date for Part II has been extended by 12 hours until 11:59am, Thursday 11/11.
• The web update script has been modified to send email to the first email address in the struct within your .c file. Please make sure that is the email you want to receive email at.
• One of the groups found that our code was not detecting a bug they had in their code. I've updated the code in L4.tar to do more rigorous testing. You might want to check it out, since the writeup specifies that you will not get any credit for buggy code.
• Some of the sources of inconsistent performance have been identified and fixed. The performance of the code depended on whether or not the starting addresses of the source and destination arrays were aligned on cache line boundaries. The new versions of the benchmark code (L4.tar) and the Web testing code fix these problems. This change has the following effects:
  • Make sure you are using the latest version of the source code and the Makefile. Retrieve the files from L4.tar on the assignment directory. [But make sure you don't overwrite your copy of trans.c!]
  • Some people will find their code runs ~20% faster. For example, my code went from a mean speedup of 3.51 to 4.32. Others were already getting this advantage by sheer luck. Try resubmitting your code for testing
  • We will maintain our grading policy of giving full (40 point) credit for any program with a mean speedup of >= 3.0. This is not difficult to achieve.
  • To make things interesting, we will give extra credit to any program that achieves a mean speedup >= 4.0. The number of extra credit points will be computed as: 15*(Your_mean_speedup - 4.0). For example, I would get 4.8 points.
  • In our grading, we will trust the best numbers displayed on the Web page for your group. This program uses the absolute numbers in the Lab handout as its basis.
• The automatic testing system for measuring the throughputs in Part II is now up!
  You can check the transpose statistics page to see how you and your classmates are doing.
  • Make sure your submit your file for testing using NAME=AndrewID on the command line, where AndrewID is your Andrew ID. Our program sends the email results back to AndrewID@andrew.cmu.edu.
• Part I of this assignment is due Friday November 5. Part II is due Wed. Nov. 10. Note change of date from original handout
• In the original handout, the term "harmonic mean" was used to describe our method for combining the throughput improvements into an aggregate improvement score. The correct form for the method used (as given by the formula in the handout) is "geometric mean."
• The performance points for part I (maximum of 40) will be assigned based on the Average Read/Write miss rate computed by the cache simulation. If this is a value x, then the performance will be computed by a piecewise linear formula:
  • x < 14: Points = 40
  • 14 < x <= 18: Points = 40 - 2.5 * (x - 14).
  • 18 < x <= 48: Points= 30 - (x-18)
  • 48 < x: Points = 0

Lab 3 - Implementing a Dynamic Storage Allocator (ps, pdf)

L3 Important Facts

• The deadline for L3 is now Thursday, October 21, at 11:59pm.
• Read the handout carefully for information on what you're supposed to do as well as hints on testing and debugging.
• We will be using an automated testing and grading system. Use "gmake update NAME=username" to submit your solution to the automated testing and grading system and your performance will be reported on the web in a few minutes. You can do this as many times as you wish.
• You can check the malloc statistics page to see how you and your classmates are doing.
• Use "gmake handin NAME=username", with "VERSION=version" if necessary (after the first handin) to turn in your assignment. More extensive information is available in the handout.

Homework Assignment H3 (ps, pdf)

H3 Important Facts

• Be sure to do H3 on a fish machine and not on one of the Linux boxes in the Andrew cluster. RedHat Linux 4.2 (the OS on the Andrew cluster Linux machines), and Solaris made a design decision to abnormally terminate ongoing syscalls (such as wait()) when a SIGINT arrives at a process, even though the child hasn't terminated yet. For these machines, you would need to put your wait call in a while loop to keep redoing the wait call until the child actually terminates. The Linux kernel in RedHat 5.2 machines doesn't interrupt terminate syscalls when SIGINTs arrive, so things are much simpler. So to keep your life simple, please do your work for H3 on a fish machine.
• We realize that many of your will be gone over the weekend because of midsemester break. Note that H3 is due 11:59pm on Wednesday, instead of the usual Monday handin deadline for homeworks.
• I modified the time bomb template in $coursedir/H3/timebomb.c slightly to eliminate some warning messages from gcc -Wall. The old template is OK, but us this new template if you don't want to see the warnings (droh, Thur, Oct, 7, 1999, 7:30pm).

Exam 1 ( ps, pdf, solutions )

Exam 1 will be held in class on Tuesday, October 5. Coverage will include all of the lecture material, up through (and including) class 10 (Sept. 23). Floating point will be covered. In addition, you will be expected to have really done all of the work required for homeworks H1a, H1b, and H2, as well as labs L1 and L2.

Here are some logistical issues:

• The exam will be open book and open notes and handouts. You may bring any (printed) material you wish.
• You will write all of your answers on the exam. No blue books are required.

To help you get started, we have created a practice exam available in postscript, with solutions. This exam was created by adapting problems from last Fall's version of the course, converting code to IA32. They are fairly representative of the styles of problems you will encounter. These problems, and their answers, will be covered in recitations on Monday, October 4. Note also that we don't guarantee that these practice problems cover the entire scope of the problems you'll encounter on the exam. Be sure to study the lecture notes and to review the homework and lab material.

Homework Assignment H2 (ps, pdf)

H2 Important Facts

• Note that H2 is due 11:59pm on Tuesday, instead of the usual Monday handin deadline for homeworks.

Lab Assignment L2 (ps, pdf)

L2 Important Facts

• You can check the bomb stats to see how you and your classmates did.
• Be extremely careful when working on your bomb. ANY explosion will cost you 1/4 point, even if you mistype a string by mistake, forget to set a breakpoint, or DDD crashes on you.
• Your bomb is only defused when all the inputs to the bomb are correct. So yes, you could use gdb to alter the contents of the registers and memory and then jump around the code to generate the phase defused messages. BUT you only get points for defusing a stage if the input you used is valid, so I wouldn't recommend doing this.
• There is no extra credit for the (hypothetical) secret stage. If it exists, it's for your amusement only.

Homework Assignment H1b (ps, pdf)

H1b Important Facts

• Policy Change. We will accept as correct any code that is functionally equivalent to the solution object code. That means you don't have to exactly match the object code we generate, but your procedure must do the same things as our's. You can make sure this is the case by either:
  • Getting the two so close to each other that it's clear they are equivalent.
  • Writing your own test code to compare our procedures to your's. Since you have our .o files, that shouldn't be too difficult to do.
• Policy Change. We will not accept any late submissions. Make the deadline or don't bother! This will allow us to release the solutions earlier and to let you get on with L2 rather than getting behind & staying behind.
• You'll probably want to run GDB to decode the jump table in b1.o. You must be running on one of the ``fish'' machines to do this.

Homework Assignment H1a (ps, pdf)

Solutions

• You can take a look at the Original Source Code.
• Many people generated solutions that, while functionally correct, didn't look like code any human would ever write. You should try in the future to really reverse engineer the code, understanding what the function is computing.

H1a Important Facts

• GCC seems to generate different labels in the assembly code for very similar programs. If your code matches the solution code in all respects except the labels, try modifying your code to use the loop types described in the assignment.
• You must do this assignment using version 2.8.1 of GCC on a machine having the ``i386'' instruction set as target. You will get this running on one of the Intel Cluster machines running /usr/local/bin/gcc. The assignment Make file invokes this version of the compiler. Use other machines and compiler installations at your own risk. You can determine the version of GCC by including the -v flag on the command line.
• Some documentation on IA32 and Linux is available in electronic form.

Lab Assignment L1 (ps, pdf)

9/1/99:I fixed a bug in c2c that caused it to miscount operators like "+=" and "|=". I also added a "-e" option to emit the operator count for each function. The new version of c2c is in $coursedir/L1/c2c. [droh]

L1 Frequently Asked Questions

Q1: Are we allowed to do X or assume Y?
A1: First check the CODING RULES section of bits.c or use c2c (see below). If you're still not sure, post or send mail to droh@cs.

Q2: Are we allowed to create local variables in our functions?
A2: Yes.

Q3: What is c2c?
A3: c2c is a modified ANSI C front-end that we'll use to check your Lab 1 handins for compliance with the coding rules that are documented in bits.c. It is available to you in $coursedir/L1/c2c. It runs on RedHat 5.2 Linux systems such as our Intel Cluster machines. c2c checks for illegal operators (e.g., "-"), illegal constructs (e.g., "if"), and illegal constants (e.g., "0x1ff") and prints error messages for each use. It also counts the number of operators used in each function and prints a warning if this number exceeds the legal limit for that function. If you call it with the "-e" options, it will also print the number of operators used by each function.

Example:
% ./c2c bits.c
cs213:bits.c:43:bitOr: Illegal operator (!)
cs213:bits.c:153:negate: Warning: 7 operators exceeds max of 6
cs213:bits.c:165:logicalShift: Warning: 27 operators exceeds max of 24
%

In this example, c2c found an illegal "!" operator in function bitOr, and it warned us that we were using too many operators for the negate and logicalShift functions.

Q4:For leastBitPos, the handout says 18 maxops, and bits.c says 45 maxops. Which is it?
A4: 45 is the maximum number of operators allowed for leastBitPos.