

Feature Articles: Phygitaldatacentric Computing for Datadriven Innovation in the Physical World LASOLV^{TM} Computing System: Hybrid Platform for Efficient Combinatorial OptimizationAbstractLASOLV^{TM} is a computing machine developed by NTT based on photonics technologies. While we can efficiently solve combinatorial optimization problems by using LASOLV, there are technical challenges in its application to realworld problems. For example, we need to mathematically convert problems to a specific format for solving them using LASOLV. Moreover, LASOLV requires cooperation with conventional digital computers to solve complex problems. In this article, we introduce LASOLV Computing System, which is a computing platform that helps users overcome these challenges. Keywords: LASOLV, combinatorial optimization, nonvon Neumann Computer 1. Challenges in using Ising computersWe are close to the end of Moore’s Law, and it is becoming increasingly difficult to significantly improve computing performance. Nevertheless, we are still facing complex problems that overwhelm today’s conventional digital computers. Combinatorial optimization is one such problem. It asks which answer is the ‘best’ in a set of possible answers, for example, “Which is the shortest route that visits all the given cities?” (traveling salesman problem) and “How can we assign colors to each area using a limited number of colors without assigning the same color to adjacent areas?” (graph coloring problem). We can find these simple questions in realworld problems such as quality improvement of wireless communication. To provide wireless access in a large venue, multiple access points might be installed. Closely located access points should not use the same frequency band; otherwise, wireless access will be unstable due to radiowave interference. We can consider this problem as a graph coloring problem that assigns frequency bands instead of colors. Thus, combinatorial optimization is applied in various realworld problems. Various instances of combinatorial optimization can be converted into Ising optimization problems, i.e., a groundstate search of the Ising model. The Ising model is a theoretical model in statistical mechanics that represents a network of spins (Fig. 1). Spin σ_{i} takes one of two states: up (+1) or down (−1). By letting J_{ij} and h_{i} represent the strengths of a spintospin interaction and a magnetic field, respectively, the ground state refers to the spin configuration that minimizes the Ising Hamiltonian H defined as
Computers specialized for Ising optimization have been developed to efficiently solve Ising optimization problems. We call these computers Ising computers. There are several types of Ising computers: quantum annealing machines, such as DWave 2000Q, specially designed semiconductor chips, such as Fujitsu’s Digital Annealing Unit, and the coherent Ising machine (CIM) [1]. The CIM is an Ising computer that simulates the Ising model using photonics technologies. NTT Basic Research Laboratories is conducting research and development of LASOLV^{TM} (Fig. 2), which is a CIM implemented by NTT. Although Ising computers can do nothing other than solve Ising optimization problems of a limited number of spins, we can apply them to complex problems by using hybrid algorithms. Hybrid algorithms use both Ising computers and digital computers cooperatively. For example, decomposition heuristics solves largescale Ising optimization problems by iteratively generating small subproblems on a digital computer and solving them on an Ising computer. Hence, Ising computers are widely applicable to realworld problems.
However, there are several challenges with using Ising computers. One of the most fundamental challenges is sharing among multiple users. Since it is difficult to have a ‘personal’ Ising computer due to its cost and facility requirements, we need a multiuser system that coordinates accesses to Ising computers. Some companies solve this problem by using cloud platforms [2, 3] that provide Ising computers as a service. Platform users run their programs on their digital computers and offload Ising optimization to the cloud by issuing a web application programming interface (API) request from the programs. While these platforms enable many developers to use Ising computers, they are inefficient in executing hybrid algorithms. Latencies of web API requests via the Internet are significantly long compared with the solution time of Ising computers, which is in milliseconds. Since hybrid algorithms tend to involve frequent communication between Ising computers and digital computers, communication overheads affect performance. Thus, we are still facing challenges with using Ising computers. To solve these problems, we developed a platform for Ising computing. In this article, we first clarify the issues with the design of Ising computing platforms then introduce our platform, LASOLV Computing System (LCS). The most distinguishing feature of LCS is the integration of LASOLV and digital computers in a single system. LCS allows users to run their programs on a digital computer colocated with LASOLV. This enables efficient communication between LASOLV and digital computers. LCS also provides a Python library that assists in converting various problems to Ising optimization problems. We give details of LCS in the following sections. Due to space limitations, we omit a description of LASOLV. Refer to a previous article [1] for further details. 2. Issues in platform designIn this section, we state three issues with the design of Ising computing platforms. 2.1 EfficiencyAs mentioned above, communication via the Internet takes an order of magnitude longer than Ising optimization. In addition, as technology advances, Ising computers will have a larger number of spins. For example, LASOLV currently supports up to 2000 spins, but NTT Basic Research Laboratories aims to increase this to 100,000 spins. As a result, the data size of Ising optimization problems, that is, the size of J_{ij} and h_{i}, will increase, and communication efficiency will have more impact on performance. Therefore, platforms need to be designed to minimize communication overheads. 2.2 ExtensibilitySpecifications of Ising computers are subject to change due to their evolution. This inevitably makes the platforms a heterogeneous environment consisting of incompatible Ising computers. Thus, it is necessary to manage these computing resources so that users can avoid compatibility problems and effectively use available resources. 2.3 ProductivityPlatform users have to convert combinatorial optimization problems into Ising optimization problems to use Ising computers. This conversion requires special skills and knowledge of Ising computers. Since conversion methods differ among problems, it is impractical to provide readymade conversion algorithms for each problem. To achieve high productivity for a wide range of purposes, we need to design a programming interface that offers both convenience and versatility. 3. LASOLV Computing SystemNTT Software Innovation Center has developed LCS, which is a computer cluster with a Python library and middleware such as a job scheduler. It has the following three features to solve the design problems described in the previous section. 3.1 CIMdigital integrationTo enable efficient communication between LASOLV and digital computers, they are integrated within a single cluster of LCS (Fig. 3). Except for the integration of LASOLV, this is a cluster configuration standard in highperformance computing. Users can request execution of their program as a job through SSH (Secure Shell) or Jupyter Notebook on web browsers (Fig. 4). Through cooperation of the job scheduler and LCS library, Ising optimization is implicitly offloaded to LASOLV, and the other computation is executed on a compute node using a digital computer. Since compute nodes and LASOLV communicate within the cluster, LCS can provide higherbandwidth and lowerlatency communication than other platforms. In addition, LCS coordinates jobs so that each one can occupy a CPU (central processing unit) core and LASOLV exclusively; thus, multiple users can use LCS simultaneously.
3.2 Group dispatchLCS is designed to be a scaleout system. Since LASOLV with different specifications may appear in the future, LCS makes groups of compatible LASOLVs for ease of management. Users can select a target group for offloading depending on the requirements of the problem (e.g., the number of spins). LCS then distributes offloading requests among LASOLVs in the target group for using them equally and improving throughput. Note that we are going to update the library for automatically determining the target group for offloading. 3.3 Layered reductionCombinatorial optimization problems are converted into Ising optimization problems by the following three steps: formally defining the problem, converting it to a minimization problem of a polynomial objective function, and deforming the objective function to the Ising Hamiltonian. To offer options of the programming interface to cover various use cases, the LCS library has the following three layers that correspond to each conversion step (Fig. 5).
(1) Solver layer The solver layer is a set of problemspecific conversion algorithms for wellknown NPhard problems such as the traveling salesman and graph coloring problems. These algorithms generate a polynomial objective function or the Ising Hamiltonian, which is handled in the following layers. (2) Polynomial layer This layer provides an internal domainspecific language (DSL) for converting polynomial objective functions into the Ising Hamiltonian. The DSL is useful when the solver layer lacks an algorithm for the problem to be solved or when users need more flexibility for handtuning. (3) Hamiltonian layer The Hamiltonian layer is a raw interface for the Ising Hamiltonian. It takes J_{ij} and h_{i} as inputs, solves the Ising optimization problem using LASOLV, and returns the answer. While the solver layer has an algorithm for the graph coloring problem, we solve it using the DSL of the polynomial layer as an example. Consider the graph coloring problem that asks how we can paint n vertices in graph G using c colors so that adjacent vertices have different colors. By letting A be an adjacency matrix of G and p be a hyperparameter and using the variable x_{v,i} ∈ {0, 1}, we can convert the graph coloring problem into the minimization problem of the following function [4]: This function is quadratic polynomial about x_{v,i}. Using the DSL of the polynomial layer, this function can be expressed and minimized using intuitive Python code (Fig. 6).
Moreover, the Hamiltonian layer provides a hybrid algorithm for solving largescale Ising optimization problems beyond the capacity of LASOLV. This is a heuristics we developed based on several existing methods. To deliver our research and development outcomes, such as this heuristics, to users quickly, we developed an original library with which users can benefit from these outcomes by simply implementing programs. Users can also use other libraries [5–8] at the same time for Ising computing on LCS. These libraries finally generate the Ising Hamiltonian; thus, it can be solved by the Hamiltonian layer. Conversely, results of Ising conversion using the LCS library can be used as input for Ising computers other than LASOLV. 4. Future prospectsIn this article, we first stated issues with the design of Ising computing platforms then introduced how LCS solves them. LCS is currently available to research collaborators in the smallstart configuration of two highend servers that serve as a login, compute, and storage node and one LASOLV. To promote research and development using LASOLV, we will continue to improve LCS. References
Trademark notesAll brand, product, and company/organization names that appear in this article are trademarks or registered trademarks of their respective owners. 