Can you use theoretical physics to design a city or a supercomputer? By caek in MLP Tue Jun 01, 2004 at 05:45:46 AM EST Tags: Science (all tags)
	If you've played Sim City you've wrestled with one of the problems faced by supercomputer designers. Unfortunately there's no GameFAQs.com for the technical staff at Japan's Earth Simulator or Srinidhi Varadarajan and colleagues at Virginia Tech. True enough, they won't have to deal with rising crime or Godzilla but, as hinted at in a recent paper in Journal of Physics A, the physical layout of a massively parallel supercomputer is fundamentally the same problem as minimizing the time commuters spent stuck in traffic jams. Cities and people are just too complicated for a complete and rigorous mathematical treatment of commuter behaviour. However, in spite of the simplifications made in What is the optimal shape of a city? by Carl Bender et al, their results provide food for thought for supercomputer designers and Sim Mayors. This article contains a summary of those results, some background on the techniques they used, and a critical assessment of the extent to which they can be applied.

What have supercomputers got to do with cities? A supercomputer usually contains multiple processors. These processors can work on different calculations (or different bits of the same calculation) simultaneously, which speeds things up. A common use of such supercomputers is to simulate climate change. Each processor is allocated a grid square of the Earth's surface, and passes it findings onto the processor in charge adjacent grid square. So for example, the Puerto Rico processor would give the North Carolina processor a heads-up that Hurricane Isabel was headed its way. Say you're using the supercomputer you keep in your garden shed to find z, where z = x + y, but x and y are unknown. The supercomputer might ask one of its processors to find x and another to find y. These processors would then send their values for x and y to a third processor (or each other), giving z. The choice of which processors are used is neither arbitrary nor simple, and is loosely known as scheduling. There are two factors to consider when scheduling a calculation. One is the physical location of the processor. Processors whose results are inputs into one another's calculations should be located closely together. This is because the time taken for them to communicate with each other is limited by physical separation. Although the electronics in a supercomputer are very fast, every nanosecond counts. In terms of our Hurricane example, the optimal allocation of processors would place the North Carolina processor close to the Puerto Rico processor, because whatever goes on in the atmosphere of Puerto Rico is likely to affect that of North Carolina. The other factor is simple but easily forgotten: a processor must be available. If it's busy working out how to make a cup of tea it can't help. Because a processor may not be free, it is usually necessary to allocate from an irregular set of processors, which makes minimizing physical separation much more complicated. In a supercomputer, there are thousands of processors (5120 in the case of the current Top of the Pops, the NEC-built Earth Simulator in Japan). These processors are configured in a three- or two-dimensional lattice. Here's the clever bit: consider the simpler two-dimensional case. Imagine each processor is a bulding, and the wires linking them are streets and avenues. If you define the the Manhattan distance as the sum of the North-South and East-West separation of two processors (or buildings), you can probably see the link between designing a city and a supercomputer; putting processors with common goals nearby is similar to making sure an office block has good transport links to a residential area. In the paper1 Bender et al write down an equation that gives the sum of the Manhattan distance between every point in their city. They use this sum as a metric of how optimally a city is designed. The smaller the sum, the shorter the average distance of all journeys. To minimize this sum they use variational calculus. If your response to that is, "Huh? They do what to who?", then the aside that follows is for you. An aside on the calculus of variations Variational calculus is a common tool in classical and quantum physics. It is used to find the stationary points of functions—those sweet spots where something is optimally small or large. The canonical example of the use of variational calculus is the brachistochrone problem. Imagine a frictionless wire with a bead threaded onto it. The brachistochrone problem asks how you should bend the wire (which is fixed at its ends) to minimize the time taken for the bead to slide down under gravity. To solve the problem you begin by obtaining an equation for the time taken for the bead to descend in terms of the shape of the wire. It's here that the variational calculus comes in: if you vary this shape then the time taken either increases, decreases or stays the same. The curve at which time stays the same is the minimum time. Problem solved.2 Another neat problem solved using variational calculus is the catenary. The catenary is the curve you get when you dangle a chain between two points. The world's best known (upside-down) catenary is the Gateway Arch in St Louis. These classic (and classical) problems have solutions which can be found analytically. This means that can be solved using nothing more than a pencil and paper and a little thought. This is possible because the solutions are relatively simple curves. But in the case of the problem tackled by Bender et al the solution is a more complicated curve so they had to resort to solving their equations numerically. This involves changing the curve by a tiny amount and checking what now comes out of the original equations. This often has to be repeated many, many times so a computer is used. Problems which can be solved analytically are able to skip this step. Many modern problems must be attacked with numerical methods. Although its modern use is often more hacky than it once was, variational calculus remains a useful tool in such diverse and sophisticated fields as quantum field theory, statistical physics and cosmology. Back to the paper Using variational calculus the authors find the optimal shape for their city, where the optimal shape is defined as that which minimizes the length of the average journey. Perhaps unexpectedly, this shape isn't a well known form such as a circle, diamond or square. In fact it's a 'rounded diamond' that is very close to being circular.3 This figure shows one quarter of the boundary of the optimal city. w(x) (solid line) is the optimal boundary, while the dashed line is a reference circle. They extend their model to include parks and lakes. Parks are regions of the city in which no one lives, but acrooss which you can walk. Lakes are regions in which no one lives and no travel is possible.4 Of course the exact shape of the optimal city containing a park or lake depends critically on the position and shape of the park, but their method is pressed into service to prove what you might expect: a Central Park in the middle of your city causes problems for commuters. Rounded diamonds for fun and profit Should you use this rounded diamond for your next new town or supercomputer? Unfortunately no; the results aren't yet terribly useful in these applications, as Carl Bender happily admitted to me when I discussed the paper with him for the purposes of this article. Together we identified the following limitations and unrealistic assumptions: Supercomputers are already built such that processors are as close together as possible. See for example, this model of the Earth Simulator. The blue cabinets in the centre are tightly packed processor nodes. The purple cabinets round the outside are the interconnection network responsible for shifting petabytes of date into and out of the core. The paper shows that the best way of doing this packing is a particular curve, but the difference in average separation between the optimal curve and a circle (0.02%) is negligible. Even the deviation from perfection for a square or diamond (2% or so) is small, and such configurations may be much easier to construct in practice. The model is continuous. In the model there is a building or processor at every point within the boundaries. In the real world these things are discrete entities. A discrete version of the model would give a different curve, which would certainly depend on the number of nodes. The results do not apply to three-dimensional supercomputers or cities. Cities in which continuous travel in three dimensions is possible do not yet exist, but the varying (and non-zero) height of buildings would also modify the results. The results are irrelevant to towns not laid out on a grid system. There a plenty of reasons to lay a new town out with perpendicular streets and avenues, not least the prospect of your home town turning into Stone Henge twice yearly, but pre-existing towns with such a layout are rare in Europe. Milton Keynes is a well-known and widely loathed exception. As any Sim Mayor knows, designing a city is not a matter of packing as many buildings into as small a space as possible and hoping for the best. Aesthetics, pollution, crime and quality of life are also considerations. Heat dissipation in a supercomputer is a similar real world practicality the model is forced to ignore. And finally So why did I bother to explain all this if the result is so useless? It's clear that, taken alone, the paper is meant to be little more than a diverting but incomplete solution to a toy problem. I chose to explain it here in some detail because it's a neat tour of a sophisticated mathematical technique used in serious theoretical physics, mathematics and elsewhere in terms of a couple of real physical situations we're all familiar with. The paper got me thinking about what we really want from our cities, and whether we can achieve that using hard-nosed science. For example, rules of thumb are currently used to determine how best to provide transport links for a given population density. Presumably these are derived from costly experience. Perhaps some number-crunching would save some money and time by answering these questions before a brick is laid.5 Creating accurate simulations of people is very difficult, and may even be impossible. However, there is no doubt that scientists working in many areas of quantitative science and computing are getting closer. At the very least these tiny steps provide ways for Will Wright to make Sim City 5 a little more realistic. Footnotes [1] I think What is the optimal shape of a city? is quite readable, so I urge anyone who is familiar with undergraduate-level calculus (and doesn't consider PDF unfit for human consumption) to have a go. As is usual for theoretical papers, the introduction and concluding sections are particularly accessible. [2] The full proof of the solution is given on Mathworld. By one of those delightful mathematical coincidences that send people potty, the curve turns out to be the line drawn when you fix a piece of chalk to the rim of a wheel and roll it against a wall. [3] This rounded diamond (or oblate circle) is a special case of the curve approximately described by the equation y = (2 - |x|d)1/d, where d = 1.81546. Other special cases of this curve are the diamond (d = 1, around 1.5% off optimal), the circle (d = 2, around 0.02% off optimal) and the astroid (d = 2/3, around 5.5% off optimal). An astroid is curve described by a ladder sliding down a wall. [4] Parks perhaps correspond to areas of a supercomputer used for things other than number-crunching (I/O, storage). Lakes might by an area of the supercomputer that is down for repairs. [5] Variatonal methods aren't the only tools being applied to urban planning. In another branch of theoretical physics altogether, Milan Krbalek and Petr Seba are trying to decompose the problem of traffic flow in congested Mexican cities using tried and tested methods from from random matrix theory and computational physics.

Poll

Most important thing to consider when designing a city Commuting distance/time 12% Recreational facilities 8% Architechture, beauty 16% Density of police stations, fire stations, schools 6% Vulnerability to Godzilla/Mothra attack 30% Presence of titty bars 28% Votes: 50 Results | Other Polls

Related Links

GameFAQs.c om Earth Simulator Srinidhi Varadarajan and colleagues a recent paper in Journal of Physics A What is the optimal shape of a city? Hurricane Isabel how to make a cup of tea Top of the Pops Earth Simulator [2] Manhattan distance the paper 1 brachistoc hrone problem 2 catenary Gateway Arch 3 This figure 4 Central Park new town model of the Earth Simulator do not yet exist your home town turning into Stone Henge twice yearly Milton Keynes rules of thumb 5 Will Wright little more realistic PDF unfit for human consumption Mathworld send people potty the line drawn when you fix a piece of chalk to the rim of a wheel and roll it against a wall astroid Milan Krbalek and Petr Seba are trying to decompose the problem of traffic flow in congested Mexican cities Also by caek