Quiz Show Queries

Quiz Show 11/18

1. In a fully-associative cache with 32 entries of one word each, how many tags must be matched against the memory address in parallel? 32
2. In a 4-way set-associative cache with 32 total entries of one word each, how many tags must be matched against the memory address in parallel? 4
3. What is a big problem for direct-mapped caches? Thrashing can occur if instructions and their data map to the same blocks.
4. Give a common example of when a larger block size is advantageous. When executing a sequence of instructions or when looping through every element of an array.
5. Give a common example of when a larger block size is advantageous for an I/D cache. (see above)
6. With 64-bit addresses, 32-bit words, block size of 16 words, an 8-way set associate 32kB cache (total size for tags and data), which bits of an address are used to index into a block? bits 0-3
7. With 64-bit addresses, 32-bit words, block size of 16 words, an 8-way set associate 32kB cache (total size for tags and data), which bits of an address give the slot index of a subcache? 32kB/(4 bytes/word * 16words/entry + about 8 bytes for the tag)/8 = 56.89; nearest power of 2 is 64, so 6 bits needed for index; so bits 4-9 serve as the index
8. With 64-bit addresses, 32-bit words, block size of 16 words, an 8-way set associate 32kB cache (total size for tags and data), which bits of an address are used for the tag? bits 10-63
9. If a 4-way set-associate cache with block size 2, 32-bit word and address size uses 5 bits for a slot index, exactly how many total bits are needed for the cache not counting valid, dirty or LRU/FIFO bookkeeping bits? The tag is 32-5-1=26 bits; each entry has two words (block size 2) and a tag or 32+32+26=90bits; each subcache has 2^5 (5 bits for the slot index) entries and there are 4 (4-way) subcaches, so the total number of bits in the cache is 90bits*4*2^5=90bits*4*32=11520bits=1440Bytes
10. If a 4-way set-associate cache with block size 2, 32-bit word and address size uses 5 bits for a slot index, has a valid bit, uses write-back write policy, and uses full LRU cache replacement policy, exactly how many total bits are needed for the cache? The tag is 32-5-1=26 bits; each entry has two words (block size 2), a tag, a valid bit, a dirty bit, and 2 LRU bits (2 bits are needed to represent the ordering among 4 subcaches) or 32+32+26+1+1+2=94bits; each subcache has 2^5 (5 bits for the slot index) entries and there are 4 (4-way) subcaches, so the total number of bits in the cache is 94bits*4*2^5=12032bits=1504Bytes
11. What is fetched in a fetch-decode-execute cycle? the next instruction (and maybe data)

Quiz Show 10/28

1. Name two advantages of microprogramming. Easy to change how instructions work (e.g., to fix a bug in an instruction) and easy to add instructions (e.g., for special purpose versions of a microprocessor)
2. Give two reasons why microprogramming fell out of favor. High-level machine instructions were either not general enough or if general enough, then too complex or too slow; too much chip real estate was taken up by the control logic for microprogramming; pipelining works better with uniform length/time instructions; microprogramming is slower.
3. What is meant by locality of reference? recently accessed items tend to be accessed again in the near future; accesses tend to be clustered in address space; instructions tend to be accessed sequentially.
4. What is meant by a memory hierarchy? A typical computer contains smaller numbers of expensive memory like registers and gradually more and more of the cheaper memory like chaches, DRAM, hard disks, optical disks, and magnetic tape.
5. Assuming each entry in a fully-associative cache contains exactly one word from memory and a memory address is 16 bits, how many bits are in the tag of of a cache entry? 16 bits
6. In a direct-mapped cache with 8 blocks of 16 words each, how many bits are in the tag of a cache block if a memory address is 16 bits? 9 bits
7. In a two-way set-associative cache with 64 sets/slots of one word each, how many bits are in the tag field of a cache block if a memory address is 16 bits? 10 bits

Quiz Show 10/28

1. Since Sparc assembly language is a load-store architecture where no memory addresses appear in the instruction, how does the machine know what address in memory to load from or store to? The memory address is in a register and the register number is specified in the instruction (indirect addressing).
2. Why did the RISC II designers decide to not support direct memory addressing? Their code studies found very few operand accesses (10%) used direct memory addressing and direct memory addressing can easily be synthesized by indirect addressing.
3. In the Berkeley RISC group's code studies, what type of high-level language construct took up the most time (20-45% of machine instructions in a program and 30-60% of memory accesses)? call/return instructions
4. Because subroutine calls/returns take up so many memory accesses in calls/returns (30-60% of a typical program), what steps did the RISC II designers take to optimize memory accesses in calls/returns? rotating registers are used to pass arguments and the return address, thus bypassing the stack unless recursion levels get too deep.
5. How did the RISC II designers know how many registers are needed to pass arguments? They did a code study that found that very few subroutines require more than 3 (0-7%) to 5 (0-3%) arguments.
6. How did the RISC II designers know how big of a register file was really needed? They analyzed code and found that very few programs required more than 8 (1-20%) to 12 (1-6%) words of argument and local variable storage. Their code analysis also found that very few programs nested deeper than 4 (0-15%) to 8 (0-3%) deep. So 32 to 96 words of register storage would be sufficient for the vast majority of programs.
7. What performance feature of the UltraSPARC IV is now finding its way into more common microprocessors like the Pentium Extreme and Athlon 64 X2? dual-core
8. What feature of the SPARC IV supports high reliability? ECC data pathways to memory and bus
9. What software is touted by the UltraSPARC IV white paper as provided by Sun Microsystems to fully take advantage of the UltraSPARC IV's dual-core architectures? optimizing compilers and tuned libraries

Quiz Show 10/14

1. What does the Control Unit of a CPU do? It decodes the instruction to provide control inputs to the ALU, the bus (or busses) and routes data among the ALU, registers and bus (or busses).
2. What does an assembler do? Also give one example of why assembly is more difficult than just substitution of a particular series of binary bits for a particular series of alphanumeric characters. It translates assembly language into machine language. When jumping to a label, the exact binary address of the label cannot be determined until all previous instructions have been translated (this is why most assemblers have two passes -- one pass to translate the code, the second pass to substitute the actual address).
3. What are the two main components of a DRAM bit? A capacitor and a transistor
4. In a one address instruction set design, when performing an operation like add or multiply or compare that requires two operands, what is the implied operand? the accumulator
5. In a zero address instruction set design, where do the operands come from? the stack
6. Is the Sparc instruction set a zero, one, two, or three address design? three
7. In Sparc assembly language, where do you put the arguments to a subroutine before calling the subroutine? in %o1 to %o5 and the stack if necessary
8. Since Sparc assembly language is a load-store architecture where no memory addresses appear in the instruction, how does the machine know what address in memory to load from or store to? the memory address is in a register and the register number is specified in the instruction
9. What is strange about the Sparc branch instructions (e.g., call, ret, ba, be)? The instruction immediately after the branch instruction is executed before the branch.

Quiz Show 10/7

1. In the early days of computers, how did a computer know when an I/O device has finished its current command and is ready for the next command? polling.
2. In modern computers, how does a computer know when an I/O device has finished its current command and is ready for the next command? The I/O device signals an interrupt
3. Why is interrupt driven I/O such an advantage over polling? The CPU do other useful work while the device driver is working, which typically takes thousands to millions of CPU cycles.
4. Name the three types of lines in a typical bus. data, address, control
5. What do RISC and CISC stand for and what is the philosophy behind RISC (i.e., why do proponents of RISC claim it is better than CISC)? Reduced Instruction Set Computer and Complex Instruction Set Computer. A smaller less complex instruction set means less logic is needed on the processor chip and the clock can be sped up because the clock must be slow enough for the slowest machine instruction to complete.
6. What is the use of a Karnaugh Map? To help simplify a logic expression by visualizing blocks that represent a simplification.
7. What is a program counter? A special-purpose internal register used to store the address of the next instruction.

Quiz Show 9/30

1. What is the truth table for a JK flip-flop upon the falling edge of the clock?

   J	K	Q
   0	0	Q (no change in value)
   0	1	0
   1	0	1
   1	1	!Q (invert previous value of Q)

2. What is the truth table for a D latch with clock input?

   D	Clock	Qold	Qnew
   x	0	0	0
   x	0	1	1
   0	1	x	0
   1	1	x	1

3. Draw the Karnaugh Map for the D latch

Qnew	D/Clock
Qold	00	01	11	10
0	0	0	1	0
1	1	0	1	1

4. Find the minimal boolean equation for the D latch using the above Karnaugh Map. DC+Qold!C
5. Draw the circuit for the above minimum boolean equation.
6. Prove that the above circuit works for all possible combinations of inputs by tracing the values through the circuit.
7. Using a Karnaugh Map give the minimum boolean equation for an even parity bit given three data bits a, b, and c. a xor b xor c
8. Using a Karnaugh Map give the minimum boolean equation for an odd parity bit given four data bits a, b, c, and d. a xnor b xnor c xnor d
9. Using a Karnaugh Map give the minimum boolean equations for the sum and the carry of a half-adder with inputs x and y. sum=x xor y, carry=xy

Quiz Show 9/23

1. Draw a half adder using only two gates.
   
2. Draw a full adder.
   
3. Draw an SR latch with nor gates.
   
4. Draw an SR latch with clock input using Nand gates.
   
5. Draw an RS flip-flop.
   
6. Draw a conversion of an RS flip-flop into a D flip-flop.
   
7. Draw a D latch using only Nand gates.
   
8. Draw a D flip-flop using only Nand gates.
   

Quiz Show 9/16

1. A NAND gate has inputs a and b and its output is sent to both inputs of a second NAND gate. What is the equivalent gate of the two NAND gates? An AND gate.
2. A NAND gate has inputs a and a and a second NAND gate has inputs b and b. Both of these NAND gates send their outputs to a third NAND gate. What is the equivalent gate of the three NAND gates? An OR gate.
3. Which two gates are universal gates (i.e., several of those gates can be used to create any other gate)? NAND and NOR
4. Give a set of three gates, not including NAND or NOR that are universal. AND, OR and NOT
5. What is DeMorgan's Law? !(xy) = !x + !y and !(x+y) = !x!y
6. How many parity bits are needed for a Hamming code with one data bit and which bits are they? two parity bits: DPP (D is a data bit, P is a parity bit)
7. How many parity bits are needed for a Hamming code with four data bits and which bits are they? three parity bits: DDDPDPP
8. What is even parity and what is odd parity? Give examples. All bits including the parity bit add up to an even number. For example even parity: 110, odd parity: 111.
9. For Hamming code 1001010 with even parity, which bit, if any, is wrong? bit one (the rightmost bit)
10. Calculate the CRC for the bit pattern 101 (decimal 5) and data block 101101111. The checksum is 10, so the entire message is 10110111110.

Quiz Show 9/7

1. Write the number -5 as a one-byte ones-complement binary. 11111010 (5 = 00000101)
2. Write the number -7 as a one-byte twos-complement binary. 11111001 (7 = 00000111, 7 complemented = 11111000, then add 1)
3. Write the number 54 as a one-byte BCD. 01010010
4. What are the three parts of a floating-point number? sign, exponent, and significand (aka mantissa).
5. What is double-dabble? Give a small example. It is a fast way to convert binary numbers to decimal. Starting from the leftmost one, set the sum to 1, multiply it by 2 and then add the next digit to get the new sum. Repeat until there are no digits left. For example, 101 binary is (1*2+0)*2+1=5
6. Why is two's complement the most popular choice for representing signed integers? Because addition and subtraction is easy (all numbers, positive and/or negative can be added the same way).
7. Which group designed the current standard for floating point numbers and operations? Give both the acronym and what it stands for. IEEE (Institute for Electrical and Electronic Engineers)
8. What is the binary representation of decimal 1.5? 1.1
9. What is the exponent of binary 1001.1001 with a 4-bit (half a byte) exponent using excess 7 bias? 1010 (need to shift the binary point 3 positions to get 1.0011001, so exponent is 3, then add it to 7 for the bias to get 10 and finally convert 10 to binary to get 1010)
10. What is the significand of binary 1001.1001 with an 8-bit (one byte) significand? 00010010 (1001.1001 in canonical form is 1.001001, then drop the initial one to get 001001 and add a trailing 0 for 8 bits)

Quiz Show 8/29

1. What are the two configurations of silicon transistors? PNP and NPN
2. What are the three components of a Von Neuman computer? CPU, memory, and I/O.
3. What is CPU an abbreviation for and what are its main components? A Central Processing Unit contains an ALU, registers, and a control unit.
4. What is ALU an abbreviation for and what does it do? An Arithmetic Logic Unit computes integer arithmetic and boolean operations.
5. What is FPU an abbreviation for and what does it do? A Floating Point Unit computes floating-point arithmetic.
6. What is fetched in a fetch-execute cycle? the next instruction (and maybe data)
7. What is a program counter? A special-purpose internal register used to store the address of the next instruction.
8. What part does the cathode (filament) of a triode vacuum tube play? It heats up so that electrons are freed up into the vacuum.
9. What part does the anode (plate) of a triode vacuum tube play? It heats up so that electrons are freed up into the vacuum.
10. What part does the grid of a triode vacuum tube play? It controls the flow of electrons from the cathode to the anode.
11. Before operating systems, how did a computer know which instruction to execute first upon powering up? Either the PC would always be loaded with a fixed address (e.g., 0) or the user could load in an address via front panel toggle switches.
12. What are the advantages of transistors over vacuum tubes for computers? They are smaller, faster and cheaper, use less power and generate less heat.