Semiconductor device and information processing system

Patent metadata

Field	Value
Publication number	US-2017185380-A1
Application number	US-201415324178-A
Country	US
Kind code	A1
Filing date	Jul 9, 2014
Priority date	Jul 9, 2014
Publication date	Jun 29, 2017
Grant date	—

Abstract

A spin unit provided with a memory cell that stores a value of one spin of an Ising model, a memory cell that stores an interaction coefficient from an adjacent spin which interacts with the corresponding spin, a memory cell that stores an external magnetic field coefficient of the one spin and circuits that determine the next state of the one spin on the basis of a product of a value of each adjacent spin and the corresponding interaction coefficient and the external magnetic field coefficient is configured, the semiconductor device is provided with a spin array where the plural spin units are arranged and connected on a two-dimensional plane on a semiconductor substrate, a random number generator and a bit regulator, the bit regulator operates output of the random number generator and supplies a random bit to all spin units in the spin array via one wire.

First claim

1 . A semiconductor device, comprising:
a spin array where a plurality of spin units respectively provided with a memory cell that stores a value of each spin of an Ising model, a memory cell that stores an interaction coefficient from an adjacent spin which interacts with the corresponding spin, a memory cell that stores an external magnetic field coefficient of the corresponding spin, and circuits that determine the next state of the corresponding spin are arranged and connected on a two-dimensional plane on a semiconductor substrate in a state in which topology of the Ising model is maintained; a random number generator that generates a plural-bit random number; a bit regulator that operates output of the random number generator and supplies random one bit having variable bit probability; and one wire that supplies output of the bit regulator to all spin units in the spin array.

2 . The semiconductor device according to claim 1 ,
wherein the bit regulator includes: a bit selection unit that extracts only the number m of bits specified by the number m of operated bits from an input n-bit random number according to the number m of the operated bits stored in a memory; an AND circuit that ANDs each bit in an m-bit value which is output of the bit selection unit and outputs a 1-bit value; an OR circuit that ORs each bit in the m-bit value which is the output of the bit selection unit and outputs a 1-bit value; and an AND/OR selection unit that selects the output of the AND circuit or the OR circuit according to an AND/OR selecting bit stored in the memory and outputs the selected output as output of the whole bit regulator.

3 . The semiconductor device according to claim 1 ,
wherein the wire passes all spin units in the spin array only once in a traversable path; a random bit is supplied to each spin unit via the wire; and each spin unit inverts a value of spin using a value of the random bit.

4 . The semiconductor device according to claim 1 ,
wherein all spin units in the spin array are divided in units of a plurality of blocks; the output of the bit regulator is distributed to wire branched for each of the blocks; and each of the blocks supplies a random bit to all spin units in each of the blocks via one independent wire.

5 . The semiconductor device according to claim 1 ,
wherein the output of the bit regulator is supplied into the spin array via one wire; the wire is branched in tree structure in the spin array and each branch wire at an end is connected to respective spin units; and a random bit is supplied to the spin unit via wiring having the tree structure.

6 . The semiconductor device according to claim 1 , further comprising:
a second random number generator; and a second bit regulator, wherein the second bit regulator operates output of the second random number generator and supplies a second random bit to all spin units in the spin array via another second wire that is different from the wire; and each spin unit inverts a value of spin using a result of AND operation of the random bit and the second random bit.

7 . The semiconductor device according to claim 1 , comprising:
a random number generator located outside the semiconductor device, a
terminal for inputting a random bit output from a bit regulator and one wire for supplying the input random bit to all spin units in the spin array in place of the random number generator and the bit regulator respectively provided in the semiconductor device,
wherein each of the spin units inverts a value of spin using a value of the random bit.

8 . An information processing system comprising:
a semiconductor device a CPU, a memory, and a HDD connected to a system bus, wherein a problem conversion program executed in the CPU generates an interaction coefficient and an external magnetic field coefficient of an Ising model that represents an object problem; and wherein the CPU of the semiconductor device is configured to
generate an initial spin array at random;
writes the initial spin array, the interaction coefficient and the external magnetic field coefficient to the spin unit to which each spin of the Ising model is allocated in the spin array in the semiconductor device;
set an initial value of bit probability in random bits output from the bit regulator and a number of times of interaction corresponding to the bit probability;
repeatedly execute a ground state search process of each of all spin units in the spin array by the set number of times of interaction;
perform update for lowering bit probability and resetting of the number of times of interaction when the set bit probability does not reach a final lower limit threshold and repeatedly executes the ground state search process of the spin unit; and
read a spin array of the spin unit that reaches a ground state so as to acquire solution of the object problem.
and
wherein the semiconductor device a spin array where a plurality of spin units respectively provided with a memory cell that stores a value of each spin of an Ising model, a memory cell that stores an interaction coefficient from an adjacent spin which interacts with the corresponding spin, a memory cell that stores an external magnetic field coefficient of the corresponding spin, and circuits that determine the next state of the corresponding spin are arranged and connected on a two-dimensional plane on a semiconductor substrate in a state in which topology of the Ising model is maintained;
a random number generator that generates a plural-bit random number;
a bit regulator that operates output of the random number generator and supplies random one bit having variable bit probability; and
one wire that supplies output of the bit regulator to all spin units in the spin array.

9 . An information processing system comprising: CPU, a memory, an HDD and a semiconductor device applicable as an accelerator are connected to a system bus,
wherein the semiconductor device comprises: a spin array where a plurality of spin units respectively provided with a memory cell that stores a value of each spin of an Ising model, a memory cell that stores an interaction coefficient from an adjacent spin which interacts with the corresponding spin, a memory cell that stores an external magnetic field coefficient of the corresponding spin, and circuits that determine the next state of the corresponding spin are arranged and connected on a two-dimensional plane on a semiconductor substrate in a state in which topology of the Ising model is maintained; a random number generator that generates a plural-bit random number; a bit regulator that operates output of the random number generator and supplies a random one bit having variable bit probability; one wire that supplies output of the bit regulator to all spin units in the spin array; and an I/O interface that reads/writes data from/to the memory cell of the spin unit arranged in the spin array; a problem conversion program executed in the CPU generates an interaction coefficient and an external magnetic field coefficient of the Ising model that represents an object problem; and a control program executed in the CPU of the semiconductor device: generates an initial spin array at random; writes the initial spin array, the interaction coefficient and the external magnetic field coefficient to the spin unit to which each spin of the Ising model is allocated in the spin array in the semiconductor device; sets an initial value of bit probability in random bits output from the bit regulator and a number of times of interaction corresponding to the bit probability; repeatedly executes a ground state search process of each of all spin units in the spin array by the set

Assignees

• Hitachi Ltd

Inventors

• Hayashi Masato
• Yamaoka Masanao
• Yoshimura Chihiro

Classifications

• G06N7/01 Primary

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06F17/18

  for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title

• G06F7/588 Primary

  Random number generators, i.e. based on natural stochastic processes · CPC title

• G11C11/16

  using elements in which the storage effect is based on magnetic spin effect · CPC title

• H03L7/26

  using energy levels of molecules, atoms, or subatomic particles as a frequency reference · CPC title