Amoeba-inspired computing system outperforms conventional optimization methods

June 1, 2015 by Lisa Zyga feature
(Left) An amoeboid organism, like the slime mold Physarum polycephalum shown here on a gold-coated chip in an agar plate, provides a model of the computing principles of biological systems. (Right) Researchers designed a network of electrical Brownian ratchets to implement an amoeba-inspired computing system. Credit: M. Aono, et al. ©2015 IOP Publishing

(Phys.org)—Researchers have designed and implemented an algorithm that solves computing problems using a strategy inspired by the way that an amoeba branches out to obtain resources. The new algorithm, called AmoebaSAT, can solve the satisfiability (SAT) problem—a difficult optimization problem with many practical applications—using orders of magnitude fewer steps than the number of steps required by one of the fastest conventional algorithms.

The researchers predict that the amoeba-inspired may offer several benefits, such as high efficiency, miniaturization, and low , that could lead to a new computing paradigm for nanoscale high-speed .

Led by Masashi Aono, Associate Principal Investigator at the Earth-Life Science Institute, Tokyo Institute of Technology, and at PRESTO, Japan Science and Technology Agency, the researchers have published a paper on the amoeba-inspired system in a recent issue of Nanotechnology.

"We demonstrated a way to harness the huge computational power of natural phenomena in terms of complexity and energy," Aono told Phys.org.

The motivation for this research comes in large part from the ongoing trend of electronic miniaturization. As the scientists explain, transistors have become so small that they are approaching the scale at which thermal fluctuations can disrupt their operation. These fluctuations must be addressed, but rather than try to minimize their impact, recent research has suggested that a better alternative may be to coexist with them. Many biological systems, such as the molecular motors involved in muscle contraction, have been doing this successfully for millions of years.

In their study, the researchers designed a nanoscale computing system consisting of an electrical Brownian ratchet, which uses the same basic mechanism as a biological molecular motor, to generate current from fluctuating electrons. In an electrical Brownian ratchet, thermal energy in a nanowire randomly causes electrons to either move in one direction (e.g., left but not right) or stay in the same place. Repeating this process multiple times generates a directed electron flow, resulting in an electric current with stochastic (random) fluctuations. As previous research has shown, as long as no energy is transferred outside of the system, the process does not violate the second law of thermodynamics.

To implement their amoeba-inspired computing system, the researchers designed a network of electrical Brownian ratchets with numerous "branches" or wires. The branches correspond to an amoeba's pseudopods, which can extend across large areas of space to maximize nutrient absorption. In a similar way, the branches of the ratchet network can supply current (which represents the binary value "1") or no current (representing "0") in a stochastic manner. Overall, both systems use random motion, coupled with dynamic feedback control, to perform computing tasks.

To evaluate the AmoebaSAT system's computing ability, the researchers applied it to solve a difficult combinatorial called the SAT problem, which basically involves determining if a given formula consisting of numerous logical variables and constraints is "satisfiable." The SAT problem and its derived problems have a wide range of applications in fields including robotics, modeling, electronic commerce, and others.

"To search for a solution to the SAT problem, each unit of the system must behave in a stochastic manner and make an 'error' for exploring a broader state space; the error indicates that the resource is not supplied even when the inhibitory control signal is not applied," Aono explained. "In this regard, the electrical Brownian ratchet is one of the best devices for solving the problems because it implements stochastic operations with errors, as exposed to random thermal noise. Furthermore, this device is advantageous because it consumes low levels of energy, which are comparable to ; it facilitates large-scale integration to solve large problems."

Tests showed that the AmoebaSAT system had a 100% success rate in finding a solution to various 50-variable SAT problems, solving these problems with an average of about 3,000 steps. A modified version of the algorithm, which can more effectively deal with error-inducing random noise, performed even better, averaging fewer than 1800 steps. For comparison, one of the fastest known local search algorithms, WalkSAT, required orders of magnitude more steps to solve the same problems. Moreover, the AmoebaSAT outperforms WalkSAT more significantly as the number of variables increases.

The researchers propose that the AmoebaSAT's superior performance originates from its "concurrent search" feature, referring to its ability to update multiple variables simultaneously. In contrast, WalkSAT algorithms and other methods that run on conventional digital computers can update only one variable at each step. This "serial" feature can be traced back to the Turing machine, which defined the conventional notion of computation. In the future, the researchers plan to further explore the origins of the new nature-inspired algorithm's performance advantages.

Another advantage of the new algorithm that makes it especially promising for future developments is its potential scalability. Many natural computers, such as brain-inspired neural networks, require a large number of interconnected wires that grows rapidly as the complexity of the problem grows, limiting the scalability of these networks. The amoeba-inspired architecture avoids this problem because the number of interconnected units grows only linearly as complexity increases.

With all of these advantages, the researchers hope that amoeba-inspired computing will offer more than just a computing novelty, but a practical way to implement future nanoscale computing technology.

"Currently, we have just designed the system and verified that it works quite well, although the correct operations of the electrical Brownian ratchets have already been confirmed," Aono said. "In the near future, we'll fabricate the actual AmoebaSAT system implemented using the electrical Brownian ratchet and demonstrate that it successfully achieves its excellent performances in terms of the efficiency, miniaturization, and reductions in energy consumption."

Explore further: Scientists develop atomic-scale hardware to implement natural computing

More information: M. Aono, et al. "Amoeba-inspired nanoarchitectonic computing implemented using electrical Brownian ratchets." Nanotechnology. DOI: 10.1088/0957-4484/26/23/234001

Related Stories

The brain could be key to a better computer

May 15, 2014

Your brain is incredibly well-suited to handling whatever comes along, plus it's tough and operates on little energy. Those attributes—dealing with real-world situations, resiliency and energy efficiency—are precisely ...

Recommended for you

ANU invention to inspire new night-vision specs

December 7, 2016

Scientists at The Australian National University (ANU) have designed a nano crystal around 500 times smaller than a human hair that turns darkness into visible light and can be used to create light-weight night-vision glasses.

New method for studying individual defects in transistors

December 6, 2016

Scientists from the University of Twente's MESA+ Research Institute have developed a method for studying individual defects in transistors. All computer chips, which are each made up of huge numbers of transistors, contain ...

2 comments

Adjust slider to filter visible comments by rank

Display comments: newest first

retrosurf
not rated yet Jun 01, 2015
Something's missing from the article or the paper (or both :-)

Brownian Ratchets can't work as described. They can work if there is a temperature differential that they can exploit, in which case they are really "Carnot Ratchets", so there must be a temperature differential that is used to power the devices.
antonima
not rated yet Jun 02, 2015
wiki: "Léon Brillouin in 1950 discussed an electrical analogy that uses a rectifier (such as a diode) instead of a ratchet. The idea was that the thermal current fluctuations impinging on the diode should be rectified, and therefore spontaneously produce a nonzero constant voltage offset that can be used to perform work. In the detailed analysis it was shown that the thermal fluctuations within the diode generate an electromotive force that cancels the voltage from rectified current fluctuations"

It says that EMF cancels out voltage from biased flow of electrons, not that it cancels out the biased flow of electrons itself. Perhaps there will still be perpetual electron flow through the circuit?

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.