STATICA, a novel processor architecture designed by scientists at Tokyo Institute of Technology solves combinatorial optimization problems faster than existing processors.
Combinatorial optimization is a topic within operations research, applied mathematics and theoretical computer science. It consists of solving problems or finding an optimal object from a finite set of objects. These complex problems are used across many different fields of science and engineering are require specialized processor architecture.
These complex mathematical problems can be applied in finance as portfolio optimization, in machine learning as well as drug discovery. However current conventional computers are unable to cope with these problems due to the high number of variables.
To solve this issue, a team of researchers form the Tokyo Institute of Technology Collaborated with Hitachi Hokkaido University Laboratory, and the University of Tokyo to design a novel processor architecture. This novel design will be used to specifically solve combinatorial optimization problems expressed in the form of an Ising model. Originally used to describe the magnetic states of atoms in magnetic materials this models is also used as an abstraction for solving combinatorial optimization problems. This is due to the corresponding effect of how the evolution of spins in atoms tending to reach the lowest energy state mimics how an optimization algorithm searches for the best solution.
STATICA, the novel processor architecture is different from existing processors called annealers that calculate Ising models because it is fully connected, and all spin-to-spin interactions are considered. In STATICA, the updating process is carried out in parallel using what is known as stochastic cell automata. Instead of calculating spin states using the spins themselves, STATICA creates replicas of the spins and spin-to-replica interactions are used, allowing for parallel calculation. This saves a tremendous amount of time due to the reduced number of steps needed.
"We have proven that conventional approaches and STATICA derive the same solution under certain conditions, but STATICA does so in N times fewer steps, where N is the number of spins in the model," remarks Prof. Masato Motomura, who led this project.
"STATICA aims at revolutionizing annealing processors by solving optimization problems based on the mathematical model of stochastic cell automata. Our initial evaluations have provided strong results," concludes Prof. Motomura. Further refinements will make STATICA an attractive choice for combinatorial optimization.
Click here for the complete issue.