Suppose Tserial $=$ n and Tparallel $=$ n$/$p $+$ log$2($p$),$ As $($an example, suppose that $T_{\text{s}\text{e}\text{r}\text{i}\text{a}\text{l}}=n,$ where the units of $T_{\text{s}\text{e}\text{r}\text{i}\text{a}\text{l}}$ are in microsec$-$

onds, and $n$ is also the problem size. Also suppose that $T_{\text{p}\text{a}\text{r}\text{a}\text{l}\text{l}\text{e}\text{l}}=\frac{n}{p}+1.$ Then

$E=\frac{n}{p(\frac{n}{p}+1)}=\frac{n}{n+p}.$

To see if the program is scalable, we increase the number of processes$/$threads by a

factor of $k,$ and we want to find the factor $x$ that we need to increase the problem

size by so that $E$ is unchanged. The number of processes$/$threads will be $kp$ and the

problem size will be $xn,$ and we want to solve the following equation for $x$ :

$E=\frac{n}{n+p}=\frac{xn}{xn+kp}.$

Well, if $x=k,$ there will be a common factor of $k$ in the denominator $xn+kp=$

$kn+kp=k(n+p),$ and we can reduce the fraction to get

$\frac{xn}{xn+kp}=\frac{kn}{k(n+p)}=\frac{n}{n+p}.$

In other words, if we increase the problem size at the same rate that we increase the

number of processes$/$threads$,$ then the efficiency will be unchanged, and our program

is scalable.

There are a couple of cases that have special names. If when we increase the

number of processes$/$threads$,$ we can keep the efficiency fixed without increasing the

problem size, the program is said to be strongly scalable. If we can keep the efficiency

fixed by increasing the problem size at the same rate as we increase the number of

processes$/$threads$,$ then the program is said to be weakly scalable. The program in our

example would be weakly scalable.where times are in microseconds. If we increase p by

a factor of k$,$ find a formula for how much we$$ll need to increase n in order to maintain constant efficiency.

How much should we increase n by if we double the number of processes from $8$ to $16?$ Is the parallel program

scalable? I worked out that the efficiency equation would be E $=$ n $/(($n$/$p$)+$ p $*$ log$2($p$))$ but I am having trouble with the increasing by a factor of k aspect. I found an example in my textbook and from there got to E $=$ xn $/(($xn$/$kp$)+$ kp $*$ log$2($kp$))*$ kp$/$kp $.$ Can someone help?