Kenta Saito
Kenta Saito has a total of 8 co-authors. Here are the top co-authors by number of shared publications:
- Seiya Kasai
Hokkaido Univ, Res Ctr Integrated Quantum Elect, North 13,West 8, Sapporo, Hokkaido 0600813, Japan
4 shared publications Hideharu Amano
Keio University, Japan
1 shared publicationKaori Ohkoda
Amoeba Energy Co., Ltd., Japan
1 shared publicationMasashi Aono
Amoeba Energy Co., Ltd., Fujisawa, Japan
1 shared publication- Masashi Aono
Faculty of Environment and Information Studies, Keio University, 5322 Endo, Fujisawa, Kanagawa 252-0882, Japan
1 shared publication Naoki Suefuji
Hokkaido University, North13, West 8, Sapporo, Hokkaido, 060-0813, JAPAN
1 shared publication
Latest Publications
- 6 December 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-5
Resource-saving FPGA Implementation of the Satisfiability Problem Solver: AmoebaSATslim
The Boolean satisfiability problem (SAT) is an NP-complete combinatorial optimization problem, where fast SAT solvers are useful for various smart society applications. Since these edge-oriented applications require time-critical control, a high speed SAT solver on FPGA is a promising approach. Here the authors propose a novel FPGA implementation of a bio-inspired stochastic local search algorithm called ‘AmoebaSAT’ on a Zynq board. Previous studies on FPGA-AmoebaSATs tackled relatively smaller-sized 3-SAT instances with a few hundred variables and found the solutions in several milli seconds. These implementations, however, adopted an instance-specific approach, which requires synthesis of FPGA configuration every time when the targeted instance is altered. In this paper, a slimmed version of AmoebaSAT named ‘AmoebaSATslim,’ which omits the most resource-consuming part of interactions among variables, is proposed. The FPGA-AmoebaSATslim enables to tackle significantly larger-sized 3-SAT instances, accepting 30,000 variables with 130, 800 clauses. It achieves up to approximately 24 times faster execution speed than the software-AmoebaSATslim implemented on a CPU of the x86 server.
- 6 December 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-5
Resource-saving FPGA Implementation of the Satisfiability Problem Solver: AmoebaSATslim
The Boolean satisfiability problem (SAT) is an NP-complete combinatorial optimization problem, where fast SAT solvers are useful for various smart society applications. Since these edge-oriented applications require time-critical control, a high speed SAT solver on FPGA is a promising approach. Here the authors propose a novel FPGA implementation of a bio-inspired stochastic local search algorithm called ‘AmoebaSAT’ on a Zynq board. Previous studies on FPGA-AmoebaSATs tackled relatively smaller-sized 3-SAT instances with a few hundred variables and found the solutions in several milli seconds. These implementations, however, adopted an instance-specific approach, which requires synthesis of FPGA configuration every time when the targeted instance is altered. In this paper, a slimmed version of AmoebaSAT named ‘AmoebaSATslim,’ which omits the most resource-consuming part of interactions among variables, is proposed. The FPGA-AmoebaSATslim enables to tackle significantly larger-sized 3-SAT instances, accepting 30,000 variables with 130, 800 clauses. It achieves up to approximately 24 times faster execution speed than the software-AmoebaSATslim implemented on a CPU of the x86 server.
- 16 February 2021
- Published by IOP Publishing in Bioinspiration & Biomimetics
- Vol. 16 (3) , 036003
Effect of asymmetric deformation dynamics in amoeboid organism on its search ability
We investigate the effect of asymmetric deformation dynamics in an amoeboid organism on its search ability using a model amoeba. The model represents the behaviours of the amoeboid organism and its search ability is evaluated by searching for the solution to a Boolean satisfiability problem (SAT). We found that the efficiency of the search is significantly improved by implementing asymmetric delays in response to the feedback signals that increase and decrease the variable under appropriate errors. The results indicate that the model could search around the variable vector space by means of the appropriate combination of the inherent local search in the model and the error-induced global search. The results also show that the asymmetric response delays bias the variable to the values that can satisfy the SAT. We also demonstrate that an analog electronic system implementing the amoeba model with asymmetric dynamics possesses the search characteristics of the model.
- 16 February 2021
- Published by IOP Publishing in Bioinspiration & Biomimetics
- Vol. 16 (3) , 036003
Effect of asymmetric deformation dynamics in amoeboid organism on its search ability
We investigate the effect of asymmetric deformation dynamics in an amoeboid organism on its search ability using a model amoeba. The model represents the behaviours of the amoeboid organism and its search ability is evaluated by searching for the solution to a Boolean satisfiability problem (SAT). We found that the efficiency of the search is significantly improved by implementing asymmetric delays in response to the feedback signals that increase and decrease the variable under appropriate errors. The results indicate that the model could search around the variable vector space by means of the appropriate combination of the inherent local search in the model and the error-induced global search. The results also show that the asymmetric response delays bias the variable to the values that can satisfy the SAT. We also demonstrate that an analog electronic system implementing the amoeba model with asymmetric dynamics possesses the search characteristics of the model.
- Open Access
- 27 November 2020
- Published by Springer Nature in Scientific Reports
- Vol. 10 (1) , 1-9
Amoeba-inspired analog electronic computing system integrating resistance crossbar for solving the travelling salesman problem
Combinatorial optimization to search for the best solution across a vast number of legal candidates requires the development of a domain-specific computing architecture that can exploit the computational power of physical processes, as conventional general-purpose computers are not powerful enough. Recently, Ising machines that execute quantum annealing or related mechanisms for rapid search have attracted attention. These machines, however, are hard to map application problems into their architecture, and often converge even at an illegal candidate. Here, we demonstrate an analogue electronic computing system for solving the travelling salesman problem, which mimics efficient foraging behaviour of an amoeboid organism by the spontaneous dynamics of an electric current in its core and enables a high problem-mapping flexibility and resilience using a resistance crossbar circuit. The system has high application potential, as it can determine a high-quality legal solution in a time that grows proportionally to the problem size without suffering from the weaknesses of Ising machines.
- 27 November 2020
- Published by Springer Nature in Scientific Reports
- Vol. 10 (1) , 1-9
Open AccessAmoeba-inspired analog electronic computing system integrating resistance crossbar for solving the travelling salesman problem
Combinatorial optimization to search for the best solution across a vast number of legal candidates requires the development of a domain-specific computing architecture that can exploit the computational power of physical processes, as conventional general-purpose computers are not powerful enough. Recently, Ising machines that execute quantum annealing or related mechanisms for rapid search have attracted attention. These machines, however, are hard to map application problems into their architecture, and often converge even at an illegal candidate. Here, we demonstrate an analogue electronic computing system for solving the travelling salesman problem, which mimics efficient foraging behaviour of an amoeboid organism by the spontaneous dynamics of an electric current in its core and enables a high problem-mapping flexibility and resilience using a resistance crossbar circuit. The system has high application potential, as it can determine a high-quality legal solution in a time that grows proportionally to the problem size without suffering from the weaknesses of Ising machines.
- 21 October 2020
- Published by IOP Publishing in Applied Physics Express
- Vol. 13 (11) , 114501
Effect of feedback delays on solution quality in amoeba-inspired computing system that solves traveling salesman problem
We investigate how feedback delays affect the quality of solutions from an amoeba-inspired analog electronic computing system that solves the "traveling salesman problem." Delays in the feedback process induce the oscillation of state variables. With an appropriate delay length, the system converges to the stable state that corresponds to the solution after oscillation. We find that the solution quality is improved by increasing the delay length. Consequently, delays bring a trade-off between the solution search time and the solution quality. Delay scheduling can further improve solution quality.
- 21 October 2020
- Published by IOP Publishing in Applied Physics Express
- Vol. 13 (11) , 114501
Effect of feedback delays on solution quality in amoeba-inspired computing system that solves traveling salesman problem
We investigate how feedback delays affect the quality of solutions from an amoeba-inspired analog electronic computing system that solves the "traveling salesman problem." Delays in the feedback process induce the oscillation of state variables. With an appropriate delay length, the system converges to the stable state that corresponds to the solution after oscillation. We find that the solution quality is improved by increasing the delay length. Consequently, delays bring a trade-off between the solution search time and the solution quality. Delay scheduling can further improve solution quality.