Purdue CS 250 Exam 2

The principle that allows a digital circuit to interpret a near-reference voltage as exactly that reference voltage is essential for achieving _________.

digital perfection

Computers built from CMOS are computationally fast, low volume, low mass, energy efficient, and affordable because CMOS logic circuits are:

(a) ___________ (gate compute time ˜10ˆ-10 sec) {slow, fast, unpredictable}

(b) ___________ (billions of transistors fit on one chip) {large, small, medium-sized}

(c) ___________ power (little power needed to compute or wasted when not computing) {high, low, variable}

(d) ___________ (wires and transistors of massive circuits are made simultaneously) {expensive, cheap, custom-made}

(a) fast, (b) small, (c) low, (d) cheap

In a general form truth table, the number of rows is determined by:

The number of inputs as 2^(number of inputs)

Combinatorial hardware accepts voltage inputs that are within the ranges of ________ bands for logic 0 and 1.

two

The worst case computational time of a complex combinatorial circuit is:

The total gate delay on the longest path from an input to an output

The S’R’ latch is a:

1-bit memory circuit

Sequential logic differs from combinatorial logic in that its output is a function of (a) _______ and present time inputs, and that it uses (b) _______ to supply historic outputs as inputs

(a) historic inputs, (b) feedback

Sequential logic circuits differ from combinational logic circuits because they:

Implement functions of current and historic logic inputs

In a byte-addressable memory with N bytes per word, the physical address of the word containing byte B is:

W = floor(B/N)

According to the 90/10 program locality rule, (a) _________ of instructions come from just (b) __________ of the listing instructions, and this rule is true for (c) __________ programs

(a) 90%, (b) 10%, (c) many

The latency of a memory operation refers to:

The elapsed time from start to completion of a memory operation

According to the Three Rules of the memory hierarchy, the (a) ________ level is the ultimate repository for all information long-term, and changes made at the top level must eventually propagate (b) ______ the levels

(a) lowest, (b) down

What are the 3 C’s of cache misses?

Compulsory, capacity, and conflict

Compulsory misses can be reduced by making the _______ size larger

block

The principle of locality in virtual memory refers to the tendency of programs to access a ________ set of pages during a time window

small

The principle of locality is exploited by keeping the _________ set of pages in main memory

working

The concept of thrashing in virtual memory refers to a situation where the system spends more time (a) _________ pages than executing useful work, and it occurs when the working set is (b) ____________ than the available physical memory

(a) swapping, (b) larger

What is a conditional branch?

An instruction that tests a value and that allows for a subsequent transfer of control to a new address in the program based on the outcome of the test.

What is a branch address table?

Also called branch table. A table of addresses of alternative instruction sequences.

Consider the L1 instruction cache of a present-day CPU. How many of the characteristics in the following list does this cache have?

Volatile, random access, high latency, needs refresh, highest density of electronic memories

2 (volatile and random access)

A direct mapped cache design is changed such that the number of bytes in a block is doubled but the capacity of the cache is unchanged. What other characteristic of the cache must have changed?

Number of sets

This memory technology may contain flaws in its circuits that are hidden by the manufacturer before the time of sale to the end user.

Flash

Which memory technology uses destructive read?

Magnetic disk

A computer language has dependence on a specific computer circuit and no language abstractions. This language is:

assembly language

A mnemonic in an assembly language program is a symbolic name for:

an opcode

Which is not hidden from software by memory technologies?

Cost

A cache uses 32-bit memory addresses, has 4-word blocks, 4-byte words, and is k-way associative. Which one of the following questions, when answered, will provide information allowing the size of the tag field for this cache to be determined?

A) What is the value of k?
B) What is the size of the index, or set number field?
C) What is the replacement policy for this cache?
D) Is this a write-back cache?

What is the size of the index, or set number field?

Which of these assembly language instructions overrides the default next instruction pointer value without performing the operation, “add a value to the default next instruction pointer”?

A) Branch

B) Call subroutine

C) Jump

D) Add

None of the answers are correct

Let N and K each be equal to some power of 2. For a memory with N locations that each store a K-byte word, how many bits are required for a word address?

log₂(N)

(N = 2^m, where m is the number of bits required to address N locations. Since we are just looking for the number of bits required for a word address, we don’t care about K and just need m, which is equivalent to log₂(N))

Consider an assembly language program that executes and ends normally. Name an assembly language instruction for which the next address in the instruction execution trace of this program was both not the default next instruction address and the next address is known statically.

Jump

The following average memory access time (AMAT) equation is a model for performance of a two-level memory hierarchy comprising a cache and a memory.

AMAT = Hit Time + Miss Rate x Miss Penalty

Assume a computer with a two-level memory hierarchy and a C program written without paying any attention to that memory hierarchy. Which term(s) of the AMAT equation might improve if the compiler improves?

Miss rate

What electronic memory technology suffers failures when in use, detects those failures, and then hides the non-functional portion of the device from system software?

Flash

Consider this processor circuit. How many buses in this figure carry bit strings that are not used to Fetch and Execute an ADD instruction?

Remember, a bus may branch, such as the bus for the output of the 32-bit program counter in the figure, but it remains one bus.

Recall that the definition of ADD is dst_reg ← reg_A + reg_B; PC ← PC + 4.

1 bus

If an array element index value can be converted to a pointer to that array element by, first, performing a logical left shift of 3 bit positions on that index and, second, adding that result to the address of the first array element, then what is the size of an array element in bytes?

8 bytes

What software characteristic allows a computer memory hierarchy to have average memory access time similar to the lowest latency, greatest cost per bit technology in the hierarchy and also have the average cost per bit similar to the lowest cost per bit, greatest latency technology in the hierarchy?

Program locality/locality of reference

A general-purpose processor executes an HLL (high level language) program by:

performing the fetch-execute cycle

Which is a reason that the representation of machine instructions differs among various general-purpose processors?

A) machine instructions for one processor are not intended to be portable to another general-purpose processor

B) different general-purpose processors have different collections of combinatorial function circuits in their ALU

C) different general-purpose processors have different numbers of general-purpose registers in their register unit

All of these answers are correct

A machine code program:

A) is a series of machine instructions.

B) does not contain undefined binary digits.

C) is constant.

D) has a first instruction.

All of these answers are correct

Consider this assembly language snippet:

target1: cmp r3, #536   @ compare r3 contents with decimal 536
	 ble target2    @ fetch at target1 if r3 <= 536
	 add r3, r3, r4 @ r3 <- r3 + r4, integer addition
	 b target1	@ always fetch next at target1
target2: add r5, r6, r7 @ r5 <- r6 + r7, integer addition

Assume that initially register r3 contains a 32-bit string consisting only of zero bits, and that register r4 contains the 32-bit 2’s complement bit string for decimal integer 3. What control flow program structure does the snippet implement?

while loop

The first pass of an assembler over an assembly language program:

builds a symbol table, a table of correspondence between each label and its position in the assembly language program

An if-else construct written in assembly language contains:

Two labels with one defined before use and the other used before definition

(T/F) Assembly language syntax matches machine instruction format field order.

False

Which memory technology requires the use of wear leveling?

Flash

When a clocked register is receiving power:

A) the register is not necessarily storing a bit string.
B) the register waits for an input bit string before it outputs a bit string.
C) the register waits for a clock input before it outputs a bit string.

All of the answers are correct

(T/F) An immediate operand is an operand obtained from a register in a register unit.

False

Which location is not suitable for containing input resulting from program prompts that request input from the program user?

Immediate field of a machine instruction

A purpose for choosing fixed-length machine language instructions is:

to make instruction fetch and decode faster

Which of these assembly language instructions overrides the default next instruction pointer by adding a fixed constant to that pointer?

A) Branch
B) Return from subroutine
C) Jump to address equal to register + offset

Branch

Processor hardware does not use pointers to:

access immediate operands

What is the time taken by a logic gate to perform its computation called?

Propagation/gate delay

What data structure is used to store the machine code program for a processor having a fixed-length instruction representation?

A memory array

What is the greatest possible number of registers in one register unit for a computer having a 32-bit machine instruction format (representation) that has three register pointer fields, no offset field, a 6-bit opcode filed, and no other fields in the representation?

256 registers

The picture shows information about one machine instruction for some 32-bit computer.

Assemble the following assembly language instruction and write the resulting 32-bit bit string using hexadecimal notation. Unused fields must be filled with 0 bits.

ADDI r1, r1, 7

0×28210007

(T/F) Sometimes the bit string in the opcode field of a machine instruction representation has no valid meaning.

True

(T/F) Sourcing two operands simultaneously from the register unit using two register pointer fields in a machine instruction requires using two multiplexers within that register unit circuit.

True

(T/F) Assume that the subroutine call assembly language instruction adds an offset to the default next instruction address to compute a pointer to fetch the first instruction of the called subroutine. In a machine language program that contains exactly one subroutine that is called from several locations in the main routine, each of the machine language instructions calling the subroutine will be identical bit strings.

False

Which memory technology is non-volatile?

A) Register

B) SRAM

C) DRAM

D) Any technology where the bit strings are not accessible when the power is restored after a power failure

None of the answers are correct

How is a general-purpose processor circuit configured so that it will execute a particular machine instruction of the instruction set architecture?

By computing the processor control logic circuit outputs

Execution of which machine instruction can change the execution trace away from the default next machine instruction?

Jump

A label in an assembly language program is a symbolic name for:

a memory address

The stored charge representing a 1 bit leaks rather rapidly from the DRAM memory cell. This requires that the DRAM memory controller include the capability to:

refresh all of the 1 bits in the memory circuit array

The characteristic of a memory technology that most affects program execution time is:

latency

List all of the registers that hold the result of any instruction in the following snippet:

      loadi r5, 16     ; r5 <- 16 (load immediate value into register r5)
loop: load r1, r5, 40  ; r1 <- memory[r5 + 40]
      add r1, r1, r2   ; r1 <- r1 + r2
      addi r5, r5, -4  ; r5 <- r5 - 4
      store r1, r5, 40 ; memory[r5 + 40] <- r1
      bne r5, 0, loop  ; branch to loop if r5 != 0, else fetch at default next instruction

r1, r5

Consider a computer enhancement that offers Se speedup and can be used 50% of the time by a given program. What is the maximum possible overall speedup for this given program when the enhancement is made available for the program to use?

2 times faster (use Amdahl’s Law)

The instruction decoding circuit in a processor with 32-bit machine instructions has extracted the offset field bit string from the current machine instruction. Assuming that the offset bit string is a 2’s complement integer, what must be done with the offset bit string before sending it to the 64-bit ALU of this processor?

Sign-extend it to 64 bits

When a circuit output is connected to a circuit input, we say the circuit has:

feedback

Let N and K each be equal to some power of 2. For a memory with N locations that each store a K-byte word, how many bits are required for a byte address?

log₂(N * K)

Consider this processor circuit. How many buses in this figure carry bit strings that are not used to Fetch and Execute an ADD instruction?

Every bus begins at a circuit element symbolized by an oval, rectangle, rounded rectangle, or other geometric shape with area.

Remember, a bus may branch, such as the bus for the output of the 32-bit program counter in the figure, but it remains one bus.

Recall that the definition of ADD is dst_reg ← reg_A + reg_B; PC ← PC + 4.

2 buses

(T/F) Machine instructions for one processor are intended to be portable to another general-purpose processor.

False

(T/F) Different general-purpose processors have different collections of combinatorial function circuits in their ALU.

True

(T/F) Different general-purpose processors have the same number of general-purpose registers in their register unit.

False

(T/F) When a clocked register is receiving power, the register is storing a bit string.

True

(T/F) When a clocked register is receiving power, the register does not wait for an input bit string before it outputs a bit string.

True

(T/F) When a clocked register is receiving power, the register waits for a clock input before it outputs a bit string.

False

(T/F) A machine code program is a series of machine instructions.

True

(T/F) A machine code program contains undefined binary digits.

False

(T/F) A machine code program is constant.

True

(T/F) A machine code program does not have a first instruction.

False

(T/F) IEEE 754 Floating Point Representation has two bit strings for the value zero.

True

The three fields of the IEEE 754 representation are (a) _________, (b) ___________, and (c) ____________.

(a) sign, (b) biased exponent, (c) mantissa

What is a combinational element?

An operational element, such as an AND gate or an ALU.

What is a state element?

A memory element, such as a register or a memory.

What is a datapath element?

A unit used to operate on or hold data within a processor, such as the ALU or adders.

(T/F) The program counter is the register containing the address of the next instruction in the program to be executed.

True

(T/F) The register file always outputs the two registers' values for the two input read addresses.

True

What is the difference between jump and branch?

A jump instruction is unconditional and will go to a static address which is known at compile time. A typical branch instruction is conditional, so whether it will go to the given address is not known until runtime.

What is a structural hazard?

When a planned instruction cannot execute in the proper clock cycle because the hardware does not support the combination of instructions that are set to execute.

What is a data hazard?

Also called a pipeline data hazard. When a planned instruction cannot execute in the proper clock cycle because data that is needed to execute the instruction are not yet available.

What is forwarding?

Also called bypassing. A method of resolving a data hazard by retrieving the missing data element from internal buffers rather than waiting for it to arrive from programmer-visible registers or memory.

What is a control hazard?

Also called a branch hazard. When the proper instruction cannot execute in the proper pipeline clock cycle because the instruction that was fetched is not the one that is needed; that is, the flow of instruction addresses is not what the pipeline expected.

What are the 5 stages of LEGv8 instructions?

1. Fetch instruction from memory.

2. Read registers and decode the instruction.

3. Execute the operation or calculate an address.

4. Access an operand in data memory (if necessary).

5. Write the result into a register (if necessary).

(T/F) During stage 1 of the load datapath pipeline (instruction fetch), the register file is written to.

False

(T/F) Sign extension is a part of stage 2 of the load datapath piepline (instruction decode),

True

(T/F) The ALU operates during stage 3 of the load datapath pipeline (execution).

True

(T/F) Instruction memory is read during stage 4 of the load datapath pipeline (memory).

False

What is the fifth stage of the load datapath pipeline?

Write back (WB)

What is a NOP instruction?

An instruction which does nothing to change the state and stalls the pipeline.

Discarding instructions from a pipeline is known as _____ the pipeline.

flushing

Instead of stalling until a branch is complete, what optimization can be made that halves the cost of control hazards?

Predict that the conditional branch will not be taken and continue execution down the sequential instruction stream

What is temporal locality?

The locality principle stating that if a data location is referenced then it will tend to be referenced again soon.