Reference no: EM133257883
case: The purpose of this question is to show that details of a computing system can impact what algorithms we prefer to use. Consider a computing system where memory accesses to the cache are 20 times faster than random access memory (RAM) access. Now consider the memory resources that two algorithms require for processing an input of size N.
> Algorithm 1 requires fc1(N) = 10N cache accesses and fR1(N) = sqrt(N) RAM accesses.
> Algorithm 2 requires fc2(N) = 3N cache accesses and fR2(N) = N RAM accesses.
Algorithm 1 uses more cache accesses than Algorithm 2, but fewer RAM accesses.
Question 1: Because RAM is 20 times slower than cache, we can interpret RAM accesses as analogous to 20 cache accesses. Compute f1(N) = fc1(N)+20fR1(N) and f2(N) = fc2(N)+20fR2(N).
Question 2: For small values of N, f2(N) is faster (smaller); for large values of N, f1(N) is faster. Compute N* for which f1(N*) = f2(N*). You need not compute an actual number for N*; an expression such as N* + 100/sqrt(N*) = log2(N*) is fine.
Question 3: This question assumes that the cache is 20 times faster than RAM. What if it the cache is 10 times faster than RAM, 40 times faster? Discuss (there is no need for detailed calculations) whether the break-even point, N*, will become larger or smaller.