2002 Summer CS147 Midterm 3 Study GuideJuly 18,2002Fundamentals of computer designInstruction set designCache memoryMemory-hierarchy design2002 Summer CS147 Midterm 3 Study GuideJuly 18,2002- Fundamentals of computer design1. The task of a computer designer 2. Technology and computer usage trends 3. measuring and reporting performance 4. Principles of computer design 5. Concept of memory hierarchy - Instruction set design6. Classifying instruction set architectures 7. memory addressing 8. Operations in the instruction set 9. Type and size of operands 10. Encoding an instruction set - Finite State machines and Flip-flop- Pipelining- Recent Trend in Computer Architecture- Cache memoryo Basic notions o Cache structure o Writing to the cache o Replacement algorithms o Other types of caches: Split I- and D-caches On-chip caches Multi-level caches Write assembly caches o Cache analysis o Cache design considerations o Virtual-to-real translation Translation lookaside buffer (TLB) Overlapping address translation and cache lookup- Memory-hierarchy designo Principle of locality o Caches o Main memory o Virtual memory Virtual-memory structure Virtual-memory mapping Improving program locality o Protection of virtual memory o Design of memory hierarchy Sample Problems1. Consider a computer having 4-bit memory cells. Use this assumption to answer the following two questions. (a)How many bytes of memory can be accessed using a 16-bit address? (b)If a single memory cell were used to store a single symbol, how many different symbols could be represented by a cell? 2. Convert 105 base 7 to its decimal, binary, and hexadecimal equivalents. 3. Convert 1023.0625 base 10 to its binary, octal, and hexadecimal equivalents. 4. Convert -1234 base 10 to its sixteen-bit one's complement binary equivalent. 5. Convert -2345 base 10 to its sixteen-bit two's complement binary equivalent. 6. Convert 10000001 from eight-bit one's complement to decimal. 7. Convert 10010011 from eight-bit two's complement to decimal. 8. Perform an eight-bit two's complement addition of 01101001 and 10001000. 9. What is the instruction cycle and clearly describe its steps?The instruction cycle is the process in which a computer executes a single instruction. Often called the Fetch-Decode-Execute cycle. Here are the steps:- Fetch: control unit loads instruction from memory location in PC into IR- Decode: control unit interprets instruction- Execute: control unit executes instruction (tells ALU what to do)- Increment PC: PC is incremented to next program instruction and cycle repeats10.What is the purpose of registers in the ALU?Registers hold values that are needed in operations performed by the ALU. ALU handles the arithmetic andlogical operations in a CPU.11.What is a cache and describe its purpose?A cache is smaller and faster memory that is used to store frequently used memory values in order to improve memory access performance. When CPU attempts to access memory, it first looks for the data inthe cache before going to the slower larger memories12.What is a cache miss? Cache hit?If data is found in the cache, it is called a cache hit. Otherwise, it is a cache miss.13.What does “locality of memory references” mean?The idea that frequently accessed data tends to be close together in memory. 14.Describe the memory hierarchy, starting with the CPU.A collection of memories ranging from the largest and slowest hard disk drive to the smallest and fastest on-chip L1 cache.CPU cache( L1, L2, …) main memory disk controller cache hard disk storage. 15.Fill in the entries of the following table. Maintain the same value within a row of the table. Make all binary representations 8 bits. decimal sign magnitude one's complement two's complement 64 0100 0000 0100 0000 0100 0000 72 01001000 0100 1000 0100 1000 -1 1000 0001 11111110 1111 1111 -16 1001 0000 1110 1111 11110000 16.17. Design the following finite state machine. The FSM takes two continuous streams of unsigned 4-bit numbers A and B in a serial fashion with the most significant bit first. The least significant bit is marked by the presence of a 1 on the control line C. When C is asserted, the output Z should become 1 if the 4-bit number A is larger than B, otherwise Z remains 0. The following bit stream illustrates the operation of the FSM: A (A3 A2 A1 A0): 1 0 1 1 1 0 1 0 0 1 1 1 . . .B (B3 B2 B1 B0): 0 1 1 1 1 1 0 0 0 1 1 0 . . .C : 0 0 0 1 0 0 0 1 0 0 0 1 . . .Z (OUTPUT) : 0 0 0 1 0 0 0 0 0 0 0 1 . . .Draw the state diagram for the FSM, assuming that you implement it as a Mealy machine. Label the transitions with the inputs A, B, C (in this sequence) and give them the values 0, 1 or X. Only the minimized state diagram will get full credit (there is no need to apply the state minimization methods). Solution:State Diagram: Alternative solution needs an additional state (reset state):18. Design a 2-bit counter that counts in the following fashion depending on the status of two control signals A and B: A B Function0 0 Stop counting (hold the count)0 1 Counts up by 11 0 Counts down by 11 1 Gray code up counterDraw the state diagram. Indicate in each state the binary value of the counter (00, 01, etcSolution: . a b. Binary up counter : 00 --- 01 --- 10 --- 11 --- 00 ... Binary down counter : 00 --- 11 --- 10 --- 01 --- 00 ... Gray up counter : 00 --- 01 --- 11 --- 10 --- 00 ... 19.Implement a counter that can count in two sequences, depending on a control signal X: When X=0, the counter goes through the sequence 0, 1, 2, 3, 0, etc When X=1, the counter goes through the sequence 0, 2, 1, 3, 0, etc. An output signal is generated at every 4th pulse (when the counter goes from state 3 to back to 0). This counter has to be implemented as a Mealy machine. You can make use of SR flip-flops, one 3:8 decoder and OR gates. You have two SR flip-flops, one 3:8 decoder and several OR gates available.a. Give the state diagram [10 pts] b. Give the state transition table with the inputs to the SR flip flops and the output. Use the following state encoding (State 0 (00), State 1 (01), State 2(10) and State 3 (11)). [5pts]c. Draw the schematic of the counter using the above specified components. [5 pts] Solution: a. State Diagram b. State transition and excitation table: Q1Q0X Q1+Q0+S1R1S0R0OUTS00 0 0 0 1 0 X 1 0 0S00 0 1 1 0 1 0 0 X 0S10 1 0 1 0 1 0 0 1 0S10 1 1 1 1 1 0 X 0 0S21 0 0 1 1 X 0 1 0
View Full Document
Unlocking...