University of California, Berkeley – College of Engineering Department of Electrical Engineering and Computer Sciences Fall 2006 Instructor: Dan Garcia 2006-12-14 C S 6 1 C F i n a l E x a m Last Name First Name Student ID Number Login cs61c- Login First Letter (please circle) a b c d e f g Login Second Letter (please circle) a b c d e f g h i j k l m n o p q r s t u v w x y z The name of your LAB TA (please circle) Scott Aaron David P. Sameer David J. Name of the person to your Left Name of the person to your Right All the work is my own. I have no prior knowledge of the exam contents nor will I share the contents with others in CS61C who have not taken it yet. (please sign) Instructions (Read Me!) • This booklet contains 8 numbered pages including the cover page. Put all answers on these pages (feel free to use the back of any page for scratch work); don’t hand in any stray pieces of paper. • Please turn off all pagers, cell phones & beepers. Remove all hats & headphones. Place your backpacks, laptops and jackets at the front. Sit in every other seat. Nothing may be placed in the “no fly zone” spare seat/desk between students. • Fill in the front of this page and put your name & login on every sheet of paper. • You have 180 minutes to complete this exam. The exam is closed book, no computers, PDAs or calculators. You may use two pages (US Letter, front and back) of notes, plus the green reference sheet from COD 3/e. • There may be partial credit for incomplete answers; write as much of the solution as you can. We will deduct points if your solution is far more complicated than necessary. When we provide a blank, please fit your answer within the space provided. “IEC format” refers to the mebi, tebi, etc prefixes. You have 3 hours...relax. • You must complete ALL THE QUESTIONS, regardless of your score on the midterm. Clobbering only works from the Final to the Midterm, not vice versa. Problem M1 M2 M3 Ms F1 F2 F3 F4 Fs Total Minutes 20 20 20 60 30 30 30 30 120 180 Points 10 10 10 30 22 22 22 24 90 120 ScoreName: _______________________________ Login: cs61c-____ 2/8 Midterm Revisited M1) “Son of a bits…” (10 pts, 20 min) a) How many bits does it take to address N things? (hint: you may use the floor or ceiling function) Recall the quarter definition from midterm (skip this paragraph if you remember it): Early processors had no hardware support for floating point numbers. Suppose you are a game developer for the original 8-bit Nintendo Entertainment System (NES) and wish to represent fractional numbers. You and your engineering team decide to create a variant on IEEE floating point numbers you call a quarter (for quarter precision floats). It has all the properties of IEEE 754 (including denorms, NaNs and ± ∞) just with different ranges, precision & representations. A quarter is a single byte split into the following fields (1 sign, 3 exponent, 4 mantissa): SEEEMMMM. The bias of the exponent is 3, and the implicit exponent for denorms is -2 You’re also familiar with the Fixed-Point Representation, where the binary point is always in the same place so there’s no need to store the exponent. E.g., you could imagine splitting the Nintendo’s byte into two nibbles with the left nibble representing the unsigned whole number component (W), and the right representing the fractional component (F): WWWW.FFFF. Thus the bit pattern 0xa8 would be interpreted as the unsigned fixed-point value 0xa.8 = 0b1010.1000 = 10.510. As a systems designer, you could choose to interpret a byte any way you want, so you could change the point location (e.g., WW.FFFFFF or WWWWWWW.F) to suit your needs. b) One of your games involves velocities that always fall in the range of [10, 15), i.e., 10 ≤ v < 15. If you only have a single NES byte, you’re asked to design a novel representation to encode a velocity (assume the hardware can handle whatever you do). It should be better than a quarter, fixed-point, and any 8-bit encoding we’ve discussed! What is “better”? You will be judged on four criteria (check the box to the left of the ones you think you satisfy, listed in decreasing priority order). Explain your decoding below on the left (how to go from a bit pattern b to a velocity v), and on the right show the bit patterns that would result from encoding numbers closest to 10, 12.5 and 15 as well as the velocity each bit pattern actually represents. ______ Most bit patterns encoding the most different numbers in [10, 15) ______ You have bit patterns that are as close as possible to 10, 12.5, and 15 ______ Uniform spacing between numbers in [10, 15) is better than non-uniform ______ Simplicity My scheme has _____ NES byte bit patterns representing the range [10, 15). Here’s how I go from a bit pattern b to a velocity v: (if you’d like, you may write it mathematically... v as a function of b). Number closest to... ...and its bit pattern ...and the velocity it represents 10 0b 12.5 0b 15 0bName: _______________________________ Login: cs61c-____ 3/8 M2) “Those are some big numbers you got there…” (10 pts, 20 min) A bignum is a data structure designed to represent large integers. It does so by abstractly considering all of the bits in the num array as part of one very large integer. This code is run on a standard 32-bit MIPS machine, where a word (defined below) is 32 bits wide and a halfword is 16 bits wide. typedef unsigned int word; typedef unsigned short halfword; typedef struct bignum_struct { int length; // number of words word *num; // the actual data } bignum; a) Is the ordering of words in the num array BIG or LITTLE endian? (circle one) b) How many bytes would be used in the static, stack and heap areas as the result of lines 1, 3 and 4 below? Treat each line independently! E.g., For line 3, don’t count the space allocated in line 1. 1 bignum biggie; 2 int main(int argc, char *argv[]) { 3 bignum bigTriple[3], *bigArray[4]; 4 bigArray[1] = (bignum *) malloc (sizeof(bignum) * 2); b) Complete the add function for two bignums, which you may assume are the same length. Our C compiler translates z = x + y (where x,y,z are words) to add (not addu, as is customary) and thus could generate a hardware (HW) overflow we don’t want, as we’re running on untrusted HW. Your code should be written so that words never overflow in HW (so we do all
View Full Document
Unlocking...