When a program is adapted to run on multiple processors in a multiprocessor system, the execution

time on each processor is comprised of computing time and the overhead time required for locked critical sections

and$/$or to send data from one processor to another. Assume a program requires t $=300$s of execution time on one

processor. When run on p processors, each processor requires t$/$p s$,$ as well as an additional $6$ s of overhead $($to$),$

irrespective of the number of processors.

a$.(15$ points$)$ Compute the per$-$processor execution time for $2,4,8,16,32,64,128,$ and $256$ processors.

b$.(15$ points$)$ For each case, list the corresponding speedup relative to a single processor S$,$ and the ratio

between actual speedup versus ideal speedup, R $($speedup if there was no overhead$).$ How does S and R

change with respect to p$?$

c$.(15$ points$)$ Assume now the overhead increases with the number of cores such that overhead to

$=2$p seconds

$($e$.$g$.,8$ processors will have an overhead of $16$s$).$ How much speed$-$up is achieved using $150$ processors

compared to a single processor? Explain your answer.