Chaotic Computing

In chaotic computing, anarchy rules OK Push a microchip to the limits and it performs in ways unimaginable with ordinary silicon, says Duncan Graham-Rowe Duncan Graham-Rowe BEACH holiday a washout? Camping trip cut short by gales? Cheer up every storm cloud really does have a silver lining. It seems that the unpredictable behaviour of our weather could hold the key to the future of computing. If you don't believe it, talk to William Ditto, a physicist at the University of Florida in Gainesville. Along with a team of colleagues in India and the US, Ditto has spent more than 10 years conjuring up the electronic equivalent of chaotic weather systems and harnessing them to build the next generation of computer processors. In the precisely designed world of computer chips, this is an unconventional approach: any chaotic behaviour is usually seen as a Bad Thing. After all, there's little point building a chip if its carefully regulated signals decay into anarchy as soon as it is switched on. However, Ditto and his colleagues believe that such anarchy can yield huge rewards, if used in the right way. To prove it, they have harnessed chaotic oscillations to create "chameleon" logic circuits that can switch their behaviour on the fly. In the space of a nanosecond or two, these morphing circuits can transform themselves from a processor unit, say, into a graphics controller. A "chaotic" computer built from circuits like these would be able to make far better use of its precious hardware than today's machines. By throwing all its computational firepower at the task in hand, and then reassigning it the instant a different task comes along, chaotic processor chips would be hugely more powerful than conventional chips of the same size. They would even be able to repair themselves. Ditto has founded a company to commercialise the technology, but in the meantime he is pursuing another application. His team has come up with a way to use these circuits to store data, creating digital memory that is far more compact than conventional memory and which can also retrieve data more quickly. This makes it perfect for systems that handle huge databases, such as internet search engines, Ditto says. The fruits of this work should go live this year, in the form of a chaotic search engine for a commercial customer's private use. The idea of chaotic computing emerged from a chance meeting in 1997.

Ditto, then working at Georgia Institute of Technology in Atlanta, was at a conference in Bangalore, India, when he bumped into Sudeshna Sinha, who was studying non-linear dynamics at the Institute of Mathematical Sciences in Chennai. As they talked, it emerged that they were both intrigued by other researchers' attempts to adapt quantum mechanics and DNA chemistry to perform traditional computing tasks, and they began to wonder whether chaos could offer any advantages. Chaotic behaviour is all around us - in the way that rivers flow and weather evolves, for example. While the behaviour of such systems is inherently unpredictable over all but the shortest timescales, they are not random. Their unpredictability arises because they are sensitive to the smallest of influences. Tiny fluctuations get amplified and eventually dominate the system. As chaos pioneer Edward Lorenz put it, the flap of a butterfly's wings in Brazil could set off a tornado in Texas. This is a problem for long-term weather forecasters, but Ditto and Sinha reasoned that if they could construct a circuit that behaved in a chaotic manner, then they might be able to use this sensitivity to their advantage. On a whim, they began to sketch out a design. Deliberately creating chaos rather goes against the grain for electrical engineers. Though students are often taught how to build circuits that behave chaotically, this is for one reason only: so that they will know how to avoid chaotic behaviour in the circuits they design later in their careers. The challenge is that chaotic signals can form spontaneously in devices like amplifiers, seeded by nothing more than background noise. This produces an oscillating current that can quickly swamp the desired signal. Because of the apparent randomness of their output, these circuits are sometimes used in random number generators. Ditto reasoned, however, that beneath the chaos the output is cycling through a set of predictable voltages, and by nudging the circuit he ought to be able to stabilise it into any one of a number of states. This could be used to construct a logic gate. Logic gates are the building blocks of computer processors. There are several types, each one producing a different digital output from a particular combination of 1s or 0s that it receives at its inputs. A NOR gate, for example, generates an output of 0 with any input values, unless both are 0. If Ditto and Sinha could mimic such behaviour by stabilising the oscillations in a chaotic circuit, it could bring some unique advantages. Stabilise the chaos in one particular pattern and they might be able to create the equivalent of a NOR gate. Stabilise it in a different pattern and they might get the equivalent of a NAND gate, which outputs a 1 unless both inputs are 1.

In 1998, Ditto and Sinha outlined their theory in a paper called "Dynamics based computation" (Physical Review Letters, vol 81, p 2156) and started to flesh out the idea. By 2002 they had published detailed results of computer simulations showing how such a device might function. They envisioned a chaotic logic gate with two inputs and one output like a conventional gate, but made up of a chaotic element they call a "chaogate". When the chaogate receives its input signals, the internal chaotic circuit begins to oscillate, rapidly stabilising at a value that depends on the inputs and, crucially, a control signal. The control signal has two components. The first is a fixed "bias" voltage which, along with the gate inputs, directs the circuit's chaotic oscillations into a particular pattern. The second component monitors the circuit and triggers an output when the chaotic oscillations reach the desired threshold voltage (see diagram). According to the team's calculations, simply changing the settings of the control signal would allow them to morph a chaogate into any logic gate they wanted. By 2005 they had constructed a prototype gate that behaved as they envisaged (Physics Letters A, vol 339, p 39). It was large, requiring roughly 1000 transistors - about 100 times as many as a conventional logic gate - but they showed it could morph from a NOR gate to a NAND gate in about a nanosecond. "We don't design NAND, NOR and AND gates," Ditto says, "they are already there." The chaogate takes the rich pattern of chaotic behaviour and selects the bits that are required. Ditto has set up a company called Chaologix to commercialise the concept and is building prototype circuits using manufacturing technology similar to that used in conventional chip-making plants. At the moment, their gates require around 120 transistors - 100 in the control circuit and 20 in the gate circuit - but the number is shrinking all the time, Ditto says. The latest design uses just two transistors for the chaotic circuit with another 20 in the control circuit. So where might we expect to find Ditto's morphing logic? Digital devices such as mobile phones rely on chips known as ASICs (application specific integrated circuits), which are custom-designed and built to perform specific functions. Each new handset requires new ASICs, and every ASIC needs a dedicated fabrication process which costs millions of dollars to set up. With chaotic logic, one design could be transformed into a variety of custom chips at a fraction of

the cost. This flexibility is already available thanks to the field programmable gate array (FPGA), a chip consisting of a set of logic gates and a network of programmable connections that engineers manipulate to change the ways the gates are connected. But these connections consume around 90 per cent of the circuitry on an FPGA chip. Ditto says that Chaologix chips could be just as flexible, while leaving far more of their transistors and circuits available for useful work. And ASICs are only the start. A single chaotic logic chip should be able to reinvent itself time after time, and in far more radical ways. To prove the principle, Ditto has created a chaotic chip designed to mimic the function of an 8-bit microprocessor. Costing pennies each, they are used in their millions to control everything from toys and toasters to washing machines. Ditto's chip does the job using around 5000 transistors, where the normal processors need 15,000. What's more, it can morph in an instant from an 8-bit to a 16-bit processor. This sort of adaptability is unprecedented, Ditto claims, and with chip-makers struggling to pack ever more processing power into a smaller space, the possibility of making every chip multifunctional is particularly attractive. With this in mind, Ditto and his colleagues are stripping down their chaotic circuits to see just how few transistors they can get away with. They calculate that they can reduce the 750 million transistors used in one of the latest graphics processor chips by an order of magnitude. "We might get away with 75 million transistors," he says. This is not just an matter of saving space. Powerful graphics chips consume a large amount of power and throw out heat that has to be removed. Chaogates could reduce power consumption and perhaps eliminate the need for fans to keep these chips from overheating. Chaotic logic gates can each morph to provide a variety of functions, so damage to any part of a chip containing them need not cause failure - it could reconfigure itself to bypass the damaged section. This could be very useful in space. Probes equipped with chaotic logic could prove significantly more robust, and remain operational when those that rely on conventional circuitry have failed. Alongside its processors, every computer needs memory chips, and here Ditto's chaotic logic also promises radical change. To help achieve this, Ditto has enlisted Mark Spano from the Caderock division of the Naval Surface Warfare Center in West Bethesda, Maryland, who is studying how chaotic states can be used to store and retrieve information.

Total recall One of the simplest forms of digital memory is the flip-flop. This small circuit has two stable states, one to represent a digital 1 and the other to represent 0, so the flip-flop can store a single bit of binary data. But storing data such as text takes a lot of bits. With 26 letters in the alphabet, it takes at least five bits of data - but more usually eight - to represent each letter. A chaogate is far more flexible, as it has a huge number of stable states, each one at a different voltage. There are more than enough of these states to represent every letter of the alphabet, perhaps enough for every word in the English language. To demonstrate this, Spano has used chaogates to store the 1452 characters making up Abraham Lincoln's Gettysburg Address. Using conventional binary gates this would require about 12,000 bits of memory. Non-linear chaotic bits, or "nits" as Spano calls them, can represent individual words rather than letters, and that takes up just 264 nits. "It's a tremendous saving in storage space," says Spano. Chaos could also make retrieving information much faster. In conventional searching tasks - hunting for a file name on your computer's hard disc, for example - the computer must check each memory cell in turn to see if its contents match the search criteria. With nits you can search every memory cell simultaneously, Spano says. Say you have stored the Gettysburg Address, with each word represented by a nit in a different voltage state, and you want to find the word "liberty". With a chaogate memory you simply set the bias on all nits to the voltage matching "liberty" and interrogate them using a 1 input. Thanks to the way that chaogates operate, every nit will output a 0, except the cell containing "liberty", which produces a 1. This type of "parallel" search process is already possible with a form of conventional memory called content addressable memory. But CAM requires extra circuitry, making it expensive and power-hungry. Chaotic memory could be cheaper, since it can store data at higher densities and retrieve it at least eight times as fast as conventional memory, Ditto says. More importantly, he adds, these circuits could morph as required. "It's exciting research and creates a lot of possibilities," says engineer Paul Hasler from Georgia Tech. "I think there's a lot more that hasn't been tapped yet." Luca Gammaitoni, a physicist at the University of Perugia in Italy, agrees: "the work is certainly sound and interesting". But he points out that electrical noise in the memory circuits could blur the voltage state of each nit to the point where it becomes difficult to distinguish between them. The idea will

be put to the test before long, when Chaologix launches its chaotic search system, which Ditto says will use these parallel search capabilities to profile customer spending and browsing habits for a large online publisher. Eventually, Ditto suggests, chaotic logic could transform the way search engines function. These systems catalogue the internet, store the resulting list of websites in massive databases, and then sort the contents to create an index. This database must also be continually updated, and that requires huge resources. Google, for example, has around 40 large data centres. Chaotic logic could help keep such data centres down to a manageable size, Ditto says, as well as increasing search speed. Specialised chaotic search chips could also be built into every desktop computer. First the big chip-makers will have to be convinced that chaotic chips are worth mass-producing. Although Chaologix's chips can be built using existing fabrication plants, developing the interface capable of automatically morphing the chips could prove expensive, says Haslar. Ditto has talked with a number of chip-makers but suspects that they don't quite know what to make of his idea. Whether Ditto succeeds in transforming the silicon chip, chaotic logic could prove itself when conventional computing hits the buffers. Several exotic alternatives to silicon have been proposed, including light-based computing. Unfortunately, there are all kinds of hurdles to building the equivalent of logic gates in these systems, but the use of chaos may solve many of them, Ditto says. "That may be where this approach really shines."