Someone please explain how to do this. It's been a lifelong mystery that has always fascinated me:
>
By the end of that summer of 1983, Richard had completed his analysis of the behavior of the router, and much to our surprise and amusement, he presented his answer in the form of a set of partial differential equations. To a physicist this may seem natural, but to a computer designer, treating a set of boolean circuits as a continuous, differentiable system is a bit strange. Feynman’s router equations were in terms of variables representing continuous quantities such as “the average number of 1 bits in a message address.” I was much more accustomed to seeing analysis in terms of inductive proof and case analysis than taking the derivative of “the number of 1’s” with respect to time. Our discrete analysis said we needed seven buffers per chip; Feynman’s equations suggested that we only needed five. We decided to play it safe and ignore Feynman.
How is it possible to use PDEs to model boolean circuits?
Just today I was reminded of this paragraph when we thought about completely different discrete optimalization problem with the expectation that there must be some way to solve it analytically instead of numerically.
But in case of CM router, “the average number of 1 bits in a message address.” is surprisingly useful quantity, because for the most straightforward implementation of hypercube routing the number of one bits in address is equal to number of links the message must traverse. The algorithm is essentially this: find address bit set to one, clear it and send the message down the link with same number as was the order of that bit, if address is all zeros, message has reached the destination (the same thing can be implemented without changing the address seen on wire by each router XORing its node ID with address in message and getting the same bitvector, but I believe most implementations actually modify the message address in each router).
I think the "in respect to time" and "amount of bit" part is the continuum. You can then think of your communication as a stream and rate. Their computer had a million cores in it's original design, but each could only talk with ~20 nearest neighbors. Weirdly information might begin to mimic simple fluid dynamics in this environment.
I suspect that's why Feynman could build those equations as well as discover that they only needed the 5 buffers. Though I can fully sympathize with the program manager in not wanting to reason in terms of differentials.
There aren't enough details about but there are a lot of touch points between discrete mathematics and calculus. If you read Knuth's AOCP you'll see a lot of other examples where things like integrals are used in discrete math problems...
Have a really large number of circuits. It's the same as how you can use PDEs to model atoms. If you have enough atoms in the collection, you don't have to think about individual atoms.
The same way that you can use continuous Fourier transforms to model the discrete one. Or, for that matter, the way we use digital simulations to model all sorts of things.
My guess is that his calculations were akin to using a hash table to sort routing information and analyze the eviction patterns and probabilities over time?
> By the end of that summer of 1983, Richard had completed his analysis of the behavior of the router, and much to our surprise and amusement, he presented his answer in the form of a set of partial differential equations. To a physicist this may seem natural, but to a computer designer, treating a set of boolean circuits as a continuous, differentiable system is a bit strange. Feynman’s router equations were in terms of variables representing continuous quantities such as “the average number of 1 bits in a message address.” I was much more accustomed to seeing analysis in terms of inductive proof and case analysis than taking the derivative of “the number of 1’s” with respect to time. Our discrete analysis said we needed seven buffers per chip; Feynman’s equations suggested that we only needed five. We decided to play it safe and ignore Feynman.
How is it possible to use PDEs to model boolean circuits?