Due 11:59:59 P.M on Wed 1 April 2009
When I was a student, I had one or two "resurrection" finals, in which the final was worth all of the points that you hadn't obtained from other assignments or exams. Those were not fun for me.
Instead, I thought we'd have an "instant death" assignment: if you complete it perfectly, this assignment will contribute no additional points towards your final grade in the class. However, whatever fraction of the total points that you miss on this assignment will be deducted from any points that you have managed to garner for yourself in other assignments or exams. I firmly believe that this version will be fun (for me).
Print this page out, then write your answer on the rest, scan it back in, and find an online OCR system capable of recognizing your handwriting. If your solution does not contain any errors, I will know that you did not follow these instructions. You will lose 5 points for each minor error.
Solve one of the following problems. Do not attempt to solve more than one. Any such attempt to do so will be viewed as underhanded cheating, in which case you will receive a 0 and will be required to mark all future IP packets as specified in RFC3514.
I was fairly generous in accepting late versions for previous assignments, but I'm feeling cranky today, so just turn it in on time if you want credit.
#1: Re-implement RigelSim as a single C++ template function. Your function should take one class argument encapsulating the variant of the ISA and memory model to be used in the simulation and one parameter consisting of an STL bit vector representing the program, standard C and C++ library code, and Linux operating system. Include a sample bit string based on Lab #2 with your answer.
#2: Implement a packet filter in Java that identifies and correctly marks IP packets according to RFC3514. Based on your implementation, formally derive a Verilog version of the implementation, map it onto an FPGA, and report the line speed at which your implementation can process packets. If the speed is below 40Gbps, explain how you can use parallelism to accommodate more realistic networks. Finally, prove that your implementation is sound and robust to single-bit upsets due to soft errors.
#3: Prove that P is not equal to NP, then develop an expected-time polynomial algorithm to solve an NP-complete problem.
Write your name here: