KSKenta Saito

Kenta Saito

*This is an algorithmically generated author record based on publicly available information.

Kenta Saito has a total of 8 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Resource-saving FPGA Implementation of the Satisfiability Problem Solver: AmoebaSATslim

    by Ying Jie Yan, Hideharu Amano, Masashi Aono, Kaori Ohkoda, Shingo Fukuda, Kenta Saito, Seiya Kasai

    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.


  • Effect of asymmetric deformation dynamics in amoeboid organism on its search ability

    by Kenta Saito, Naoki Suefuji, Seiya Kasai

    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

    Amoeba-inspired analog electronic computing system integrating resistance crossbar for solving the travelling salesman problem

    by Kenta Saito, Masashi Aono, Seiya Kasai

    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.


  • Effect of feedback delays on solution quality in amoeba-inspired computing system that solves traveling salesman problem

    by Kenta Saito, Seiya Kasai

    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.