How could Feynman have modeled this computer routing problem with partial difference equations?

109 Views Asked by At

In the 1980s, Richard Feynman worked at The Thinking Machine Corporation. This article by founder Daniel Hills talks about his experience with Feynman.

Hills mentions that Feynman was able to analyze a computer router using partial difference equations:

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.

One continuous quantity Feynman measured was “the average number of 1 bits in a message address”:

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.

He even did some sort of optimization to find the minimum number of buffers needed:

Our discrete analysis said we needed seven buffers per chip; Feynman's equations suggested that we only needed five.

The 64,000 different processors of the machine were laid out in a 20-dimensional hypercube. The router’s job was to hold onto the messages between processors in a buffer until a path became free.

The router of the Connection Machine was the part of the hardware that allowed the processors to communicate. It was a complicated device; by comparison, the processors themselves were simple. Connecting a separate communication wire between each pair of processors was impractical since a million processors would require $10^{12}$ wires. Instead, we planned to connect the processors in a 20-dimensional hypercube so that each processor would only need to talk to 20 others directly. Because many processors had to communicate simultaneously, many messages would contend for the same wires. The router's job was to find a free path through this 20-dimensional traffic jam or, if it couldn't, to hold onto the message in a buffer until a path became free. Our question to Richard Feynman was whether we had allowed enough buffers for the router to operate efficiently.

My question is, how could Feynman have modeled such a system using partial differential equations? I’m not asking exactly how he did it, because there probably aren’t enough details in the description. But is it possible, using some basic assumptions to fill in the gaps, to show how he could have done it, at the level of someone like me who took undergraduate ordinary and partial differential equations? For example, how we could model bits continuously and optimize for minimum number of buffers?

If it’s not possible to guess how Feynman would have modeled this system, are there any references showing how to do a continuous analysis of a discrete computer system? Maybe some textbooks in electrical engineering or computer science?