# In multithreaded computations, how does parallelism, slackness and speedup affect the running time?

In the CLRS book it mentions that during some world-class multithreaded chess-playing program, developers had to prototype their program on a 32-processor computer then run it on a supercomputer with 512 processors.

• A program was designed with a work of $$T_1 = 2048$$ and a span of $$T_{\infty} = 1$$.
• Then developers tried to optimize it by reducing work to $$T^{'}_1 = 1024$$ and increasing span to $$T^{'}_{\infty} = 8$$.
• Developers realized that while this optimization will speed-up the running time on a 32-processors from $$65$$ to $$40$$, it will slow it down on 512-processors from $$5$$ to $$10$$.
• The optimization idea was abandoned.

• The formula they used to determine the running time was $$T_P = T_1/P + T_\infty$$.

We have lower-bounds on the running-time $$T_P$$ according to the work law and the span laws $$T_p \ge T_1/P$$ and $$T_P \ge T_\infty$$, and an upper-bound of $$T_P \le T_1/P + T_\infty$$ using a greedy scheduler. So the formula used by developers to determine running time makes sense. However I don't see any connection between the running time and parallelism, slackness or linear speedup.

In my understanding and according to the book:

Parallelism: ($$T_1/T_\infty$$) provides an upper-bound on maximum possible speedups on $$P$$ processors.

Slackness: ($$\frac{T_1/T_\infty}{P}$$) indicates how close we are from achieving perfect-linear-speed-up, with values below 1 meaning that it's impossible to achieve and greater than 1 means we are closer.

Speedup: ($$T_1/T_P$$) indicates how much faster we can run computations on $$P$$ processors rather than one.

For each $$P$$ number of processors we have:

$$P = 32$$:

1. $$T_1 = 2048$$ and $$T_\infty = 1$$:
• Running Time: $$T_P \ge Max\{T_1/P, T_\infty\} = 64$$
• Parallelism: $$T_1/T_\infty = 2048$$
• Slackness: $$(T_1/T_\infty)/P = 64$$
• Linear speedup: $$T_1/T_p \le 32$$
2. $$T^{'}_1 = 1024$$ and $$T^{'}_\infty = 8$$:
• $$T^{'}_P \ge Max\{T^{'}_1/P, T^{'}_\infty\} = 32$$
• $$T^{'}_1/T^{'}_\infty = 128$$
• $$(T^{'}_1/T^{'}_\infty)/P = 4$$
• $$T^{'}_1/T^{'}_p \le 32$$

$$P = 512$$:

1. $$T_1 = 2048$$ and $$T_\infty = 1$$:
• $$T_P \ge Max\{T_1/P, T_\infty\} = 4$$
• $$T_1/T_\infty = 2048$$
• $$(T_1/T_\infty)/P = 4$$
• $$T_1/T_p \le 512$$
2. $$T^{'}_1 = 1024$$ and $$T^{'}_\infty = 8$$:
• $$T^{'}_P \ge Max\{T^{'}_1/P, T^{'}_\infty\} = 8$$
• $$T^{'}_1/T^{'}_\infty = 128$$
• $$(T^{'}_1/T^{'}_\infty)/P = 1/4$$
• $$T^{'}_1/T^{'}_p \le 128$$

On the prototype computer $$P=32$$, speedup remained the same before and after optimization, while parallelism and slackness decreased. On the supercomputer $$P=512$$, speedup, parallelism and slackness has all decreased. How can someone interpret these values in term of running time?