CS 3330: Past Quizzes

Convert 0x93 to binary (your answer should consist of exactly 8 characters, each either 0 or 1)

Assume x is an 8-bit twos-compliment integer. What is the numeric value of x + ~x (in decimal)?

What is the binary number 1.011 in decimal?

Consider encoding 2.5 as a floating point number with 3 exponent bits (bias = 3) and 3 fraction bits . What is the exponent? (your answer should consist of exactly 3 characters, each either 0 or 1)

Consider encoding 2.5 as a floating point number with 3 exponent bits (bias = 3) and 3 fraction bits. What is the fraction? (your answer should consist of exactly 3 characters, each either 0 or 1)

(Thought question; not part of your grade). Consider a C-style float x that is between 1e-20 and 1e20. Let the low-order bit be called bit 0 and the sign bit bit 31. There is one bit that is guaranteed to be different between x and 4*x; which bit is it? (your answer should be a number between 0 and 31)

Convert 0xdad to binary (your answer should consist of exactly 12 characters, each either 0 or 1)

Assume x is an 8-bit twos-compliment integer. What is the numeric value of x + ~x (in decimal)?

What is the binary number 11.101 in decimal?

Consider encoding -5.5 as a floating point number with 4 exponent bits (bias = 7) and 5 fraction bits. What is the exponent? (your answer should consist of exactly 4 characters, each either 0 or 1)

Consider encoding -5.5 as a floating point number with 4 exponent bits (bias = 7) and 5 fraction bits. What is the fraction? (your answer should consist of exactly 5 characters, each either 0 or 1)

(Thought question; not part of your grade). In two's-compliment there is one (and only one) number that is it's own additive inverse (i.e., x = -x). What is that number for 6-bit numbers? (your answer should be exactly 6 characters, each either 0 or 1)

Each question presents one assembly operation and asks what it does. All questions assume the following initial configuration:

Memory at byte i contains 0x1f - i for i between 0 and 15; that is

address:       0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
Memory (hex): 1f 1e 1d 1c 1b 1a 19 18 17 16 15 14 13 12 11 10

The registers used in the questions have the following initial values:

eax = 0x03020100
ecx = 0xc
esp = 8

Assume the configuration resets between each question, so that (for example) even if question 1 changes eax, eax has 0x03020100 in it again for question 2.

Both the choices presented for each multiple-choice question and the questions themselves are presented in sorted order based on the text of the question or choice. There is no other meaning to the ordering.

This quiz is open-book. You may use a calculator of computer if you wish. Do not consult with others, including others located on the Internet.

I made this a question so it will show up on the page. You don't need to answer it.

True False

Reset Selection

After executing "movl %ecx, (%esp)", which of the following changes? Reset Selection

After executing "popl %eax", what is the value in register eax? Reset Selection

After executing "pushl %eax", what is the value in register esp? Reset Selection

After executing "pushl %eax", what part of memory now contains 0x03020100? Reset Selection

Each question presents one assembly operation and asks what it does. All questions assume the following initial configuration:

Memory at byte i contains 0x20 + (i  * 3)%0xf for i between 0 and 15; that is

address:       0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
Memory (hex): 20 23 26 29 2c 2f 22 25 28 2b 2e 21 24 27 2a 2d

The registers used in the questions have the following initial values:

eax = 0x11223344
ecx = 0xc
esp = 8

Assume the configuration resets between each question, so that (for example) even if question 1 changes eax, eax has 0x11223344 in it again for question 2.

Both the choices presented for each multiple-choice question and the questions themselves are presented in sorted order based on the text of the question or choice. There is no other meaning to the ordering.

This quiz is open-book. You may use a calculator of computer if you wish. Do not consult with others, including others located on the Internet.

I made this a question so it will show up on the page. You don't need to answer it.

True False

Reset Selection

After executing "movl (%esp), %ecx", which of the following changes? Reset Selection

After executing "popl %eax", what is the value in register eax? Reset Selection

After executing "popl %eax", what is the value in register esp? Reset Selection

After executing "pushl %eax", what is in memory at byte 8? Reset Selection

Section 4.2.2 defines the HCL for bit-equality to be

    bool eq = (a && b) || (!a && !b);

Section 4.2.3 defines the HCL for word-equality to be

    bool Eq = (A == B);

Assume we have two-bit words, so A is made of bits a₁ and a₀ and B is made of bits b₁ and b₀. Which of the following defines the bit-level implementation of word-level equality (A == B)?

Reset Selection

On page 358 we see the following HCL:

int Out4 = [
        !s1 && !s0 : A; # 00
        !s1        : B; # 01
        !s0        : C; # 10
        1          : D; # 11
];
 

The text following this notes "the selection can sometimes be simplified, since only the first matching case is selected. For example, the second expression can be written !s1, rather than the more complicated !s1 && s0, since the only other possibility having s1 equal to 0 was given as the first selection expression." In other words, the above could have been written as

int Out4 = [
        !s1 && !s0 : A; # 00
        !s1 &&  s0 : B; # 01
         s1 && !s0 : C; # 10
         s1 &&  s0 : D; # 11
];

without changing its meaning in any way.

Which of the following pieces of C code allow this same kind of flexibility in how we write the boolean expressions?

(Note: more than one of the following options is "correct" and will receive full credit)

Reset Selection

Section 4.2.2 defines the HCL for bit-MUX to be

    bool out = (s && a) || (!s && b);

Section 4.2.3 defines the HCL for word-MUX to be

    int Out = [
      s : A;
      1 : B;
    ];

Assume we have two-bit words, so A is made of bits a₁ and a₀ and B is made of bits b₁ and b₀. Which of the following defines the bit-level implementation of word-level MUX  ([s: A; 1:B;])?

Reset Selection

Assume S is a non-pipelined system and P is a pipelined system. Pipelining increases both throughput and latency. Which of the following cases exemplify these principles? Check all that apply (if any do)

	A.	It takes twice as long for P to answer a single sum as it takes S
	B.	It takes twice as long for S to answer a single sum as it takes P
	C.	S can do 150 sums in the same time it takes P to do 100
	D.	P can do 150 sums in the same time it takes S to do 100

What is meant by "nonuniform partitioning" and why is it a problem? Reset Selection

Diminishing returns means that the more pipeline stages there are, the less benefit we get from adding more stages. Why is this? Reset Selection

Compare DRAM and SRAM. Check the true statements from the following:

	A.	DRAM is cheaper than SRAM
	B.	DRAM is faster than SRAM
	C.	you have to refresh (read and re-write) DRAM to keep values in it
	D.	you have to refresh (read and re-write) SRAM to keep values in it
	E.	DRAM is more likely to be used for main memory than for on-chip caches
	F.	SRAM is more likely to be used for main memory than for on-chip caches

Suppose a single address sent to the memory module retrieves 128 bits of data. That data is probably retrieved by Reset Selection

It is typical for the I/O Bridge to be connected to three buses: the system bus, the memory bus, and the I/O bus. It routes a signal between pairs of these busses; the figures on pages 569, 570, and 578 show examples of

• System-to-I/O (request disk read)
• I/O-to-memory (perform disk read)
• System-to-memory (memory write), and
• Memory-to-system (memory read)

What is an example of memory-to-I/O?

Reset Selection

Compare DRAM and SRAM. Check the true statements from the following:

	A.	DRAM uses more transistors per bit than SRAM
	B.	DRAM uses a capacitor to store a value
	C.	Typically a computer has more DRAM than SRAM

Reading a supercell takes two memory controller operations. In between the two the intermediate data is stored in Reset Selection

A disk never sends memory to the CPU itself, instead sending it to memory. How does the CPU discover the data is there?

Reset Selection

One reason that arrays can be faster than linked lists is that their elements are adjacent to one another in memory, where linked list elements may be scattered across widely varying addresses. This is an example of Reset Selection

Suppose you have a program that often needs several kilobytes of temporary memory. Re-using the same temporary memory each time can be faster than using different temporary memory each time because of Reset Selection

Consider two programs; one runs in a small loop, the other invokes several dozen functions each one. Assuming the amount of work is similar, the loop will almost certainly run faster. At least some of that speed difference is due to Reset Selection

"Cache" is pronounced like Reset Selection

If we find the data we want in a cache, we call that a Reset Selection

If we fail to find data in a cache because we have never accessed the data before, we call that a Reset Selection

If we fail to find data in a cache even though we access only a few bytes since we last accessed that same data, we call that a Reset Selection

If we fail to find data in a cache because we've read too much data since we last accessed that same data, we call that a Reset Selection

Consider a cache with 1-byte words, 4-word blocks, 2-line sets, and 64 sets in total. If addresses are 32 bits long, how large is the tag stored with each line? Enter your answer as a non-negative integer without leading zeros. ____

Consider a cache with 1-byte words, 4-word blocks, 2-line sets, and 64 sets in total. Ignoring metadata like valid bits and tags, how many bytes of data does the cache store? Enter your answer as a non-negative integer without leading zeros. ____

Suppose a cache can store 64KB of data and is organized with 2-line sets. What is the largest amount of data that cache can serve without encountering a conflict miss? Reset Selection

Assume that cache F is fully associative and cache D is direct-mapped. Assume the two caches have the same address space and the same total data capacity. Reset Selection

Process A accesses 32 bytes of data scattered in a deterministic but random-looking pattern across addresses 0x00 through 0xff. Assume that cache F is fully associative (using a least-recently-used policy) with 16 lines of 4 bytes each, and cache D is direct-mapped with 32 lines of 4 bytes each. Assume we A twice and measure the cache misses the second time. Reset Selection

Process A accesses 32 bytes of data in order evenly spaced across addresses 0x00 through 0xff. Assume that cache F is fully associative (using a least-recently-used policy) with 16 lines of 4 bytes each, and cache D is direct-mapped with 32 lines of 4 bytes each. Assume we A twice and measure the cache misses the second time. Reset Selection

Process A accesses 32 bytes of data scattered in a deterministic but random-looking pattern across addresses 0x00 through 0xff. Assume that cache F is fully associative (using a least-recently-used policy) with 32 lines of 4 bytes each, and cache D is direct-mapped with 32 lines of 4 bytes each. Assume we A twice and measure the cache misses the second time. Reset Selection

Process A accesses 32 bytes of data in order evenly spaced across addresses 0x00 through 0xff. Assume that cache F is fully associative (using a least-recently-used policy) with 32 lines of 4 bytes each, and cache D is direct-mapped with 32 lines of 4 bytes each. Assume we A twice and measure the cache misses the second time. Reset Selection

Loop unrolling is usually used to remove what source of inefficiency? Reset Selection

Inline substitution (also called "inlining") is usually used to reduce what source of inefficiency? Reset Selection

Using multiple accumulators is usually used to reduce what source of inefficiency? Reset Selection

Loop blocking is usually used to reduce what source of inefficiency? Reset Selection

Adding local variables is usually used to reduce what source of inefficiency? Reset Selection

Reassociation of operators is usually used to reduce what source of inefficiency? Reset Selection

Which of the following techniques depend on a pipelined processor's ability to work on several instructions at once, and thus would not work in a non-pipelined processor? Check all that apply.

	A.	loop unrolling
	B.	inlining
	C.	multiple accumulators
	D.	loop blocking
	E.	local variables
	F.	reassociation

Section 5.2 of the textbook discusses CPE (cycles per element, also called cycles per execution or cycles per instruction in other sources). Their discussion suggests that if I have code with 20 CPE and run it on a problem where my algorithm executes on 100 elements, I should expect the runtime to be: Reset Selection

When discussing virtual memory, a single page (check all that apply)

	A.	can be in-memory, on-disk, or unallocated
	B.	can be partly in-memory and partly not in-memory
	C.	contains a contiguous block of virtual addresses
	D.	is a fixed-size block of bytes
	E.	is mapped to a contiguous block of physical addresses

From the perspective of a running application, virtual memory looks like Reset Selection

From the perspective of the operating system, virtual memory looks like Reset Selection

As used by our textbook, a "cached" virtual page is one that is Reset Selection

What is the difference between "caching" a page, "swapping in" a page, and "paging in" a page? Check all that apply.

	A.	caching refers to the cache; the other two refer to memory instead.
	B.	swapping means some memory comes in and some other memory goes out; the other two can refer to something coming in without anything going out.
	C.	paging means moving an entire page of memory; the other two can refer to just parts of a page instead.
	D.	there is no difference; they mean the same thing