C语言代写 | SP20 CIS341 final exam

C语言代写 | SP20 CIS341 final exam

Question set 1: C to Y86
The Euclidean Algorithm finds the greatest common divisor (GCD) between two numbers. Described in
circa 300BC, it is one of the oldest algorithms. Fascinating!
Match the Y86 instruction for each blank so that the complete assembly program is functionally identical
to the GCD function in C code. Assume that the two inputs to the GCD function, p and q, are non-
negative. [4 points for each correct match, -2 points for each incorrect match, minimum 0 points for this
problem]
// C program
long gcd(long p, long q){
if (p==q){
return q;
} else if (p>=q){
gcd(q, p-q);
} else {
gcd(q, p);
}
}
# Y86 program
gcd:
rrmovq %rdi, %rax
subq %rsi, %rax
jne gcd_elif
rrmovq %rsi, %rax
ret
gcd_elif:
———————– (a)
rrmovq %rsi, %rdi
rrmovq %rax, %rsi
call gcd
ret
gcd_else:
rrmovq %rsi, %rax
———————– (b)
———————– (c)
call gcd
ret

Question set 2: Cache hit/miss and coherence
Consider the following multi-core architecture. Each core has its own private cache, and both caches are
connected to the main memory. Both caches have the same configuration: 16B block size, 16 sets, and 1
way per set (direct-mapped). They also implement a write-back policy on a write hit and write-allocate
policy on a write miss.

Now, consider a series of memory accesses from the cores to its respective cache. Each memory
reference is labeled so that it indicates the core, the type (load or store), the address, and the size. For
example,
A: L 0x0, 4
For the given sequence of accesses below, indicate whether or not each access will result in either a 1)
cache hit, 2) cache miss and data shared by the other cache, or 3) cache miss and data read from
memory. (Hint: In addition to thinking of cache hits and misses, think of cache coherence protocol.) [3
points for each correct result, no incorrect penalty]
Assume that all addresses are physical addresses and caches are initially empty.
A: L 0x0300, 4
B: L 0x0308, 4
B: L 0x0100, 4
A: S 0x0304, 4
B: S 0x030c, 4

Question set 3: Data hazard
Consider a 5-stage single-issue pipelined Y86 processor that goes through fetch, decode, execute,
memory, and write-back stages. The processor is able to detect data hazards and implements both
stalling (and inserting bubbles) and data forwarding.
For the following example sequence of three instructions, each instruction is annotated whether or not
it will detect a data hazard during its pipelined processing.
irmovq \$10, %rax # No data hazard detected
mrmovq (%rax), %rbx # Data hazard detected with previous irmovq
instruction
addq %rcx, %rdx # No data hazard detected

Determine whether or not there is a data hazard for the following sequence of instructions. Assume
that the pipeline is initially empty. [3 points for each correct answer, no incorrect penalty]
irmovq \$16, %rax