title: Why would you modify the One-to-all algorithm to work for any number of processes, not just the powers of 2?
body: <p>The one-to-all broadcast algorithm for parallel computing is exponential. The idea is that you start with a single node and want to get the message from that node to all the other nodes in the hypercube. The hypercube itself is 2^k nodes. So starting with the root in the first step, you send that message to a single other node, then step two both those nodes send to 2 other nodes, then step three, those 4 nodes send to 4 other nodes, etc. This results in log2(p) steps for a p-node hypercube.
  <br />
  <br />
  I came across a problem in Introduction to Parallel Computing, Second Edition, which asks the reader to &quot;Modify (the algorithms) so that they work for any number of processes, not just the powers of 2.&quot;
  <br />
  <br />
  <a href="https://i.stack.imgur.com/gGH76.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/gGH76.png" alt="Algorithm 4.1 from the Introduction to Parallel Computing book. One-to-all broadcast algorithm" /></a></p>
  <p>Here is one of the algorithms. If I'm not mistaken the part which makes this work specifically for powers of 2, has to do with the mask := mask XOR 2^i and (my_id and 2^i) lines.</p>
  <p>Specifically why would we want this algorithm to work for none powers of 2? Since it is a hypercube which is some power of 2 amount of nodes, when would it occur and be beneficial for it to be some non power of 2 processes?</p>