1
$\begingroup$

I was trying to understand why the equation $y_i = \left( \frac{n}{w} \right) + (i \pmod w) $ describes the step property in a balancing network?

First, recall $x_i$ to be the number of tokens a network gets as input and similarly $y_i$ to be the number of output tokens. Recall that a balancing network is just a network that distributes tokens to its output.

I was reading the art of multicore programming and in page 272 it says:

If the number of tokens n is a multiple of four (the network width), then the same number of tokens emerges from each wire. If there is one excess token, it emerges on output wire 0, if there are two, they emerge on output wires 0 and 1, and so on. In general,

$$ n = \sum x_i $$

then

$$y_i = \left( \frac{n}{w} \right) + (i \pmod w) $$

we call this property the step property.

It also defines equivalent ways to see the step property as:

  1. For any $i<j$, $0 \leq y_i - y_j \leq 1$

i.e. as we go up the output wires, the wire can only increase one step at a time or not increase (so top values are always larger or equal). An example:

enter image description here

However, the formula $y_i = \left( \frac{n}{w} \right) + (i \pmod w) $ doesn't make sense to me also, specifically the following doesn't make sense:

if there are two, they emerge on output wires 0 and 1, and so on...

I tried plugging in the numbers too say, $ n = 6 $, but the results don't quite make sense.

For example according to the formula above we get:

$$ y_0 = \left( \frac{6}{4} \right) + (0 \pmod 4) = 1 + 0 = 1 $$ $$ y_1 = \left( \frac{6}{4} \right) + (1 \pmod 4) = 1 + 1 = 2 $$ $$ y_2 = \left( \frac{6}{4} \right) + (2 \pmod 4) = 1 + 2 = 3 $$ $$ y_3 = \left( \frac{6}{4} \right) + (2 \pmod 4) = 1 + 3 = 4 $$

which doesn't agree with what the picture of the diagram would be because it seems to be backwards. Not sure if I made a mistake or misunderstood the formula, but it should be giving something as in the figure/diagram/picture from the book. Also, according to the formula, is it ever possible for it be equal? It seems to always increase in the wrong direction.

$\endgroup$
2
$\begingroup$

The formula is wrong. The correct formula is $$ y_i = \lfloor \frac{n}{w} \rfloor + [i < (n \mod{w})], $$ where $[C]$ equals 1 if $C$ holds, and 0 otherwise.

Sometimes books contain mistakes. When you see a mistake, correct it and proceed. No need to ask us for permission.

$\endgroup$
  • $\begingroup$ thanks again! Sometimes, when Im confused or just learning a new concept, I can't tell if I'm confused, wrong or have a severe misunderstanding. Hence, my question. :) Also, did you meant i - m I believe, not sure what < would do here... $\endgroup$ – Charlie Parker Nov 19 '15 at 23:46
  • $\begingroup$ No, I meant what I wrote. I also explained the semantics of $<$. $\endgroup$ – Yuval Filmus Nov 19 '15 at 23:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.