Patent Description:
An optimization problem is the problem of finding a point (i.e., solution) belonging to search space that minimizes the value of an objective function defined in the search space. When the search space is a discrete set having a finite number of elements, the minimum value can be found in an exhaustive manner by comparing objective function values that are calculated at all the points belonging to the search space. As the number of dimensions of the search space increases, the number of elements in the set increases explosively, which makes it substantially impossible to perform an exhaustive search.

Simulated annealing mimics a metal annealing process that yields a crystal structure with few defects by gradually cooling a metal. Each point belonging to the search space corresponds to a respective state of physical phenomena, and the objective function corresponds to the energy of the system at each state. The concept of temperature is introduced to the probability of occurrence of each state. A probability distribution is then configured such that at any given temperature, the smaller the energy at a state is, the higher the probability of occurrence of the state is, and such that the lower the temperature is, the greater the ratio between the probabilities of occurrences of two states having different energies is. Lowering temperature at a sufficiently slow rate, while creating successive states with gradual state changes such as to realize the above-noted probability distribution, may allow the state to be converged on an optimum solution having the smallest energy value.

When a change from the energy of a current state to the energy of a next state is denoted as ΔE, the probability P of a transition from the current state to the next state is calculated as the value of a function having ΔE and temperature as variables. Lowering temperature at a sufficiently slow rate, while performing state transitions with the probability P, allows the state to be converged on an optimum solution having the smallest energy value. In an annealing process, generally, a uniform random number r (<NUM><r<<NUM>) is used in order to achieve the act of making a transition to a next state with the probability P. State transition is controlled such that, upon comparison of the uniform random number r with the probability P, a result of P>r causes a state transition, and a result of P≤r does not cause a state transition.

A true random number is difficult to generate by use of a circuit. Typically, a pseudo random number is used that is generated by deterministic calculations performed by a pseudo random number generator such as a linear feedback shift register or a Mersenne twister. In the case of using such a pseudo random number, upon determining an initial value setting (i.e., the seed), the sequence of random numbers generated thereafter is a deterministic sequence responsive to the seed. As a result, two random number sequences having the same seed are completely the same random number sequence.

In an optimization apparatus, there may be a need in some cases to check intermediate statuses during an annealing process for the purpose of tuning the annealing process or the like. For example, parameters such as spin values and energy values may be read out from the optimization apparatus at every <NUM>-th iteration with respect to a problem in which a state may converge on a solution close to the optimum solution after <NUM> iterations (i.e., <NUM> state transitions). In order to read out the parameters, the annealing process by the optimization apparatus is temporarily suspended, and, then, the parameters are read from the internal registers of the apparatus to the outside.

The purpose is to know the intermediate statuses leading to the final result that will be obtained after performing <NUM> iterations. Because of this, the final result and intermediate statuses are preferably identical between the case in which <NUM> iterations are continuously performed and the case in which <NUM> iterations are intermittently performed by running <NUM> iterations at a time. In a conventional optimization apparatus, however, a random number generator continues functioning to keep generating random numbers during other operations of the optimization apparatus in addition to an annealing process, such as during the reading of parameters. Namely, a random number generation process by the random number generator is being performed independently of the running and suspending of an annealing process. As a result, a random number sequence used in an annealing process is different between the case in which <NUM> iterations are continuously performed and the case in which <NUM> iterations are intermittently performed by running <NUM> iterations at a time. This gives rise to a problem that the final result and intermediate statuses differ.

<CIT> (<NUM>-<NUM>-<NUM>)describes an optimization apparatus and an optimization apparatus control method.

<FIG> is a drawing illustrating an example of the configuration of an optimization apparatus. In <FIG> and the subsequent similar drawings, boundaries between functional or circuit blocks illustrated as boxes basically indicate functional boundaries, and may not correspond to separation in terms of physical positions, separation in terms of electrical signals, separation in terms of control logic, etc. Each functional or circuit block is a hardware module that is physically separated from other blocks to some extent, or may indicate a function in a hardware module in which this and other blocks are physically combined together.

The optimization apparatus illustrated in <FIG> includes a control unit <NUM> and an annealing unit <NUM>. The control unit includes an operation instruct unit <NUM>, an initial value transmitting unit <NUM>, and a control data storage unit <NUM>. The annealing unit <NUM> includes a random-number-generation-&-initial-value-setting unit <NUM> and an annealing calculation unit <NUM>.

The annealing calculation unit <NUM> of the annealing unit <NUM> performs an annealing process by successively changing a state stored in an internal register. The annealing calculation unit <NUM> calculates an evaluation function value responsive to each state as the energy of each state, and controls a transition from a current state to a next state based on the evaluation function value and current temperature.

Specifically, the annealing calculation unit <NUM> calculates the evaluation function value E of the current state S, and also calculates the evaluation function value E' of a candidate next state S' that has a slight change from the current state S, followed by calculating a difference ΔE (=E'-E). In the case in which the Boltzmann distribution is used to represent the probability distribution of a state S and the Metropolis method is used, for example, probability P with which a transition to the next state S' occurs may be defined by the following formula. <MAT> Here, β is thermodynamic beta (i.e., the reciprocal of absolute temperature T), and is equal to <NUM>/T. The function min[<NUM>, x] assumes a value of <NUM> or a value of x, whichever is smaller. According to the above formula, a transition to the next state occurs with probability "<NUM>" in the case of ΔE≦<NUM>, and a transition to the next state occurs with probability P (=exp(-βΔE)) in the case of <NUM><ΔE. The Metropolis method is a non-limiting example, and other transition control algorithms such as Gibbs sampling may alternatively be used.

The form of the evaluation function is not limited to a particular form, and may be an energy function based on an Ising model, for example, as shown below. <MAT> Here, Σ represents a sum with respect to the suffix i or j from <NUM> to M (M: positive integer). The state S is a state having M spins as follows. <MAT> Each spin assumes a value of -<NUM> or +<NUM>. Wij is a weighting factor for the coupling between spins, and may be such that Wjj=<NUM>. Further, bi is a bias.

The probability P defined by the formula (<NUM>) and the evaluation function E defined by the formula (<NUM>) are examples only. The probability and evaluation function used for an annealing process are not limited to the noted probability and evaluation function. Further, the annealing unit <NUM> may be such that a plurality of annealing calculation units <NUM> calculate state transitions in a plurality of systems in parallel, rather than a single annealing calculation unit <NUM> calculating a state transition in a single system.

In an annealing process performed by the annealing calculation unit <NUM>, a uniform random number r (<NUM><r<<NUM>) generated by the random-number-generation-&-initial-value-setting unit <NUM> is used in order to achieve the act of making a transition to a next state with the probability P. State transition is controlled such that, upon comparison of the uniform random number r with the probability P, a result of P>r causes a state transition, and a result of P≤r does not cause a state transition. For example, the probability Pi of inversion with respect to each of the spins xi (i=<NUM> to M) in the above-noted formula (<NUM>) may be calculated as the probability P defined by the formula (<NUM>) with respect to an inversion of the spin of interest. Then, inversion rules may be such that the spin can be inverted when Pi>r, and should not be inverted when Pi≤r. In this case, one of the spins for which the rules allow spin inversion is randomly selected, and is inverted to achieve a state transition.

Each time the annealing calculation unit <NUM> compares the probability P with the uniform random number r, this uniform random number r may be a random number newly generated by the random-number-generation-&-initial-value-setting unit <NUM>. The random-number-generation-&-initial-value-setting unit <NUM> generates random numbers in synchronization with the advancement of an annealing process, and also sets the initial values of a state S (i.e., the initial values of respective spins), the weighting factors Wij for coupling between the spins, the biases bi, and temperature values in the annealing calculation unit <NUM> at the start of the annealing process.

The control unit <NUM> controls the operation of the annealing unit <NUM>. The initial value transmitting unit <NUM> of the control unit <NUM> transmits the initial parameters set from an external source (i.e., the initial values of a state S, the weighting factors Wij for coupling between the spins, the biases bi, temperature values, and the like) to the random-number-generation-&-initial-value-setting unit <NUM> of the annealing unit <NUM>. The control data storage unit <NUM> of the control unit <NUM> stores therein control data set from an external source (i.e., an iteration count limit and data indicative of an operation mode). The operation instruct unit <NUM> of the control unit <NUM> controls the random number generation process of the random-number-generation-&-initial-value-setting unit <NUM> and the annealing process of the annealing calculation unit <NUM> based on the control data stored in the control data storage unit <NUM>.

The portion (i.e., random number generator) of the random-number-generation-&-initial-value-setting unit <NUM> operates either in a first operation mode in which to generate a random number sequence after performing an initialization or in a second operation mode in which to generate a random number sequence without performing such an initialization. In general, a random number generator performs initialization such as setting a seed value and initializing memory areas before performing a process of generating a random number sequence. In the first operation mode, such an initialization is performed, followed by performing a process of generating a random number sequence. In the second operation mode, such an initialization is not performed, and a process of generating a random number sequence is performed based on the existing status of internal registers, memories, and the like at that point in time. Accordingly, use of the second operation mode at the time of restarting a random number generation process after temporarily suspending a random number generation process makes it possible to generate the same random number sequence as in the case in which a random number generation process is continuously performed without any interruptions.

At the time the annealing calculation unit <NUM> suspends an annealing process, the random number generator suspends its operation, and may retain the internal states existing at the time of suspension. At the time the annealing calculation unit <NUM> restarts the annealing process, the random number generator restarts its operation from the internal states existing at the time of suspension, without performing initialization. This arrangement reliably generates the same random number sequence as in the case in which a random number generation process is continuously performed without any interruptions.

In the following description, for the sake of ease of understanding, the first operation mode is referred to as a normal operation mode, and the second operation mode is referred to as a continuation operation mode.

Which one of the operation modes is used for the operation of the random number generator is determined by the operation instruct unit <NUM> based on the control data supplied from the control data storage unit <NUM>. The operation instruct unit <NUM> causes the random number generator to start operating in the normal operation mode when causing the annealing calculation unit <NUM> to perform an annealing process from the initial state. In order to cause the random number generator to operate in the normal operation mode, a user may set data in the control data storage unit <NUM> which provides an express indication of the normal operation mode from outside the optimization apparatus. Alternatively, the number of iterations that have been performed in a particular annealing process may be kept of record, and the random number generator may be controlled to operate in the normal operation mode when the number is zero at the start or restart of the particular annealing process.

The operation instruct unit <NUM> stops the operation of the random number generator when the annealing calculation unit <NUM> suspends an annealing process upon completing the execution of a predetermined number of iterations. The number of iterations is the number of state transitions performed by the annealing calculation unit <NUM>.

The operation instruct unit <NUM> causes the random number generator to restart its operation in the continuation operation mode when causing the annealing calculation unit <NUM> to resume the annealing process. In order to cause the random number generator to operate in the continuation operation mode, a user may set data in the control data storage unit <NUM> from outside the optimization apparatus at the restart of the annealing process, and the data provides an express indication of the continuation operation mode. Alternatively, the number of iterations that have been performed in a particular annealing process may be kept of record, and the random number generator may be controlled to operate in the continuation operation mode when the number is not zero at the start or restart of the particular annealing process.

<FIG> is a drawing illustrating an example of the configuration of the random number generator embedded in the random-number-generation-&-initial-value-setting unit <NUM>. The random number generator illustrated in <FIG> which is a linear feedback shift register includes <NUM> flip-flops <NUM>-<NUM> through <NUM>-<NUM>, <NUM> selectors <NUM>, and XOR gates <NUM> through <NUM>.

The flip-flops <NUM>-<NUM> through <NUM>-<NUM> are connected in series such that a data output Q is coupled to a data input D, thereby constituting a shift register which operates in synchronization with a clock signal CLK. The XOR gates <NUM> through <NUM> calculate an exclusive OR of the <NUM>-th, <NUM>-th, <NUM>-th, and <NUM>-th flip-flops, and the calculated outcome is applied as a feedback input to the first flip-flop <NUM>-<NUM> of the shift register. This feedback input achieves a linear feedback shift register.

The selectors <NUM> are provided in one-to-one correspondence with the flip-flops <NUM>-<NUM> through <NUM>-<NUM> to select either the input for shift operations or a seed value SEED (<NUM> bits) for initialization. The values selected by the selectors <NUM> are loaded into the flip-flops <NUM>-<NUM> through <NUM>-<NUM> in synchronization with the clock signal CLK. At the time of initialization, an initialization signal INISET may be set to <NUM>, for example. In response to this, the <NUM> selectors <NUM> select the <NUM> respective bits of the seed value SEED. The <NUM> respective bits of the seed value SEED are then stored in the <NUM> flip-flops <NUM>-<NUM> through <NUM>-<NUM>. At the time of shift operations, the initialization signal INISET may be set to <NUM>, for example. In response to this, the selectors <NUM> select the inputs for shift operations (i.e., the outputs of the preceding flip-flops or the feedback input). The selected values are then stored in the <NUM> flip-flops <NUM>-<NUM> through <NUM>-<NUM>.

After setting the seed value at the initialization, shift operations are successively performed in synchronization with the clock signal CLK, so that the linear feedback shift register generates a random number sequence. Outputting an N-bit random number as a uniform random number r is achieved by consolidating N successive outputs of the XOR gate <NUM> as a uniform random number r. Alternatively, an XOR gate may be provided to calculate an XOR of the outputs Q of a two or more predetermined number of flip-flops among the flip-flops <NUM>-<NUM> through <NUM>-<NUM>. N successive outputs of the XOR gate may then be output as a uniform random number r.

In the normal operation mode described above, the initialization signal INISET may be set to <NUM>, for example, to set the seed value SEED to the flip-flops <NUM>-<NUM> through <NUM>-<NUM> in synchronization with the clock signal CLK to perform initialization. After the initialization, the initialization signal INISET may be set to <NUM>, for example, to perform shift operations successively in synchronization with the clock signal CLK, thereby generating a random number sequence.

In order to suspend a random number generation process, the pulses of the clock signal CLK are stopped from being supplied so as to retain the bit values stored in the flip-flops <NUM>-<NUM> through <NUM>-<NUM>. The initialization signal INISET is kept in the state in which it is set to <NUM>.

In the continuation operation mode previously described, while keeping the state in which the initialization signal INISET is set to <NUM>, the pulses of the clock signal CLK are supplied again to perform shift operations successively in synchronization with the clock signal CLK, thereby generating a random number sequence. Namely, shift operations are successively performed to generate a random number sequence as a continuation from the state in which the values stored in the flip-flops <NUM>-<NUM> through <NUM>-<NUM> are the same as at the time of suspension.

Use of a linear feedback shift register as illustrated in <FIG> as a random number generator enables the generation of pseudo-random numbers by use of a simple, small-scale circuit configuration. In the case of the linear feedback shift register illustrated in <FIG>, the period of pseudo-random numbers is <NUM>.

<FIG> is a drawing illustrating another example of the configuration of the random number generator embedded in the random-number-generation-&-initial-value-setting unit <NUM>. The random number generator illustrated in <FIG> which is a Mersenne twister includes an initialization block <NUM>, a memory circuit <NUM>, a selector circuit <NUM>, a combinatorial logic circuit <NUM>, an address counter <NUM>, and a flip-flop <NUM>.

The memory circuit <NUM> has addresses <NUM> through <NUM>, each of which stores therein <NUM>-word (i.e., <NUM> bits) data. At the time of initialization, the initialization signal INISET may be set to <NUM>, for example, to place the selector circuit <NUM> in such a state as to select the output value of the initialization block <NUM>. The initialization block <NUM> performs predetermined arithmetic operations based on a seed value SEED such as multiplication, addition, and bit shifts so as to calculate and output values that are to be stored in the respective addresses of the memory circuit <NUM>. The output values calculated by the initialization block <NUM> are successively stored via the selector circuit <NUM> in the respective addresses <NUM> through <NUM> of the memory circuit <NUM> in the first cycle to the <NUM>-th cycles of the initialization process. In so doing, the address value indicated by the address counter <NUM> successively increases from <NUM> to <NUM> in synchronization with the clock signal CLK. In the first cycle of the initialization process, the initialization block <NUM> calculates an output value by performing a predetermined arithmetic operation on the seed value SEED. The output value calculated by the initialization block <NUM> is stored in the memory circuit <NUM> and also stored in the flip-flop <NUM>. In the second cycle through the <NUM>-th cycle, the initialization block <NUM> calculates output values by performing predetermined arithmetic operations on the value stored in the flip-flop <NUM>.

As a further initialization process following after the above-described process, the initialization signal INISET may be set to <NUM>, for example, to place the selector circuit <NUM> in such a state as to select the output value of the combinatorial logic circuit <NUM>. The combinatorial logic circuit <NUM> may then perform arithmetic operations on the values stored at the respective addresses of the memory circuit <NUM>. Specifically, the stored values may be retrieved from the memory circuit <NUM> in response to the address value indicated by the address counter <NUM>, and, then, the combinatorial logic circuit <NUM> performs arithmetic operations inclusive of bit shits, EXOR, multiplication, and addition, followed by writing the result of the operation back to the memory circuit <NUM>. With this, the initialization process comes to an end.

At the time of a random number generation process following the initialization, the initialization signal INISET may be set to <NUM>, for example, to place the selector circuit <NUM> in such a state as to select the output value of the combinatorial logic circuit <NUM>. The address counter <NUM> outputs addresses in synchronization with the clock signal CLK so that the stored values are retrieved from the memory circuit <NUM> in response to these addresses. The combinatorial logic circuit <NUM> performs predetermined arithmetic operations inclusive of AND, OR, bits shifts, XOR, and the like on the received retrieved values. The calculated values are then stored via the selector circuit <NUM>, at the addresses in the memory circuit <NUM> indicated by the address counter <NUM>. At the (624n+<NUM>)-th random number generation (n: integer greater than or equal to <NUM>), a process is performed that updates the values stored in the respective addresses <NUM> through <NUM> in the memory circuit <NUM> as described above. The address counter <NUM> thereafter outputs an address that is successively increased from <NUM> to <NUM>, and the stored values are retrieved from such addresses in the memory circuit <NUM>. Random numbers are generated by performing predetermined arithmetic operations inclusive of bit shifts, AND, and XOR on the retrieved values. In this manner, (624n+m)-th random number generations (m: integer from <NUM> to <NUM>) are performed. Thereafter, the process described above is repeated multiple times.

In the normal operation mode described above, the initialization signal INISET may be set to <NUM>, for example, to set initial values to the respective addresses <NUM> through <NUM> in the memory circuit <NUM> in synchronization with the clock signal CLK to perform initialization. After the initialization, the initialization signal INISET may be set to <NUM>, for example, to perform retrieval from the memory circuit <NUM> and arithmetic operations by the combinatorial logic circuit <NUM> successively in synchronization with the clock signal CLK, thereby generating a random number sequence.

In order to suspend a random number generation process, the pulses of the clock signal CLK are stopped from being supplied so as to retain the values stored in the memory circuit <NUM>. Further, the internal state of the address counter <NUM> (i.e., the output address value) may also be retained. Moreover, the initialization signal INISET may be kept in the state in which it is set to <NUM>.

In the continuation operation mode previously described, while keeping the state in which the initialization signal INISET is set to <NUM>, the pulses of the clock signal CLK are supplied again to perform retrieval from the memory circuit <NUM> and arithmetic operations successively in synchronization with the clock signal CLK, thereby generating a random number sequence. Namely, retrieval from the memory circuit <NUM> and arithmetic operations are successively performed to generate a random number sequence as a continuation from the state in which the output address value of the address counter <NUM> and the stored values of the memory circuit <NUM> are the same as at the time of suspension.

Use of a Mersenne twister as illustrated in <FIG> as a random number generator enables the generation of high-quality pseudo-random numbers. In the case of the Mersenne twister illustrated in <FIG>, the period of pseudo-random numbers is <NUM><NUM>-<NUM>, which is an extremely long length.

<FIG> is a drawing illustrating a synchronous relationship in step counts between an annealing process and a random number generation process in the case in which the iterations of the annealing process are continuously performed. As illustrated in <FIG>, when the iterations of an annealing process are continuously performed from the first round to the <NUM>-th round, the step count of a random number generation process also increases in synchronization with increases in the number of iterations of the annealing process (i.e., the step count illustrated in <FIG>). Here, the step count of a random number generation process is a number obtained by counting, as one step, a random number generation process that generates a number of random numbers used in a single iteration of the annealing process.

<FIG> is a drawing illustrating a synchronous relationship in step counts between an annealing process and a random number generation process in the case in which the annealing process is temporarily suspended and restarted. As illustrated in <FIG>, when the iterations of an annealing process are suspended after <NUM> rounds, the step count of a random number generation process also stops after successively increasing from <NUM> to <NUM>, in synchronization with the stopping of the step count of the annealing process upon successively increasing from <NUM> to <NUM>. After the suspension, the values of the internal registers of the annealing calculation unit <NUM> are read from the outside by taking <NUM> clock cycles, for example. Thereafter, the annealing process restarts from the <NUM>-th iteration. In synchronization with the step count of the annealing process that stops upon successively increasing from <NUM> to <NUM>, the step count of the random number generation process also stops upon successively increasing from <NUM> to <NUM>.

In the optimization apparatus of the present disclosures, the operations in "synchronization", regarding the annealing process and the random number generation process that operate in synchronization with each other when starting, suspending, and restarting their operations, does not have to be operations that are synchronized with a common clock signal used across the entirety of the optimization apparatus. For example, the phrase "suspend the operations in synchronization" does not have to refer to the suspension of operations of the annealing process and the random number generation process at the same cycle of a common clock signal. It suffices for the operations "in synchronization" to be operations that can maintain conditions in which random numbers generated by the random number generation process are in one-to-one correspondence to random numbers used in the annealing process. Namely, the condition is satisfactory if the one-to-one correspondence does not collapse as in the cases in which the random number generation process generates excessive random numbers that are not used by the annealing process, or in which a random number generated by the random number generation process is used twice erroneously by the annealing process.

In other words, it suffices for one-to-one correspondence to be kept, without an excess or a deficit, between the random numbers generated by the random number generator and the random numbers utilized by the annealing calculation unit both before and after the annealing calculation unit suspends and resumes the annealing process. With this arrangement, synchronization is established on a step-by-step basis or on a random-number-by-random-number basis, even if synchronization is not established on a clock-pulse-by-clock-pulse basis. As a result, the objective to generate the same annealing results between continuous execution and intermittent execution is more readily achieved.

The optimization apparatus illustrated in <FIG> is provided with the normal operation mode and the continuation operation mode for a random number generation process as previously described, and may selectively use one of these. As a result, when the annealing process and the random number generation process are synchronized both before and after a suspension as illustrated in <FIG>, a random number sequence can be generated that is the same as when the annealing process is continuously performed as illustrated in <FIG>. The final calculation results and intermediate statuses obtained by the annealing calculation unit can thus be completely matched between the continuous execution of the annealing process and the intermittent execution of the annealing process.

<FIG> is a flowchart illustrating an example of the operation of the optimization apparatus illustrated in <FIG>. This example illustrates the operation of the optimization apparatus when a user specifies an operation mode as appropriate.

In <FIG> and the subsequent flowcharts, an order in which the steps illustrated in the flowchart are performed is only an example. The scope of the disclosed technology is not limited to the disclosed order. For example, a description may explain that an A step is performed before a B step is performed. Despite such a description, it may be physically and logically possible to perform the B step before the A step while it is possible to perform the A step before the B step. In such a case, all the consequences that affect the outcomes of the flowchart may be the same regardless of which step is performed first. It then follows that, for the purposes of the disclosed technology, it is apparent that the B step can be performed before the A step is performed. Despite the explanation that the A step is performed before the B step, such a description is not intended to place the obvious case as described above outside the scope of the disclosed technology. Such an obvious case inevitably falls within the scope of the technology intended by this disclosure.

In step S1, the user of the optimization apparatus selects an operation mode. For an annealing process that is started for the first time in the optimization apparatus, the user selects the normal operation mode, which causes data indicative of the normal operation mode to be stored in the control data storage unit <NUM> of the optimization apparatus.

In step S2, the optimization apparatus starts operating, and the operation instruct unit <NUM> refers to the data indicative of an operation mode stored in the control data storage unit <NUM> to determine whether the operation mode setting is the continuation operation mode. When it is found that the operation mode setting is not the continuation operation mode, the procedure proceeds to step S3.

In step S3, the operation instruct unit <NUM> instructs the random-number-generation-&-initial-value-setting unit <NUM> to start generating random numbers in the normal operation mode. In response to this instruction, the random number generator of the random-number-generation-&-initial-value-setting unit <NUM> first performs initialization. At step S4, the random number generator checks whether the initialization is completed. The check in step S4 is repeated until the initialization is completed. Upon completion of the initialization, the procedure proceeds to step S5, in which the operation instruct unit <NUM> instructs the annealing calculation unit <NUM> to start an annealing process. The annealing calculation unit <NUM> starts an annealing process, and the random number generator generates a random number sequence used in the annealing process.

When it is found in step S2 that the operation mode setting is the continuation operation mode, the procedure proceeds to step S6. In step S6, the operation instruct unit <NUM> instructs the annealing calculation unit <NUM> to perform an annealing process, and also instructs the random-number-generation-&-initial-value-setting unit <NUM> to generate random numbers. In response to these instructions, the annealing calculation unit <NUM> restarts the annealing process, and the random number generator of the random-number-generation-&-initial-value-setting unit <NUM> generates a random number sequence used in the annealing process. The annealing process by the annealing calculation unit <NUM> and the random number generation process by the random number generator are controlled to proceed in synchronization with each other.

In step S7, the annealing calculation unit <NUM> performs the annealing process until a termination condition is satisfied. The termination condition may be an iteration count limit stored in the control data storage unit <NUM>. When the termination condition is satisfied, the annealing process by the annealing calculation unit <NUM> is brought to an end. In synchronization with the end of the annealing process, the random number generation process by the random number generator of the random-number-generation-&-initial-value-setting unit <NUM> is also brought to an end.

The synchronization control in step S6 and step S7 may be achieved by communication between the annealing calculation unit <NUM> and the random-number-generation-&-initial-value-setting unit <NUM>, or may be achieved by an instruction from the operation instruct unit <NUM> (e.g., an instruction to perform an iteration on an iteration-by-iteration basis). Alternatively, the random number generator may have been notified of a predetermined iteration count limit by the operation instruct unit <NUM> in advance, and stops the random number generation process after generating a predetermined number of random numbers corresponding to the predetermined iteration count limit. How to achieve synchronization control is not limited to a particular method.

In step S8, the annealing calculation unit <NUM> and the random-number-generation-&-initial-value-setting unit <NUM> retain their internal states existing in the condition in which the operations are suspended. The annealing calculation unit <NUM> may retain all the values stored in the internal registers, such as the spin values of the current state, the values of coupling factors, temperature, the evaluation function value, and the like. Alternatively, the value of the internal registers of the annealing calculation unit <NUM> may be temporarily evacuated to the random-number-generation-&-initial-value-setting unit <NUM>, so that parameters regarding the annealing process are stored in the registers of the random-number-generation-&-initial-value-setting unit <NUM>. The random number generator of the random-number-generation-&-initial-value-setting unit <NUM> may retain the internal states regarding random number generation (e.g., the stored values of the flip-flops of a linear feedback shift register or the stored values of the memory circuit of a Mersenne twister).

In step S9, the results of calculation by the annealing calculation unit <NUM>, i.e., the parameter values (the spin values of the current state and the evaluation function value) stored in the internal registers, are sent to the outside. Based on the results of calculation sent to the outside, the user determines whether to continue the annealing process. In the case of continuing the annealing process, the user sets data indicative of the continuation operation mode in the control data storage unit <NUM> of the optimization apparatus.

In step S10, the operation instruct unit <NUM> checks whether the operation mode setting has been changed. When the normal operation mode is kept without a change, the procedures comes to an end. When the operation mode setting has been changed to the continuation operation mode, the user gives instruction to the optimization apparatus in step S11 to restart the annealing process in the continuation operation mode. Thereafter, the procedure returns to step S2, from which the subsequent processes are repeated.

<FIG> is a drawing illustrating an example of the more detailed configuration of the optimization apparatus. The optimization apparatus illustrated in <FIG> includes the control unit <NUM> and the annealing unit <NUM>.

The control unit includes the operation instruct unit <NUM>, the initial value transmitting unit <NUM>, the control data storage unit <NUM>, and a seed storage unit <NUM>. The operation instruct unit <NUM> includes an annealing initial value indicating unit <NUM>, a random number generation instruct unit <NUM>, and an annealing process instruct unit <NUM>. The control data storage unit <NUM> includes an iteration count limit storage unit <NUM> and an operation mode storage unit <NUM>.

The annealing unit <NUM> includes the random-number-generation-&-initial-value-setting unit <NUM> and the annealing calculation unit <NUM>. The random-number-generation-&-initial-value-setting unit <NUM> includes a random number generator <NUM>, an input select unit <NUM>, and an initial value storage unit <NUM>. The random number generator <NUM> includes an operation control unit <NUM>, a generation unit <NUM>, and a register <NUM>. The annealing calculation unit <NUM> includes an arithmetic unit <NUM> and a register <NUM>.

The random number generation instruct unit <NUM> of the operation instruct unit <NUM> causes the random number generator <NUM> to operate in an indicated operation mode that is either the normal operation mode or the continuation operation mode, based on the data indicative of an operation mode setting supplied from the operation mode storage unit <NUM>. The random number generation instruct unit <NUM> causes the random number generator to operate in the normal operation mode when the annealing process instruct unit <NUM> causes the annealing calculation unit <NUM> to perform an annealing process from the initial state. Specifically, under the control of the operation control unit <NUM>, the generation unit <NUM> performs initialization based on the seed value supplied from the seed storage unit <NUM>, followed by performing the process of generating a random number sequence. The random numbers generated by the generation unit <NUM> are successively stored in the register <NUM>.

The annealing initial value indicating unit <NUM> causes the input select unit <NUM> to select the initial parameters supplied from the initial value transmitting unit <NUM> in the case in which the operation mode storage unit <NUM> indicates the normal operation mode, i.e., in the case in which an annealing process is performed from the initial state. As a result, the input select unit <NUM> outputs the initial parameters from the initial value transmitting unit <NUM>, and these initial parameters are stored in the initial value storage unit <NUM>.

Based on the data indicative of the iteration count limit supplied from the iteration count limit storage unit <NUM>, the annealing process instruct unit <NUM> causes the annealing calculation unit <NUM> to perform an indicated number of iterations of an annealing process. Specifically, after the initial parameters from the initial value storage unit <NUM> are stored in the register <NUM>, the arithmetic unit <NUM> advances the iterations of the annealing process while controlling state transitions by use of random numbers supplied from the register <NUM> of the random number generator <NUM>. As the annealing process advances, the parameters stored in the register <NUM> keep being updated. When the annealing calculation unit <NUM> suspends the annealing process upon completing the execution of a predetermined number of iterations, the random number generation instruct unit <NUM> causes the random number generator <NUM> to stop operating in synchronization with the suspension of the annealing process. Upon the occurrence of suspension, the parameter values of the current state stored in the register <NUM> may be read out to the outside of the optimization apparatus.

When the annealing process instruct unit <NUM> causes the annealing calculation unit <NUM> to restart the annealing process after the suspension of the annealing process, the setting in the operation mode storage unit <NUM> may be the continuation operation mode. At the time of restarting the annealing process, the random number generation instruct unit <NUM> causes the random number generator <NUM> to operate in the continuation operation mode based on the data indicative of the continuation operation mode supplied from the operation mode storage unit <NUM>. Specifically, under the control of the operation control unit <NUM>, the generation unit <NUM> resumes the operation of generating a random number sequence from the current internal state without performing initialization. The random numbers generated by the generation unit <NUM> are successively stored in the register <NUM>.

The annealing initial value indicating unit <NUM> causes the input select unit <NUM> to select the parameters as existed in the suspended state supplied from the register <NUM> of the annealing calculation unit <NUM> in the case in which the operation mode storage unit <NUM> indicates the continuation operation mode, i.e., in the case in which the annealing process is restarted from the suspended state. As a result, the input select unit <NUM> outputs the parameters as existed in the suspended state supplied from the register <NUM>, and these parameters are stored in the initial value storage unit <NUM>.

Similarities exist between the case of restarting after the suspension and the case of starting from the initial state, such that the data indicative of the iteration count limit supplied from the iteration count limit storage unit <NUM> is used as a basis for the annealing process instruct unit <NUM> to cause the annealing calculation unit <NUM> to perform an indicated number of iterations of an annealing process. Specifically, after the parameters from the initial value storage unit <NUM> are stored in the register <NUM>, the arithmetic unit <NUM> advances the iterations of the annealing process while controlling state transitions by use of random numbers supplied from the register <NUM> of the random number generator <NUM>. As the annealing process advances, the parameters stored in the register <NUM> keep being updated.

<FIG> is a flowchart illustrating an example of the operation of the optimization apparatus illustrated in <FIG>.

In step S21, the user selects the normal operation mode, and gives instruction to the optimization apparatus to start an annealing process. In so doing, the user sets the initial parameters in the initial value transmitting unit <NUM>, and also sets the iteration count limit and the normal operation mode in the control data storage unit <NUM>.

In step S22, the initial parameters transmitted from the initial value transmitting unit <NUM> of the control unit <NUM> are stored in the initial value storage unit <NUM> via the input select unit <NUM> of the annealing unit <NUM>. In step S23, the random number generation instruct unit <NUM> of the control unit <NUM> instructs the random number generator <NUM> to perform initialization. In response, the random number generator <NUM> performs initialization.

In step S24, the annealing calculation unit <NUM> performs an annealing process. Specifically, the annealing process instruct unit <NUM> of the control unit <NUM> instructs the annealing calculation unit <NUM> to start an annealing process. In response to this instruction, the annealing calculation unit <NUM> receives the initial parameters from the initial value storage unit <NUM>, and then performs the annealing process while controlling state transitions based on a random number sequence supplied from the random number generator <NUM>.

In step S25, the annealing process instruct unit <NUM> or the annealing calculation unit <NUM> checks whether the state has been updated a number of times equal to the predetermined iteration count limit. The annealing calculation unit <NUM> performs the annealing process until the predetermined iteration count limit is reached. Upon reaching the predetermined iteration count limit, the procedure proceeds to step S26.

In step S26, the annealing calculation unit <NUM> stops the annealing process, and, in synchronization therewith, the random number generator <NUM> temporarily stops the random number generation process. This synchronization control may be achieved by direct communication between the annealing calculation unit <NUM> and the random number generator <NUM>, or may be achieved by a stop instruction sent to the random number generator <NUM> from the operation instruct unit <NUM> which monitors and controls the operation of the annealing calculation unit <NUM>. Alternatively, the operation control unit <NUM> of the random number generator <NUM> may have been notified of a predetermined iteration count limit by the random number generation instruct unit <NUM> in advance, and stops the random number generation process after generating a predetermined number of random numbers corresponding to the predetermined iteration count limit. How to achieve synchronization control is not limited to a particular method.

In step S27, the parameters indicative of the results of calculation is sent from the register <NUM> of the annealing calculation unit <NUM> to the outside of the optimization apparatus. Based on these results of calculation, in step S28, the user determines whether the result of the annealing process is satisfactory. In the case of the result of the annealing process being satisfactory, the procedure comes to an end. In the case of the result of the annealing process being not satisfactory, the procedure proceeds to step S29.

In step S29, the user sets either the normal operation mode or the continuation operation mode in the control data storage unit <NUM> of the control unit <NUM>. For example, the initial parameters may be modified to perform a next annealing process under different conditions than in this time's annealing process. In such a case, the normal operation mode is chosen to be set. When this time's annealing process is to be resumed from the suspended state without any change, the continuation operation mode is chosen to be set.

In step S30, the random number generation instruct unit <NUM> of the control unit <NUM> determines whether the operation mode setting is the continuation operation mode. In the case of the setting being not the continuation operation mode (i.e., in the case of the setting being the normal operation mode), the procedure returns to step S22, in which initial parameters are set again, followed by repeating the subsequent processes. In the case of the setting being the continuation operation mode, in step S31, the annealing process instruct unit <NUM> instructs the annealing calculation unit <NUM> to perform (i.e., resume) the annealing process, and the random number generation instruct unit <NUM> instructs the random number generator <NUM> to resume the random number generation (i.e., random number generation in the continuation operation mode). In response, the annealing process by the annealing calculation unit <NUM> and the random number generation by the random number generator <NUM> are resumed in synchronization with each other. Thereafter, the procedure proceeds to step S24, and the subsequent steps will be repeated.

Specifically, under the control of the operation control unit <NUM>, the generation unit <NUM> resumes the operation of generating a random number sequence from the current internal state without performing initialization. The random numbers generated by the generation unit <NUM> are successively stored in the register <NUM>. The parameters as existed in the suspended state have been stored in the initial value storage unit <NUM> from the register <NUM> via the input select unit <NUM>, so that the annealing calculation unit <NUM> stores the parameters from the initial value storage unit <NUM> in the register <NUM> as a first thing after restarting the operation. Thereafter, the arithmetic unit <NUM> advances the iterations of the annealing process while controlling state transitions by use of random numbers supplied from the register <NUM> of the random number generator <NUM>. As the annealing process advances, the parameters stored in the register <NUM> keep being updated.

<FIG> is a state transition diagram illustrating the transition of an operation state of the optimization apparatus illustrated in <FIG> in the normal operation mode. As the optimization apparatus is powered on in the power-off state ST-<NUM>, the operation state of the optimization apparatus makes a transition to an input receiving state ST-<NUM>. The input receiving state ST-<NUM> is the state in which the optimization apparatus receives inputs for settings given from an external source, such as the initial parameters (i.e., the spin values of a state, coupling factors, temperature, and the like), an iteration count limit, and an operation mode (i.e., the normal operation mode or the continuation operation mode). The input receiving state ST-<NUM> is also the state in which the optimization apparatus receives instructions input thereto such as an operation start instruction.

As the optimization apparatus receives an operation start instruction in the input receiving state ST-<NUM>, the operation state makes a transition to an initialization state ST-<NUM>. The initialization state ST-<NUM> is the state in which the random number generator <NUM> performs initialization in the optimization apparatus. This initialization stores a seed value in the flip-lops of the shift register in the case of a linear feedback shift register, and sets initial values in the respective addresses in the memory circuit in the case of a Mersenne twister. As a predetermined number of clock cycles pass to complete the initialization in the initialization state ST-<NUM>, the operation state of the optimization apparatus makes a transition to an annealing state ST-<NUM>.

The annealing state ST-<NUM> is the state in which the annealing calculation unit <NUM> of the optimization apparatus performs an annealing process, with the random number generator <NUM> generating a random number sequence for use in the annealing process. The state transitions illustrated in <FIG> correspond to the case of the normal operation mode, so that the annealing calculation unit <NUM> receives the initial parameters from the initial value storage unit <NUM>, and, then, performs the annealing process while controlling state transitions based on a random number sequence supplied from the random number generator <NUM>. As execution of a predetermined number of iterations is completed, the operation state of the optimization apparatus makes a transition to the input receiving state ST-<NUM>.

<FIG> is a state transition diagram illustrating the transition of an operation state of the optimization apparatus illustrated in <FIG> in the continuation operation mode. As the optimization apparatus receives an operation start instruction in the input receiving state ST-<NUM>, the operation state makes a transition directly to the annealing state ST-<NUM> in the case of the continuation operation mode. The state transitions illustrated in <FIG> correspond to the case of the continuation operation mode, so that the annealing calculation unit <NUM> receives the parameters as existed in the suspended state from the initial value storage unit <NUM>, and, then, performs the annealing process while controlling state transitions based on a random number sequence supplied from the random number generator <NUM>. As execution of a predetermined number of iterations is completed, the operation state of the optimization apparatus makes a transition to the input receiving state ST-<NUM>.

Claim 1:
An optimization apparatus comprising:
a pseudo random number generator hardware module configured to operate in synchronization with a clock signal, either in a first operation mode in which to generate a random number sequence after performing an initialization or in a second operation mode in which to generate a random number sequence without performing the initialization, the pseudo random number generator hardware module being initialized by an initialization signal;
an annealing calculation hardware module configured to perform an annealing process by use of random numbers generated by the pseudo random number generator, and to suspend the annealing process upon completing an execution of a predetermined number of iterations; and
an operation instruct hardware module configured to control the pseudo random number generator hardware module and the annealing calculation hardware module,
wherein the operation instruct hardware module is configured to cause the pseudo random number generator hardware module to start operating in the first operation mode by activating the initialization signal to initialize the pseudo random number generator hardware module and by supplying the clock signal to the pseudo random number generator hardware module after deactivating the initialization signal, and is configured to cause the annealing calculation hardware module to perform the annealing process while the pseudo random number generator hardware module generates a random number sequence used in the annealing process,
wherein the operation instruct hardware module is configured to stop the clock signal to cause the pseudo random number generator hardware module to stop operating when the annealing calculation hardware module suspends the annealing process, and
wherein the operation instruct hardware module is configured to cause the pseudo random number generator hardware module to restart operating in the second operation mode by supplying the clock signal to the pseudo random number generator hardware module without activating the initialization signal, and to cause the annealing calculation hardware module to restart the annealing process.