Information processing acceleration control system

An aspect of the present invention for solving the above problem is a system including a first computer, a control module controlled by the first computer, and a second computer configured to be associated with the control module. The second computer includes a plurality of units, and each of the plurality of units includes a first memory that stores a value indicating a state of a node, a second memory that stores a coefficient, and an arithmetic circuit. The arithmetic circuit performs an arithmetic process of determining a value indicating a state of a node of its own unit, based on a value indicating a state of a node of a different unit and the coefficient of its own unit, and storing the determined value in the first memory. The control module supplies a control signal for controlling the arithmetic process to the second computer.

TECHNICAL FIELD

The present invention relates to an information processing apparatus, and more particularly to an information processing apparatus that handles calculations such as an Ising model and a neuro model and an information processing system that controls the information processing apparatus as an accelerator.

BACKGROUND ART

Currently, the mainstream of computer architecture is a von Neumann type. In the von Neumann type architecture, its operation is defined by a program which is a sequential instruction sequence. By changing the program, it has versatility available for various purposes. Not only a central processing unit (CPU) that plays a central role of a computer but also a computing apparatus for a specific application such as a graphics processing unit (GPU) are configured with the von Neumann architecture, and the basic operations thereof are executed sequentially. A computer that sequentially executes instructions and solves the problem is referred to as “time expansion type computer” in the present specification, from a viewpoint that it develops a problem in a time direction.

Until now, performance improvement of a computer mainly depends on the improvement of a clock frequency. Since the basis of the von Neumann architecture is the sequential execution of the instruction sequence, if the instruction execution speed is increased, performance improvement can be expected. However, in general-purpose CPUs used in personal computers and servers, the improvement of a clock frequency has ceased at around 3 GHz in the early 2000s. In recent years, measures to realize performance improvement by a parallel process using multi cores are becoming a mainstream, in place of the clock frequency of which improvement has ceased.

In the parallel process using multi cores, performance is improved by finding parallel executable parts from the sequential instruction sequence (extraction of parallelism) and executing the parts in parallel. However, it is not easy to extract parallelism from a program in which sequential algorithms are written as instruction sequences. Instruction level parallelism (ILP) for extracting parallelism with the instruction level has already reached the limit, and in recent years, coarse grain parallelism as thread level parallelism (TLP) and data level parallelism (DLP) tends to be used.

In view of this situation, in order to improve the performance of the computer in the future, it is not based on the execution of the sequential instruction sequence as in the related art, but essentially, it is necessary to shift to a parallel information process. To do this, instead of a method of describing a problem based on the sequential instruction sequence in the related art, it is necessary to describe a problem suited for essentially realizing the parallel information process.

One candidate thereof is Ising model. The Ising model is a model of statistical mechanics to explain the behavior of magnetic materials, and is used for research on magnetic materials. The Ising model is defined as an interaction between sites (spins having two values of +1 and −1). It is known that determining the ground state of the Ising model where the topology becomes a nonplanar graph is an NP difficult problem. Since the Ising model expresses the problem with the interaction coefficient spreading in the spatial direction, there is a possibility that information processing using intrinsic parallelism can be realized.

By the way, since determining the ground state of the Ising model is an NP difficult problem as described above, it is difficult to obtain a solution using the von Neumann computer in terms of calculation time. Algorithms for introducing heuristics to increase speed have also been proposed. However, a calculation using a physical phenomenon more directly rather than the von Neumann type computer, that is, a method of rapidly obtaining the ground state of the Ising model by an analog computer has been proposed.

For example, there is an apparatus described in PTL 1 as such an apparatus. Such a computer solves a problem by expanding it in the spatial direction, not in the time direction, so it is referred to as “space expansion type computer” in this specification. Since the space expansion type computer applies a specific problem to a specific type and solve it, it is difficult to control its calculation process, and it is necessary to use a time expansion type general-purpose computer for the control.

In a case where the time expansion type computer controls the space expansion type computer, it is necessary for the time space type computer to recognize the extent of processing by the space expansion type computer, and perform control according to time. When a single time expansion type computer controls a single space expansion type computer, control corresponding to the space expansion type computer can be realized by executing control corresponding to the space type computer.

CITATION LIST

Patent Literature

PTL 1: Pamphlet of International Publication No. 2012/118064

SUMMARY OF INVENTION

Technical Problem

However, when a single time expansion type computer attempts to control a plurality of space expansion type computers, control in accordance with the operation of each space expansion type computer is required. For example, when changing the operation of each space expansion type computer in a state where a plurality of space expansion type computers are operating, time management for each space expansion type computer is performed continuously, and it is necessary to control the start and end of calculation of the space expansion type computer and to perform temperature scheduling according to the time. As the number of space expansion type computers increases, there is a problem that the time expansion type computer handles many resources to control all.

Solution to Problem

An aspect of the present invention for solving the above problem is a system including a first computer, a control module controlled by the first computer, and a second computer configured to be associated with the control module. The second computer includes a plurality of units, and each of the plurality of units includes a first memory that stores a value indicating a state of a node, a second memory that stores a coefficient, and an arithmetic circuit. The arithmetic circuit performs an arithmetic process of determining a value indicating a state of the node of its own unit, based on a value indicating a state of a node of a different unit and the coefficient of its own unit, and storing the determined value in the first memory, and the control module supplies a control signal for controlling the arithmetic process to the second computer.

Another aspect of the present invention is a system including a computer and a control module. The computer includes a plurality of units, and each of the plurality of units includes a first memory, a second memory, and an arithmetic circuit. The arithmetic circuit performs an arithmetic process of determining a value to be stored in a first memory cell of its own unit, based on the value stored in the first memory of a different unit and a value stored in the second memory of its own unit. The control module supplies a first control signal designating a memory and a second control signal designating a timing to the computer in order to control the arithmetic process.

Another aspect of the present invention is a system having a control unit separately from a space expansion type computer. In particular, when having a plurality of space expansion type computers, each of the space expansion type computers includes a control module. The control module executes time management of calculation execution and temperature control which is operation control of a space expansion type computer. The control module may be included in the time expansion type computer, the control module may be placed outside, or the control module may be mounted on the space expansion type computer.

Advantageous Effects of Invention

With the configuration of the present application, it becomes unnecessary for a space expansion type computer to perform fine control such as time management and temperature management of the space expansion type computer, and there is no need to waste resources of a time expansion type computer in order to control the space expansion type computer.

DESCRIPTION OF EMBODIMENTS

In the following embodiments, if necessary for the sake of convenience, a description will be made by separating the present invention into a plurality of sections or embodiments, but unless otherwise specified, they are not unrelated to each other, one is related to the modification example, details, supplementary explanation, or the like of a part or all of the other. Further, in the following embodiments, in a case of referring to the number of elements (including number, numerical value, quantity, range, or the like), except for a case where it is expressly specified, and a case where it is obviously limited to a specific number in principle, or the like, it is not limited to the specific number, and it may be the specific number or more or or less.

The notations such as “first”, “second”, “third”, and the like in this specification are attached to identify constituent elements, and do not necessarily limit the number or order. In addition, the number for identifying the constituent element is used for each context, and the number used in one context does not necessarily indicate the same constituent element in other contexts. Further, it does not preclude that the constituent element identified by a certain number doubles as the function of the constituent element identified by another number.

The positions, sizes, shapes, ranges, and the like of the respective components shown in the drawings and the like may not show actual positions, sizes, shapes, ranges and the like in order to facilitate understanding of the invention. Therefore, the present invention is not necessarily limited to the positions, sizes, shapes, ranges, and the like disclosed in the drawings and the like.

Furthermore, in the following embodiments, it goes without saying that the constituent elements (including element steps or the like) are not essential, except for a case where they are expressly specified or a case where it is considered to be obviously essential in principle. Similarly, in the following embodiments, it is assumed that when referring to shapes, positional relationships, or the like of constituent elements, shapes which are substantially approximate or similar to the referred shape or the like are included, except for a case where they are expressly specified and a case where it is thought that they are not obvious in principle. This also applies to the above numerical values and ranges.

Hereinafter, an embodiment of the present invention will be described in detail with reference to the drawings. In addition, in all of the drawings for describing the embodiments, the same or related reference numerals will be given to the same members in principle, and the repetitive description thereof will be omitted. In the following embodiments, the description of the same or similar parts will not be repeated in principle unless it is particularly necessary.

In the present embodiment, as an example of a space expansion type computer, an example of an Ising chip100(FIG. 1) which is a semiconductor device for finding the ground state of the Ising model will be described.

The Ising model is a model of statistical mechanics to explain the behavior of a magnetic material. The Ising model is defined by a spin having binary values of +1 and −1 (or 0 and 1, up and down), an interaction coefficient indicating an interaction between spins, and an external magnetic field coefficient for each spin.

The Ising model can calculate the energy at that time, from the given spin arrangement, interaction coefficient, and external magnetic field coefficient. The energy function E(σ) of the Ising model is generally expressed by the following equation (1).

In addition, σiand σjrepresent the i-th and j-th spin values, respectively, Ji, jrepresents an interaction coefficient between the i-th and j-th spins, hirepresents the external magnetic field coefficient for the i-th spin, <i, j> is a combination of two adjacent sites, and σ represents the spin arrangement.

The ground state search of the Ising model is an optimization problem to find a spin arrangement that minimizes the energy function of the Ising model. For example, problems such as factorization and traveling salesman problem, which are irrelevant to magnetic materials at first glance, can be converted into Ising models. Then, the ground state of the Ising model obtained by the transformation corresponds to the solution of the original problem. From this, it can be said that a device capable of searching the ground state of the Ising model is a computer usable for general purpose.

FIG. 1is a diagram for explaining an example of a configuration of an Ising chip100in the present embodiment. The Ising chip100includes a spin array110, an input/output (I/O) driver120, an I/O address decoder130, and an interaction address decoder140. In the present embodiment, the Ising chip100is described assuming that it is mounted as a complementary metal-oxide semiconductor (CMOS) integrated circuit which is now widely used, but other solid elements can also be realized.

The Ising chip100includes an SRAM compatible interface150for performing reading from and writing to the spin array110. The SRAM compatible interface150includes an address bus190, a data bus191, an R/W control line193, and an I/O clock line192. This part is based on the configuration for read/write of the SRAM memory in the related art.

It also has an interaction address line180and an interaction clock line181as an interaction control interface160for controlling the ground state search of the Ising model. The interaction control interface160is an interface for controlling interaction calculation to be described later.

In the example ofFIG. 1, the Ising chip100operates with the voltage supplied through the power supply line142. In the Ising chip100, the spin σi, the interaction coefficient Ji, jand the external magnetic field coefficient hiof the Ising model are all represented by information stored in the memory cells in the spin array110. In the example shown inFIG. 1, it is assumed that the memory cell is configured with a high-speed static random access memory (SRAM). In this case, in order to set the initial state of the spin σiand to read the solution after completing the ground state search, the spin σiis read/written by the SRAM compatible interface150. In order to set the Ising model of which the ground state is to be searched in the Ising chip100, the interaction coefficient Ji, jand the external magnetic field coefficient hiare also read/written by the SRAM compatible interface150. Therefore, the spin σi, the interaction coefficient Ji, jand the external magnetic field coefficient hiof the spin array110are given addresses corresponding to the memory cells storing them.

Note that the address bus190, the data bus191and the R/W control line193constituting the SRAM compatible interface150operate in synchronization with the clock input to the I/O clock line192. However, in this embodiment, there is no need for the interface to be synchronous, and an asynchronous interface may be used. In the present embodiment, a description will be given assuming that it is a synchronous interface.

In addition, the Ising chip100realizes the interaction between spins in the spin array110in order to perform the ground state search. The interaction control interface160externally controls the interaction. More specifically, an address designating a memory storing the spin group to perform interaction is input through the interaction address line180. Then, the spins stored in the designated memory interact with each other in synchronization with the clock input through the interaction clock line181. In the example of the Ising chip, the interaction is an operation using the spin σi, the interaction coefficient Ji, jand the external magnetic field coefficient hi, and the storage of the result. Specifically, a series of processes for reading the value of the memory cell of the spin array, calculating the energy from the read value, determining the spin value such that the energy becomes small, and writing the determined spin value into the memory cell are performed.

It should be noted that the interaction does not necessarily have to be realized by a clock synchronization circuit, and may be an asynchronous circuit. In this case, it is assumed that the role of the interaction clock line181is not to input a clock but to input an enable signal that permits the execution of an interaction. A description will be given assuming that the interaction control interface is not necessarily required to be synchronous, but an asynchronous interface may be used, but in the present embodiment, a synchronous interface is used and interaction is performed in synchronization with the clock input through the interaction clock line181.

The spin unit200implements holding of one spin and its associated interaction coefficient and external magnetic field coefficient and a ground state search process. The spin array110is configured by arranging a large number of spin units200, with a spin unit200as a basic configuration unit.

FIG. 2is a conceptual diagram for explaining an example of the configuration of the spin array110of a three-dimensional lattice.FIG. 2shows an example in which a plurality of spin units200are arranged as a spin array110to construct an Ising model having a three-dimensional lattice topology.

The example inFIG. 2is a three-dimensional lattice having a size of 3 (X-axis direction)×3 (Y-axis direction)×2 (Z-axis direction). The coordinate axes are defined as shown inFIG. 2, the X axis is the right direction ofFIG. 2, the Y axis is the downward direction ofFIG. 2, and the Z axis is the depth direction ofFIG. 2. However, the coordinate axes are only necessary for the convenience of description of the embodiment, and are not related to the present embodiment. In the case of using a topology other than the three-dimensional lattice, for example, a tree-like topology, it is expressed by the number of stages of the tree or the like separately from the coordinate axis. In the three-dimensional lattice topology ofFIG. 3, if the interaction between spins is obtained as a graph, a five-order-of spin (vertex) is required at maximum. Incidentally, considering the connection of the external magnetic field coefficient, the order 6 is required at the maximum.

The values of the spins σj, σk, σl, σm, and σnof the adjacent spin units are input to the single spin unit200shown inFIG. 2. In the example ofFIG. 2, these values indicate the values of five adjacent spin units in the up, down, left, right, and depth directions. The spin unit200includes a memory cell storing a spin σiand an external magnetic field coefficient hi. In the spin unit200ofFIG. 2, the memory cells storing the spins are shown by circles, and the memory cells storing the external magnetic field coefficients are shown by squares. It also includes memory cells that hold Jj, i, Jk, i, Jl, i, Jm, i, and Jn, iwhich are the interaction coefficients with the above-mentioned five adjacent spins σi. These are shown inFIG. 2as rectangles.

Incidentally, the Ising model generally has an interaction expressed by an undirected graph. In the above equation (1), there is Ji, j×σi×σjas a term representing the interaction, which indicates the interaction from the i-th spin to the j-th spin. At this time, in the general Ising model, there is no distinction between the interaction from the i-th spin to the j-th spin and the interaction from the j-th spin to the i-th spin. That is, Ji, jand Jj, iare the same. However, in the Ising chip100of the present embodiment, the Ising model is expanded to a directed graph to make the interaction from the i-th spin to the j-th spin and the interaction from the j-th spin to the i-th spin asymmetric. Thus, the expressive capability of the model is increased, and many problems can be expressed with a smaller model.

Therefore, when considering one spin unit200as the i-th spin σi, Jj, i, Jk, i, Jl, i, Jm, i, and Jn, i, which are the interaction coefficients held by the spin unit, are used to determine the interaction from the adjacent j-th, k-th, l-th, m-th, and n-th spins σj, σk, σl, σm, and σnto the i-th spin σi. This means that inFIG. 2, the arrows (interactions) corresponding to the interaction coefficients included in the spin unit200correspond to heading from the spins outside the illustrated spin unit200to the spins inside the spin unit200.

An example of a specific configuration of the spin unit200will be described with reference toFIG. 3. Since the spin unit200holds the spin σi, interaction coefficient Jj, i, to Jn, i, and external magnetic field coefficient hiof the ising model, it has a plurality of memory cells N, IU0, IU1, IL0, IL1, IR0, IR1, ID0, ID1, IF0, IF1, IS0, and IS1. Though not shown inFIG. 3, the memory cells have a data holding unit including two CMOS inverters like the SRAM, and realizes data reading from and writing to the data holding unit, by controlling pass gate transistors connected to both ends of the data holding unit through word lines and bit lines, which are also not illustrated. A method of reading from and writing to a desired memory cell using a word line and a bit line follows the configuration of an SRAM in the related art. That is, the Ising chip of the present embodiment basically has a structure of a memory cell array. In the present embodiment, a high-speed SRAM configuration is employed, but other types of memories can also operate.

In the Ising model, the spin values are +1 and −1 (+1 is expressed by up and −1 is expressed by down), but correspond to 0 and 1 which are the binary values of the memory cell N. For example, +1 corresponds to 1, −1 corresponds to 0.

In the present embodiment, the external magnetic field coefficient and the interaction coefficient are associated with three values of +1, 0, −1. Therefore, in order to express the external magnetic field coefficient and the interaction coefficient, 2-bit memory cells are used, respectively. As shown inFIG. 3, IS0, IS1, IU0, IU1, IL0, IL1, IR0, IR1, ID0, ID1, IF0, and IF1indicate three values of +1, 0, and −1, with a combination of two memory cells with the last digit 0 and 1 (for example, IS0and IS1in the case of the external magnetic field coefficient ISX). For example, in the case of the external magnetic field coefficient ISX, IS1indicates +1 or −1 (when IS1is 1, it indicates +1, and when IS1is 0, it indicates −1). In addition, when the IS0is 0, the external magnetic field coefficient is regarded as 0, and when IS0is 1, one of +1 and −1 determined by IS1is set as the external magnetic field coefficient. Considering that the external magnetic field coefficient is disabled when the external magnetic field coefficient is 0, it can be said that IS0is the enable bit of the external magnetic field coefficient (the external magnetic field coefficient is enabled when IS0=1). Likewise, in IU0, IU1, IL0, IL1, IR0, IR1, ID0, ID1, IF0, and IF1expressing the interaction coefficients, coefficients and bit values are associated with each other.

In the spin unit200, the next state of the spin that performs the interaction calculation so as to minimize the energy between adjacent spins or spins which are away from each other is determined. In the example ofFIG. 3, NU, NL, NR, ND, and NF indicate lines connected to spin units adjacent in the up, left, right, down, and depth directions, respectively, and receive signals about the spin values (state) read out from each spin unit. The signal indicated by N is a line for transmitting the spin value stored in the memory cell N to the adjacent spin unit. In this manner, the spin units are configured to transmit and receive the spin values of each other, but the connection may be configured to reproduce, for example, a model assumed as shown inFIG. 2.

The logic circuit2000shown in the spin unit200ofFIG. 3is a circuit for performing the above-described interaction. First, the exclusive OR of the state of the spins which are adjacent to each other or away from each other and the value indicating the interaction coefficient, which is held in the memory cell, is obtained by an exclusive OR circuit.

This makes it possible to calculate the next state of the spin that minimizes energy when considering only the interaction. When the interaction coefficient is only +1 and −1, if the majority logic circuit201determines which of +1 and −1 of the outputs of the exclusive OR circuit is more by the majority logic, the next state of the spin can be determined. Considering that the external magnetic field coefficients stored in IS0and IS1always correspond to the interaction coefficient with the spin of the state +1, the value of the external magnetic field coefficient is simply set to a value to be input to the majority logic circuit201which determines the next state of the spin. The next state of the spin calculated in this way is stored (overwritten) in the memory cell N, and one interaction calculation is completed.

By minimizing energy by repeating the interaction calculation between spins a plurality of times, the ground state search of the applied Ising model can be realized. However, there is a possibility that it will fall into a local optimum solution by itself. Basically, since there is only movement in the direction of decreasing energy, once falling into a local optimum solution, it cannot escape from it and does not reach the global optimum solution. Therefore, as an operation for escaping from the local optimum solution, a method of stochastically inverting the value of the memory cell expressing the spin is also used.

As a specific example, the random number142is input to the spin unit200, and in a case where the value is 1, the value is inverted by the inversion logic203. Thus, it is possible to obtain a low energy value as much as possible without stacking it on local optimization. The appearance frequency of 1 or 0 of the random number value corresponds to the temperature at the time of convergence calculation of the space expansion type computer. That is, in a case where the temperature in the convergence calculation is high (the overall energy is high), the frequency of occurrence of 1 is increased, and when the temperature is low (the overall energy is low), the frequency of occurrence of 0 is increased. That is, the appearance frequency of 1 or 0 of the random number is changed by one method of controlling the temperature. Specifically, in the process of repeating the interaction calculation a plurality of times, the random number142may be controlled so as to increase the frequency of occurrence of 1 at the beginning and increase the frequency of occurrence of 0 at the end.

The interaction calculation described above may be performed so that the spin units200in the spin array110are executed one by one. However, this method has a disadvantage that calculation is time consuming. Therefore, it is conceivable that the interaction between the spins is performed concurrently for all the spins. However, in actual interaction calculation, it is not preferable to simultaneously perform interaction calculation between a certain spin unit that performs the interaction calculation and a different spin unit that inputs the spin value to the certain spin unit. When updating a certain spin, the spin is updated so as to minimize the energy to and from the adjacent spin based on the value of the adjacent spin, so if the value of the adjacent spin is updated at the same time, both updates are duplicated, and energy cannot be minimized and it vibrates. That is, when updating a certain spin, it is necessary to avoid simultaneously updating a different spin connected to the certain spin (a spin directly connected through the interaction coefficient to the certain spin is hereinafter referred to as the adjacent spin).

For this reason, for example, a method is conceivable in which spin units in the spin array are divided into groups such that adjacent spins are not updated at the same time and only one group is simultaneously updated at a time. The group is sequentially updated. Therefore, in the interaction calculation, the interaction control interface160controls the address and timing of the spin unit that performs the interaction calculation.

As described above, the computer using the Ising model described inFIGS. 1 to 3can be said to be a space expansion type computer because it solves the problem by expanding it in the spatial direction. In this specification, the computer using the Ising model is described assuming that the computer is a space expansion type computer, but the same effect can be obtained with a computer not using the Ising model. For example, a neuro computer simulating the work of a neuron is considered as a space expansion type computer as well, but it is necessary for the time expansion type computer to control the neuro computer in the same way, and the same effect can be achieved by the configuration of the present application.

FIG. 4shows an example of the overall configuration of a computer configured with a time expansion type computer and a space expansion type computer. In this example, four space expansion type computers are controlled by a single time expansion type computer. The time expansion type computer302is, for example, a von Neumann type commercial CPU, and the space expansion type computer303is, for example, the Ising chip described above.

The space expansion type computer303of this embodiment is assumed to perform the ground state search of the Ising model described above. In general, in the ground state search, the same problem is solved a plurality of times and the best solution (for example, a solution with the lowest energy) is adopted. At this time, if the plurality of ground state searches can be executed in parallel, an improvement in throughput is expected. In this case, the space expansion type computers303do not necessarily operate in synchronism with each other, and may operate separately and independently from each other. For example, when one ground state search is completed by one space expansion type computer, the second ground state search can be started by the space expansion type computer for the same problem, regardless of the situation of a different space expansion type computer. Therefore, in the present embodiment, it is advantageous to dispose as many space expansion type computers303as possible.

The time expansion type computer302and the space expansion type computers303are directly connected by data lines306through which data is exchanged. Further, control modules301are connected to the time expansion type computer302through control signals304. Further, the control modules301are connected to the space expansion type computers303one-on-one through the control signals305.

With this configuration, data to be calculated by the space expansion type computer303is transferred directly from the time expansion type computer302to the space expansion type computer303, and the calculation result is transferred directly from the space expansion type computer303to the time expansion type computer302. As the data, there are coefficients such as the aforementioned interaction coefficient, external magnetic field coefficient and the like. Further, the spin value may be transferred as necessary.

On the other hand, when controlling the space expansion type computer303, a signal indicating control is transmitted from the time expansion type computer302to the control module301as the control signal304. Based on the control signal304, a signal305for controlling the space expansion type computer303is transmitted from the control module301to the space expansion type computer303. When the calculation by the space expansion type computer303is completed, a signal indicating that calculation is completed is transmitted from the control module301to the time expansion type computer302through the control signal304.

A more detailed breakdown of these signals is shown inFIG. 5. As signals for transmitting and receiving data transmitted from the time expansion type computer302to the space expansion type computer303, there are a clock signal192used for data IO, an R/W control signal193for selecting the data IO of the space expansion type computer, and an IO address191for designating an address for data IO, and the signals are transmitted from the time expansion type computer302to the space expansion type computer303.

The data transmitted from the time expansion type computer302to the space expansion type computer303is problem data, and includes, for example, an interaction coefficient and an external magnetic field coefficient. These problem data are stored in the predetermined memory cell shown inFIG. 3according to the model structure shown inFIG. 2. The storage process may follow the write operation into a general SRAM. In addition, it is possible to set the spin value as necessary and make it a part of the problem data. Alternatively, the initial spin value may be set randomly.

The data transmitted from the space expansion type computer303to the time expansion type computer302is solution data and is a spin value stored in the memory cell N inFIG. 3after a plurality times of interaction calculation. The readout process may follow the read operation from a general SRAM. In this manner, the data used in the space expansion type computer303and the calculation result by the space expansion type computer303are transmitted and received as the IO data191.

Further, an interaction clock181for the calculation by the space expansion type computer303by itself, an interaction address180indicating an address at which the interaction is performed, and a random number142for indicating the state of temperature as necessary are input from the control module301to the space expansion type computer303.

More specifically, when the space expansion type computer303actually operates, problem data191for calculation is first transferred from the time expansion type computer302to the space expansion type computer. The problem data is data corresponding to external magnetic field coefficients and interaction coefficients of the Ising model, and these data are written into memories storing the interaction coefficient of the Ising model (IS0, IS1, IU0, IU1, IL0, IL1, IR0, IR1, ID0, ID1, IF0, and IF1ofFIG. 3). Further, the initial value of the spin value is written.

Next, an instruction for executing the interaction calculation is transmitted from the time expansion type computer302to the control module301through the control signal304. At this time, setting data indicating how much time is to be spent for calculation by the space expansion type computer303(how many times the interaction calculation is to be performed) and how to change the temperature (how to change the generation condition of the random numbers) can also be transmitted to the control module301.

The control module301transmits the clock181for executing the interaction of the Ising model to the space expansion type computer303, and generates and inputs the address180of the spin unit for executing the interaction. The space expansion type computer303performs calculation, using the clock181and the address180. As described above, it is desirable that the spin units that performs the interaction calculation are selected so as not to interfere with each other.

In addition, the control module301manages the time of calculation (or the number of interaction calculations) performed in the space expansion type computer303, and changes the temperature state, that is, the frequency of 1 or 0 included in the random number142, according to the time. With respect to the temperature change, it is possible to perform a change based on the setting information transmitted from the time expansion type computer302.

In the present embodiment, a configuration called a module can be a configuration in which a predetermined process is performed in cooperation with other hardware, by a processor executing the program stored in a memory, in a so-called microcomputer equipped with an input and output device, a processing device, and the memory. Alternatively, functions equivalent to the functions configured by the software can be realized by hardware such as field programmable gate array (FPGA) and application specific integrated circuit (ASIC). In the present embodiment, any configuration can be adopted.

FIG. 6shows an example of the overall operation flow of the system ofFIG. 4. The start of the operation can be executed in response to an instruction by the operator to the time expansion type computer302or automatically (S401). Using the IO address190, the IO clock192, and the IO data191, from the time expansion type computer302, the interaction coefficient data is transmitted to the space expansion type computer303, and the value of the coefficient is set (S402). Further, in some cases, similarly, the spin value is also input (S403).

Next, a control signal304is transmitted from the space expansion type computer303to the control module301, and interaction calculation is started in each time expansion type computer302(S404). During the interaction calculation, a clock181and an address180for interaction and a random number142are supplied from the control module301, and interaction is executed (S405). In the control module301, it is checked whether or not interaction is performed a predetermined number of times (S406). If it is not performed the predetermined number of times, the process returns to S405and interaction calculation is executed. In a case where it is performed the predetermined number of times, the control module301notifies the time expansion type computer302that the operation is ended (S407). Along with this, the time expansion type computer302reads out the calculation result191from the data line, using the IO clock192and the address190(S408).

The above operations of S404to S408correspond to one ground state search. In the present embodiment, the above-described operations of S404to S408are independently performed by a plurality of space expansion type computers303. Normally, the ground state search is performed a plurality of times, and the best result is adopted. Therefore, each space expansion type computer303is configured such that once the operation is ended (S409), the process returns to S403again, and the ground state search is repeated. The result is accumulated in the time expansion type computer302sequentially in S408, Finally, the best solution may be selected.

FIG. 7shows the internal configuration of the control module301necessary for executing these operations. The control module301includes a setting register312that holds the setting data transmitted from the time expansion type computer302, a timer (or a counter)313that manages the time and temperature during which the space expansion type computer303is operating, a random number generator314that generates a random number to be used, and a nonvolatile memory315that holds data specific to each chip. The control logic module311generates an interaction clock181, an interaction address180, and a random number142, based on the information on these constituent elements.

When the calculation by the space expansion type computer303is completed, the time expansion type computer302is notified that the calculation is completed through the control signal304. Since the nonvolatile memory315holds information specific to the chip of the space expansion type computer, it is possible to set the control signal of the space expansion type computer303according to the chip. For example, if the maximum operating frequency of the corresponding space expansion type computer303is held, by generating and inputting a clock corresponding to the maximum operating frequency, the space expansion type computer303can operate at maximum speed.

As described above, by using the present embodiment, the control module301can execute the calculation of the space expansion type computer303, and it is possible to suppress the resources of the time expansion type computer302for controlling the space expansion type computer303.

FIG. 8is a block diagram showing the spin unit200inside the space expansion type computer303controlled by the control module301. As described above, in the present embodiment, the interaction calculation of each spin unit is controlled so as not to interfere with each other. In the example ofFIG. 8, the spin unit is divided into two groups A and B, and interaction calculation is performed alternately.

The interaction clock181, the interaction address180, and the random number142, from the control module301, are distributed to each spin unit200. The signals from the control module301may be used as they are, or they may be used by adjusting the phase and frequency thereof. Though these signal lines are configured independently, they are shown by one line inFIG. 8for the sake of convenience. IDs such as “N000” and codes of A and B are attached to the spin units200. A and B indicate groups which are alternately interacted by the interaction address decoder140so that adjacent spins are not rewritten at the same time.

FIG. 9shows control signals input to the spin unit ofFIG. 8. The interaction address180and the interaction clock181cause groups A and B of the spin unit to perform interaction calculation alternately. The random number142indicated by ri[t] is not limited to 1 bit, but in this example, it is a 1 bit pulse having values of +1 and −1. This signal can be generated by the normal random number generator314in the control module301.

The random effect control signal (RE) enables the random number142while this signal is HIGH and disables it during LOW. While the random number142is invalid, the value of ri[t] is 0, and while it is valid, the value of ri[t] has a random value of +1 or −1. Normally, at the initial stage of the ground state search, the random number142is validated. If necessary, the random effect control signal RE can be supplied from the control module301to the space expansion type computer303. The space expansion type computer303inverts the value of the memory cell N according to the value of the random number.

The random effect control signal (RE) and the random number signal142ofFIG. 7are input to the space expansion type computer303, a logical sum with the random number142is generated, and it is possible to control (mask) the validity and invalidity of the random number. Further, instead of masking random numbers by supplying the random effect control signal (RE) to the space expansion type computer303, the random number142may be masked in the control logic module311of the control module301, and the masked random number may directly be supplied to the space expansion type computer303.

In the present embodiment, an example of Ising chip is shown as the space expansion type computer, but it is not necessarily limited to Ising chip. For example, in a neurocomputer, which is a space expansion type computer having a neural network, control of data input and output signals, clock signals in a case of a synchronous type, and communication between chips is performed by an external space expansion type computer. In the neural network, the coefficients of the Ising model can be replaced with parameters representing the behavior of neurons, such as weights and bias parameters. For the sake of convenience in the present specification, these coefficients and parameters may be collectively referred to as “coefficient” in some cases.

In Embodiment 1, the control module301has nothing to do with the data to be transmitted from the time expansion type computer to the space expansion type computer. However, data transmission and reception can also be executed by the control module. In Embodiment 2, the aspect in that case will be described.

FIG. 10shows an overall configuration of a computer configured with the time expansion type computer302and the space expansion type computer303. Four space expansion type computers are controlled by one time expansion type computer. The difference fromFIG. 4is that both the control signal and the calculation data to be executed by the space expansion type computer are transmitted from the time expansion type computer302to the control module321. From these data and control signals322, the control module321transmits calculation data and control signals323to the space expansion type computer.

FIG. 11shows details of data and control signals. From the time expansion type computer302, a signal324for control and IO data325for calculation are transmitted to the control module321. Further, an interaction clock181for the interaction calculation by the space expansion type computer by itself, an interaction address180indicating an address at which the interaction is performed, and a random number142for indicating the state of temperature are input from the control module321to the space expansion type computer303. Further, there are a clock signal192used for data IO, an R/W control signal193for selecting the data IO of the space expansion type computer, and an IO address191for designating an address for data IO, and the signals are transmitted from the control module321to the space expansion type computer303.

When the space expansion type computer303operates, first, data325for calculation is transferred from the time expansion type computer302to the control module321. The data is data corresponding to the interaction coefficient of the Ising model. Further, the data is transmitted from the control module321to the space expansion type computer303as the data191. The data is written into the memory that stores the interaction of the Ising model, using the IO address191, the clock signal192, and the R/W control signal193, as in Embodiment 1.

Next, an instruction for executing the calculation is transmitted from the time expansion type computer302to the control module321through the control signal324. At this time, the setting data is also transmitted to the control module321. The setting data includes, for example, data for setting how much time is to be spent for interaction calculation by the space expansion type computer303. Alternatively, the setting data may be data for setting how many times interaction calculation is performed. Further, data for setting how to change the temperature may be included. Specifically, the temperature setting data includes, for example, data for setting the start and stop of generation of a random number. Alternatively, data for temporally controlling the ratio between 0 and 1 included in the random number may be included.

The control module321transmits the clock181for executing the interaction of the Ising model to the space expansion type computer303, and generates and inputs the address180for executing the interaction. The space expansion type computer303performs interaction calculation, using these clocks and address signals. In addition, the control module321manages the time of calculation performed in the space expansion type computer303, and changes the temperature state, that is, the frequency of 1 or 0 included in the random number142, according to the time. With respect to the temperature change, it is possible to perform a change based on the setting information transmitted from the time expansion type computer.

FIG. 12shows an internal configuration of the control module321necessary for executing these operations. The control module321includes a setting register312that holds the setting data transmitted from the time expansion type computer302, a timer313that manages the time and temperature during which the space expansion type computer is operating, a random number generator314that generates a random number to be used, and a memory that temporarily holds data used in the space expansion type computer and a result of the space expansion type computer. The control logic module326generates an interaction clock181, an interaction address180, and a random number142, based on the information on these constituent elements.

When exchanging data with the space expansion type computer303, the I/O clock192, the R/W control signal193, and the IO address190are generated. When the calculation by the space expansion type computer is completed, the I/O clock192, the R/W control signal193, and the IO address190are generated, the calculation result is read from the space expansion type computer and stored in the memory327, and the time expansion type computer is notified that the calculation is completed through the control signal304. At the same time, the calculation result held in the memory327is transferred to the time expansion type computer302through the I/O data325.

As described above, by using the present embodiment, the control module can execute the calculation of the space expansion type computer, and it is possible to suppress the resources of the time expansion type computer for controlling the space expansion type computer.

In Embodiment 1, the control module301is disposed as a module separate from the time expansion type computer and the space expansion type computer. However, this module can be included in the time expansion type computer or the space expansion type computer. In Embodiment 3, an aspect of a case where it is included in the space expansion type computer will be described as an example.

FIG. 13shows an overall configuration of a computer configured with the time expansion type computer and the space expansion type computer. Four space expansion type computers are controlled by one time expansion type computer. The difference fromFIG. 4is that the control module331is included in the space expansion type computer332. The control signal304and the data305are transmitted directly to the space expansion type computer332from the time expansion type computer302.

A more detailed breakdown of these signals is shown inFIG. 14. As signals for transmitting and receiving data transmitted from the time expansion type computer332to the space expansion type computer303, there are a clock signal192used for data IO, an R/W control signal193for selecting the data IO of the space expansion type computer, and an IO address190for designating an address for data IO, and the signals are transmitted from the time expansion type computer302to the space expansion type computer332. Further, the data used in the space expansion type computer332and the calculation result by the space expansion type computer332are transmitted and received among computers, as the IO data191.

When the space expansion type computer actually operates, first, data for calculation is transferred from the time expansion type computer302to the space expansion type computer332. The data is data corresponding to the interaction coefficient of the Ising model, and these data are written into a memory that stores the interaction of the Ising model. Next, an instruction for executing the calculation is transmitted from the time expansion type computer302to the control module331through the control signal304. At this time, setting data indicating how much time is to be spent for calculation by the space expansion type computer332and how to change the temperature is also transmitted to the control module331. The control module331transmits the clock for executing the interaction of the Ising model to the spin unit inside the space expansion type computer332, and generates and inputs the address for executing the interaction. The space expansion type computer332performs calculation, using the clock and the address signal. In addition, the control module331manages the time of calculation performed in the space expansion type computer332, and changes the temperature state, that is, the frequency of 1 or 0 included in the random number sequence according to the time. With respect to the temperature change, the change is performed based on the setting information transmitted from the time expansion type computer302. Therefore, the control module331itself can have the same configuration as the control module301ofFIG. 7described in Embodiment 1.

As described above, by using the present embodiment, the control module can execute the calculation of the space expansion type computer, and it is possible to suppress the resources of the time expansion type computer for controlling the space expansion type computer.

In Embodiments 1 to 3, the case where the temperature scheduling, which is one control element of the space expansion type computer, is determined by time has been described.

FIG. 15is an example of a concept of temperature scheduling. This can be realized by lowering the ratio of 1 of the random number sequence over time as shown inFIG. 15, for example. In this way, in a case where the scheduling is determined in advance, the space expansion type computer may be operated according to a schedule which is determined in advance by the time expansion type computer or the control module. For example, this schedule is transmitted from the time expansion type computer to the control module as a part of the setting data, stored in the setting register of the control module, and control of the random number sequence is performed according to the schedule.

However, it is inherently desirable that the ratio of 1 decreases, as the energy of the Ising model, which is a space expansion type calculator, decreases. Therefore, it becomes possible to obtain a solution with higher accuracy, by checking the energy of the Ising model and changing the ratio of 1 included in the random number sequence according to the energy. In Embodiment 4, an example of a control module for realizing the operation is shown. A case where parts other than the control module correspond to Embodiment 2 (FIG. 10andFIG. 11) will be described, but the same configuration is adopted in other cases as well.

FIG. 16shows an internal configuration of the control module. The control module341includes a setting register312that holds the setting data transmitted from the time expansion type computer302, a random number generator314that generates random numbers to be used, a memory327that temporarily holds data used in the space expansion type computer303and the result of the space expansion type computer303, and an energy calculation module343that calculates the energy of the Ising model. The control logic module342generates the interaction clock181, the interaction address180, and the random number142, based on the information of these components.

When exchanging data with the space expansion type computer303, the I/O clock192, the R/W control signal193, and the IO address190are generated. When the calculation by the space expansion type computer303is completed, the I/O clock192, the R/W control signal193, and the IO address190are generated, the calculation result is read from the space expansion type computer303and stored in the memory327, and the time expansion type computer302is notified that the calculation is completed through the control signal304. At the same time, the calculation result held in the memory327is transferred to the time expansion type computer through the I/O data325.

When the space expansion type computer303executes the calculation, the space expansion type computer303is supplied with the interaction clock181and executes the interaction calculation. Further, the state on the way of the space expansion type computer is read into the control module301at any time by using the IO function. More specifically, for example, the value stored in the memory cell N inFIG. 3is read, using the IO clock192, the R/W control signal193, and the I/O address190. The energy calculation module343calculates the energy of the Ising model using the read data, and the ratio between 1 and 0 in the random number sequence is changed according to the energy. More specifically, the ratio of 1 decreases as energy decreases. As a method of changing the ratio between 1 and 0 in the random number sequence, various known methods may be applied. By doing this type of operation, it becomes possible to operate a space calculation type computer with high accuracy.

FIG. 17shows an example of a processing flow. In S422, data is transmitted from the time expansion type computer to the space expansion type computer through the IO address line, the IO clock, and the IO data, and the value of the coefficient is set. Further, in some cases, the spin value is also input in S423, similarly. Next, in S424, a control signal is transmitted from the space expansion type computer to the control module, and interaction calculation is started. During the interaction calculation, in S425, a clock and an address for interaction and a random number are supplied from the control module, and interaction is executed. In S426, energy calculation of the Ising model in that state is executed in the control module. In S427, it is checked whether or not the energy has fallen below a predetermined value, and in a case where it has fallen below, the process returns to S425and interaction calculation is executed. In a case where the energy reaches a predetermined value, in S428, the control module notifies the time expansion type computer that the operation is ended. Along with this, in S429, the time expansion type computer reads out the calculation result, using the IO clock, the address, and the data line.

In the example described above, the random number generator is used, but as another means for randomly inverting the spin value, there is a method of inducing a bit error of the memory cell by lowering the power supply voltage supplied to the memory cell expressing the spin, and randomly changing the spin arrangement. For this purpose, among the memory cells of the spin unit200, the memory cell N storing the spin value operates with the voltage supplied through a spin dedicated power supply line. Further, memory cells holding coefficients and constituent elements other than the memory cells, for example, logic gates for calculating interactions, are operated with a voltage normally supplied from a power supply line.

With respect to the bit error rate of the memory cell, as the voltage decreases from a proper voltage for recording, the bit error rate worsens in proportion to the decrease in the voltage. Utilizing this state, the error rate is set to a high state at the initial stage of the ground state search, and the voltage is changed to a state where the bit error rate is low as the search progresses. For example, in a case of changing the configuration ofFIG. 5to this system, a spin dedicated power supply line may be provided in the space expansion type computer303, and a control signal for controlling the voltage of the spin dedicated power supply line may be used instead of the random number142.

Hitherto, the invention made by the present inventor has been described in detail based on the embodiments. As described in the embodiments, the present invention can be applied to a space expansion type computer handling Ising models, neural networks, and the like. However, it is needless to say that the present invention is not limited to the above-described embodiments, and various modifications can be made without departing from the gist thereof.

For example, the above embodiments have been described in detail in order to explain the present invention in an easy-to-understand manner and are not necessarily limited to those having all the configurations described. Further, with respect to a part of the configuration of the embodiments, addition, deletion, and replacement of other configurations can be performed.

INDUSTRIAL APPLICABILITY

The present invention can be applied to an information processing system handling various calculations.

REFERENCE SIGNS LIST