Amdahl$$s law assumes that the sequential portion of execution cannot be sped up and

that the parallel portion can be indefinitely parallelized. In more general models, both

assumptions can be relaxed: some parallel segments might have limited parallelism and

there are techniques to speed up the execution of sequential sections $($as we will see later

in the course$).$

Assume you have a multi$-$core processor with n Cores. You can configure the system

before running a program so that r cores work together as a single larger r$-$Core that can

run sequential code $$

r times as fast as a primitive core; the resulting system therefore

will have one r$-$Core and n $$ r primitive cores.

You have an application that runs in three phases. Phase $1(20\%$ of computation$)$ is

sequential; Phase $2(50\%$ of computation$)$ is linearly and indefinitely parallelizable while

Phase $3(30\%$ of computation$)$ can be linearly parallelized up to $3$ ways. Assume that

parallelization adds no overhead.

$($a$)$ For the application on a system with one r$-$Core and n $$ r primitive cores $($n $>=$

$1,$ n $>=$ r$),$ give the general formula for the speedup over sequential execution on a single

primitive core.

$($b$)$ Find the optimal r that offers the highest possible speedup for the following systems:

n $=2,$ n $=4$ and n $=16$