0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.