SDP10 Final - Part I

A branch instruction

In binary, the number 1/3 is 0.01010101 . . .. In the following, assume that x is an int and y is a short. (short)((0x5555 * (int)y)>>16) and y/3 could differ even when neither computation overflows

A callee-saved register should be saved before it is written to in a procedure

In binary, the number 1/3 is 0.01010101 . . .. In the following, assume that x is an int and y is a short. For each x there exists some integer w (which may be different for different xs) such that abs(x/3 - q) < 10, where q = (((0x55555555>>w)*x)>>(32-w)).

In the FDEMW five-stage pipeline we analyzed in class, if we want to stall memory how many pipeline registers should be given the "stall" signal?

A CPU register file is a small storage device that

In the FDEMW five-stage pipeline we analyzed in class, if we want to stall decode how many pipeline registers should be given the “normal operation” signal?

A memory leak is caused by a

In the two's complement number representation, a negative number with more leading ones is larger (i.e. less negative) than a negative number with fewer leading ones.

When shifting a two’s complement number to the left, an overflow can only occur if the number is negative, since positive numbers have a zero in the leftmost bit

A program cannot accidentally use another program's memory space and "crash" a computer that uses (see the img)

1- virtual memory address

2- program relocation

3- separate instruction and data caches

In x86 assembly, the eax register can be used to hold integers but not addresses.

A program written directly in machine language (binary) would run faster than the same program written in assembly code and then assembled.

Initially byte i of memory is i + 0x20 (mod 256), %eax contains the number 3, and %ebx contains the number 5. What is in %ebx after running x86 movl (%eax), %ebx?

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

Asserting a word line and asserting (to "high" voltage) a bit line writes a 1 to a DRAM cell)

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

Jump tables, such as are used for switch statements, require that the new PC be determined by a memory read. Suppose we added an assembly instruction memjump accepting a single memory address as its parameter, like memjump (%eax). In the five-stage example pipeline (F D E M W), for how many cycles will we need to bubble and/or stall stage F after executing a memjump?

Let f32 be the number of distinct numbers that can be represented in 4-byte IEEE-style floating point and u32 be the number of distinct numbers that can be represented as unsigned 4-byte integers. Which of the following is true?

Let s8 be the number of distinct numbers that can be represented as signed (two's complement) 1-byte integers and u8 be the number of distinct numbers that can be represented as unsigned 1-byte integers. Which of the following is true?

Assume x is the most positive signed integer. What is x + 1?

Logical address is calculated by: segment.base + eff_addr

Assuming the standard IEEE-style bias, what is the smallest number of bits a float point number could have and represent the number −29/4 exactly?

Buses are typically designed to transfer fixed-sized chunks of bytes known as

Capacity misses are typically discussed in connection with?

Check the following (listed in alphabetical order) in order of importance when optimizing code that operates on very large arrays: B = Body of loop optimization (function inlining, efficient math), C = Cache locality, O = big-O of algorithm used

Compare the size of int and int*

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

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

Programs with good ______ ______, tend to access a referenced memory location multiple times in the near future.

Putting \#include "foo.h" in your C file is the equivalent of typing the contents of foo.h into your file

Compiling C into x86 assembly comprises translating each C statement into a single assembly instruction.

Conflict misses are typically discussed in connection with?

Rank the following in order of significance when writing code that deals with large arrays:
- Algorithmic efficiency (i.e., big-O),
- Computational efficiency (e.g., loop unrolling, inlining, etc),
- L cache Locality.

CPE (cycles per element, also called cycles per execution or cycles per instruction in other sources). If we 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

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

Register %edx is one of the "callee-save" registers. This means that if procedure baz calls procedure xyxxy

Register %esi is one of the "caller-save" registers. This means that if procedure baz calls procedure xyxxy

Dirty bits are associated with (pick the best answer)

Edsger Dijkstra wrote "Go To Statement Considered Harmful" in 1968 in which he argued (translated into current language) that code that uses goto becomes needlessly hard to read and maintain compared to only using if and while. In assembly, we use the goto-like jump instructions extensively; the main reason for this is?

Every procedure in an x86 assembly program must be declared using .globl

Which of the following is a good reason (are good reasons) to equip the CPU with small amounts of fast memory?
I. To make the design of the compiler simpler
II. To make some CPU instructions smaller
III. To make some CPU instructions faster

Given 6-bit numbers where 010001 + 001010 = 010110, which of the following describes the number representation used?

Given 6-bit numbers where 010101 + 000001 = 010110, which of the following describes the number representation used?

Good software design includes writing procedures for code you might otherwise repeat in-line. Pulling code into procedures can help some branch predictors; how else can it improve your program’s performance and/or your compiler’s ability to optimize your code?

Return from function issues a bubble in pipeline.

Good software design includes writing procedures for code you might otherwise repeat in-line. Pulling code into procedures involves call/return overhead; how else can it hurt your program's performance and/or your compiler's ability to optimize your code?

SRAM is "static" in the sense that if the power is turned off, SRAM will continue to store data (e.g. as in flash memory in MP3 players or USB thumb drives).

Suppose addresses A and B have different tags but the same index (for those caches that have tags and indexes, that is). Assume the cache is empty prior to the accesses listed in the questions. In the access pattern "read A, then read B, then read A, then read B" the second read of A will be a miss for?

How does knowing you have a pipelined processor change the code you write?

Suppose addresses A and B have different tags but the same index (for those caches that have tags and indexes, that is). Assume the cache is empty prior to the accesses listed in the questions. In the access pattern "read A, then read B" the read of B will be a miss for

How is "-1" (decimal) represented in an 8-bit 2's complement binary format?

Suppose page table entries are 8 bytes long and virtual addresses are 32 bytes long. If each page table is to fit on a single page, what is the smallest pages can be if we have a 2-level page table hierarchy?

How is 46 (decimal) represented in an 8-bit 2's complement binary format?

How is -10 (decimal) represented in an 8-bit 2's complement binary format?

Which of the following move operations is the following instruction an example of movl (%edx), (%eax)?

In the access pattern “write A, then write B, then write A”, to minimize
writes to the higher-level cache we should pick which of the following?

How many hex digits are needed to represent the decimal number 67?

How many ints fit inside x if x is declared as int *x = malloc(8); ? Word size is 4.

Which of the following move operations is the following instruction an example of movl (%edx), %eax?

How many rules do Unix linkers use for dealing with multiply defined symbol

Suppose an array of char (8-bit values) {0x12, 0x34, 0x56, 0x78} is stored at address 0x24 of a little-endian computer. What byte is stored at address 0x26?

If a computer has 8GB memory, a single 1MB cache, and 4KB of registers, the total amount of data it can store is?

Suppose the 32-bit value 0x12345678 is stored at address 0x24 of a big-endian computer. What byte is stored at address 0x23?

If a wire carries a logical value of 0, its voltage level will be 0 Volts.

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

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

Suppose the 32-bit value 0x12345678 is stored at address 0x24 of a big-endian computer. What byte is stored at address 0x25?

If we were running a non-pipelined processor (like SEQ) with a real memory system, which of the following optimization strategies would no longer provide a speed benefit?

The .data section of an x86 assembly program is used to specify the parameters for each procedure.

In C, a pointer variable is used for storing an address

If x is the most negative signed integer, what is -x?

In a DRAM, all cells have to be periodically refreshed, not just the ones that have been read.

In a program with good ____________, if a memory location is referenced once, then the program is likely to access nearby memory locations in the near future

The ASCII code for the character 'B' is 0x42. What is the ASCII hex code for the character 'D'?

If we were running a non-pipelined processor (like SEQ) with a real memory system, which of the following optimization strategies would not longer provide a speed benefit?

In C, local variables allocated inside functions are allocated:

In C, using default floating point settings, a special value of "infinity" is computed when

The ASCII code for the character 'B' is 0x42. What is the ASCII hex code for the character ‘E’?

The assembly instruction int x used to make system calls only accepts a 1-byte (256-value) argument x, but Linux uses it to support over 300 system calls. How does it do that?

The contents of how many program registers are modified by an assembly push operation?

The difference between the SAR (arithmetic shift right) and SHR (logical shift right) operations is that SAR puts a one into the leftmost bit after a shift and SHR puts a zero.

The EBP is a callee-saved register.

The EFLAGS register contains the zero flag and the sign flag?

What is the value of the following C expression? x=0x1234 and y=0x3 ((x >> y) << y)

The hardware is aware of the program stack

The instruction addq %rax, %rbx changes what?

What is the value of the following C expression? x=0x00 and y=0xA5 x && ~y

The instruction cmp eax,ebx (or cmp %ebx,%eax in AT&T syntax) computes the value of EAX - EBX.

_______ - program transformation that reduces the number of iterations for a loop by increasing the number of elements computed on each iteration

The valid bit is associated with

It is possible to explicitly specify the number of threads to be created in the team, using the _____ attribute:

CPU optimized for throughput

The working set of a program is formed by

This problem occurs when a larger type is converted into a smaller type or with the signed-unsigned operations?

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

169. In C a single statement that performs the equivalent of y=x*100; but without using the multiply operator (*);

We can encode the C command a ? b : c, where all three variables are of type int,

We say that pipelining generally increases latency. That statement means (select all that are part of the definition of "increases latency")

The bitwise and operation (& in C) can be used to flip the bits of a word

Linking can be performed at

Parallel processing mechanisms to achieve parallelism in uniprocessor system are:

The _______ directive causes threads encountering the barrier to wait until all the other threads in the same team have encountered the barrier.

How is 148 (decimal) represented in a 16-bit 2’s complement binary format?

In a Compare the runtime of y = x * 5 and y = (x<<2) + x, measured by the time it takes for the resulting value of y to be available somewhere in the pipeline.

What is the difference between 15 and $15?

What is the value of the following C expression? x=0xA0 and y=0x0F ~x||~y

Which of the five phases determines how many bytes long an instruction is?

Which of the five phases determines what the next PC is?

Which of the five phases determines the destination register for instructions that write to registers?

Which of the following computations may be performed by exactly one CPU instruction? (img)
a = 5;
a = b + c * 5;
for (i = 0; i < 10; i += a[i++]);

Which of the following is true?

Which of the following manages the transfer of data between the cache and main memory

Which of the following manages the transfer of data between the CPU registers and the cache

Which of the following registers is the lower order 16 bit register of register %ecx?

Which of the following statements about alignment within C struct's is true?

Which one of the following IA32 registers is typically used for stack management?

Which one of the following optimizations does not provide any speed benefit for a non-pipelined processor, such as SEQ?

Which of the following levels of a typical memory hierarchy transfers data in chunks of smallest size?

If we cut power for one millisecond, which of the following is true?

If we cut power for one minute, which of the following is true?

Select the most correct statement from the following as applied over the last two decades:

Which one of the following optimizations does not provide any speed benefit for a
non-pipelined processor, such as SEQ?

Consider a direct-mapped cache with 256 sets and 16 byte blocks. In this cache the address 0x12345 maps to the same set as which of the following addresses?

A & B is the bitwise version of A && B; A | B is the bitwise version of A || B; which of the following is the bitwise version of A == B?

The unary & operator returns (in C language)

In C a single statement that performs the equivalent of y = x *100, but without using the multiply operator (*)

Adding local variable is usually used to reduce what source inefficiency?

Which of the following code snippets is fastest? Assume n is very large (more than ten thousand).

Which of the following code snippets is fastest? Assume n is very large (more than ten thousand).

How is 148 (decimal) represented in a 16-bit 2’s complement binary format?

Which of the following code snippets is fastest? Assume n is very large (more than ten thousand).

In a Compare the runtime of y = x * 5 and y = (x<<2) + x, measured by the time it takes for the resulting value of y to be available somewhere in the pipeline.

The program counter contains:

A memory leak is caused by a:

Registers and cache memory are the same thing

In C, local variables allocated inside functions are allocated:

What is the value of the following C expression? x=0xA0 and y=0x0F ~x || ~y

How is 215 (decimal) represented in a 16-bit 2's complement binary format?

____ involve identifying a computation that is performed multiple times (e.g., within a loop), but such that the result of the computation will not change.

In C, for the expression (x | THE_MASK), where THE_MASK has at least one bit that is not zero, the result will be zero if all the bits of x are zero.

What is the value of the following C expression? x = 0x128 and y = 0x2 ~x << y (in hex)

In C, using default floating point settings, a special value of "infinity" is computed when:

GPU optimized for latency.

If you don’t explicitly specify the number of threads (OpenMP) how many thread will be executed?