Amoeba-inspired computing system outperforms conventional optimization methods

(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 computing system may offer several benefits, such as high efficiency, miniaturization, and low energy consumption, that could lead to a new computing paradigm for nanoscale high-speed problem solving.

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 optimization problem 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 thermal energy; 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."

© 2015 Phys.org