3
$\begingroup$

If there are n threads with m instructions in each thread, when these threads are run concurrently how many possible interleavings in instruction execution are possible?

2 Answers 2

6

There are altogether $nm$ instructions. There are $\binom{nm}m$ ways to pick which $m$ slots in the sequence of $nm$ instructions are occupied by the $m$ instructions in thread $1$. Once those are chosen, there are $\binom{nm-m}m$ ways to pick which of the $m$ remaining slots are filled by the instructions in thread $2$, then $\binom{nm-2m}m$ ways to pick the $m$ slots for thread $3$, and so on. In general, for thread $k$ you’ve already filled $(k-1)m$ slots, so there are $\binom{nm-(k-1)m}m$ ways to pick the slots for thread $k$. The total number of interleavings is the product of these numbers, $\begin{align*} &\binom{nm}m\binom{nm-m}m\binom{nm-2m}m\dots\binom{2m}m\binom{m}m =\\\\ &\frac{(nm)!}{m!(nm-m)!}\cdot\frac{(nm-m)!}{m!(nm-2m)!}\cdot\frac{(nm-2m)!}{m!(nm-3m)!}\cdot\dots\cdot\frac{(2m)!}{m!m!}\cdot\frac{m!}{m!}=\\\\ &\frac{(nm)!}{(m!)^n}. \end{align*}$

This multinomial coefficient is also written ${nm \choose m,m,\ldots,m},$ where there are $n$ entries in the bottom row.

4

There are $(nm)!$ ways to order the full set of $nm$ instructions. This is a product of $m!$ ways to order the instructions in each individual thread (i.e., a factor of $(m!)^n$), times the requested number of ways to interleave the threads. We conclude that there are $ \frac{(nm)!}{(m!)^n} $ ways to interleave the threads.

An alternate derivation is to start with $nm$ slots for the instructions, then choose $m$ in which to place the first thread's instructions, $m$ of the remaining slots in which to place the second thread's instructions, and so on. This gives the result $ {{nm}\choose{m}}\times{{nm-m}\choose{m}}\times {...} \times{{2m}\choose{m}}, $ or $ \frac{(nm)!}{m!(nm-m)!}\times\frac{(nm-m)!}{m!(nm-2m)!}\times{...}\times\frac{(2m)!}{m!m!}, $ which is the same as before: the only terms that don't cancel are the $(nm)!$ in the numerator and the $n$ copies of $m!$ in the denominator.