CN118569363A - A spin-scale adaptive Ising annealing circuit - Google Patents

Abstract

The invention discloses a spin-scale self-adaptive Xin Tuihuo processing circuit, relates to an isooctyl model technology, and provides a scheme for solving the problems of low hardware resource utilization rate and the like in the prior art. The annealing task is uniformly distributed to each spin calculation node according to the self-adaptive calculation method, and the workload of the spin calculation nodes is balanced; processing the assigned individual spins in a serial or parallel mode; the adaptive computing method comprises two parts of spin distribution and a computing method determination; (E-R) spins are uniformly distributed to (E-R) spin calculation nodes, and the rest are uniformly distributed to other spin calculation nodes; if F > L, each spin calculation node will be independently processed in serial calculation mode The R spins are cooperatively processed by all spin calculation nodes in a parallel calculation mode; otherwise, each spin-calculation node will independently process all its assigned spins in serial calculation mode. The circuit has the advantages of high utilization rate of circuit resources and low cost.

Description

A spin-scale adaptive Ising annealing circuit

Technical Field

The invention relates to the technical field of Ising models, and in particular to a spin-scale adaptive Ising annealing processing circuit.

Background Art

Ising annealing processor has become an effective method for quickly solving combinatorial optimization problems. This processor uses the Ising model as a bridge between itself and the combinatorial optimization problem, and quickly finds the solution to the problem by simulating the annealing process of solid matter. The current annealing processor can effectively support a fixed, predefined number of spins, and use a fixed calculation method and a fixed hardware circuit to implement the Ising model annealing process. Generally, combinatorial optimization problems of different types and sizes require different spin numbers when mapped to the Ising model, and the real-time state flip spin number of different iterations in the Ising model annealing process is also different. However, when facing these situations, the current annealing processor has a very low utilization rate of its own hardware resources, wasting a lot of circuit resources. Therefore, it is necessary to develop an Ising annealing processing circuit that can adapt to the total spin number and the real-time flip spin number.

Summary of the invention

The present invention aims to provide a spin-scale adaptive Ising annealing processing circuit to solve the problems existing in the above-mentioned prior art.

The spin-scale adaptive Ising annealing processing circuit described in the present invention comprises:

An interface, used to complete information exchange between a user and the Ising annealing processing circuit;

The top-level controller is used to evenly distribute the annealing tasks to each spin computing node according to the adaptive computing method, so as to balance the workload of the spin computing nodes;

Off-chip memory for storing spin connection weights;

A storage controller is used to manage the refresh, read, and write operations of the off-chip memory and provide corresponding connection weights for each spin computing node;

A spin calculation node, used for processing each assigned spin in a serial or parallel mode according to the adaptive calculation method;

The coefficient channel is used to transmit the spin connection weights to the spin calculation nodes;

A readout network, used to read out the calculation results to the outside or other spin calculation nodes;

The write-back network is used to transmit the instruction stream generated by the top-level controller to the spin computing nodes;

The result channel is used to transfer the calculation result of the spin calculation node to the next level spin calculation node;

The adaptive calculation method includes two parts: spin allocation and calculation method determination;

Spin Allocation: (ER) spins are evenly distributed to (ER) spin computing nodes, and the remaining spins are evenly distributed to the remaining R spin computing nodes;

Calculation method determination: If F>L, each spin calculation node will be processed independently in serial calculation mode spins, and the remaining R spins will be processed collaboratively by all spin computing nodes in parallel computing mode; otherwise, each spin computing node will independently process all its assigned spins in serial computing mode;

Among them, N is the total number of spins, E is the number of spin calculation nodes with multiplier accumulators, F is the number of flipped spins in the previous iteration, L is the depth of the hierarchical tree network, and L<<E, R is the remainder of N divided by E, that is, R=N%E.

The spin-scale adaptive Ising annealing processing circuit described in the present invention has the advantages of high circuit resource utilization and lower cost.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a schematic diagram of the structure of the Ising annealing processing circuit described in the present invention.

FIG. 2 is a schematic diagram of the structure of the spin calculation node described in the present invention.

FIG. 3 is a schematic diagram of a mode of the Ising annealing processing circuit in the present invention under the serial calculation method.

FIG. 4 is a schematic diagram of a mode of the Ising annealing processing circuit in the present invention under a parallel computing method.

DETAILED DESCRIPTION

As shown in Figures 1 to 4, a spin-scale adaptive Ising annealing processing circuit based on the proposed adaptive computing method of the present invention includes multiple sub-circuits: an interface, a top-level controller, an off-chip memory, a storage controller, a spin computing node, a coefficient channel, a readout network, a write-back network and a result channel.

The adaptive computing method completes the Ising annealing process based on a hierarchical tree topology to balance hardware resources and actual computing needs. Specifically, it can be represented by several parameters: the total number of spins N, the number of spin computing nodes with multiplier accumulators E, the number of flipped spins in the previous iteration F, the depth L of the hierarchical tree network, and L E, the total number of input ports P of the first layer spin computing nodes, and the remainder R of N divided by E, that is, R=N%E. The method includes two key stages: spin allocation and calculation method determination. The former allocates N spins to E spin computing nodes, and the latter determines the best calculation method for Ising annealing based on the real-time values of the above variables.

Spin Allocation: (ER) spins are evenly distributed to (ER) spin computing nodes, that is, each spin computing node receives , the remaining spins are evenly distributed to the remaining R spin computing nodes, that is, each of the remaining spin computing nodes receives . This ensures that each spin computing node is assigned almost the same amount of spin.

Calculation method determination: If F>L, each spin calculation node will be processed independently in serial calculation mode spins, and the remaining R spins will be processed collaboratively by all spin computing nodes in parallel computing mode. Otherwise, each node will independently process all its assigned spins in serial computing mode.

The interface is used to complete the information exchange between the user and the circuit.

The top-level controller consists of a register file, an annealing unit, a data flow management unit, a state machine, and an instruction generator. It evenly distributes annealing tasks to 63 spin computing nodes based on an adaptive computing method, balancing the workload of the spin computing nodes and improving hardware resource utilization.

The off-chip memory stores the spin connection weights, and the spin-momentum coupling weights are stored in the on-chip momentum memory. Generally speaking, as the number of spins increases, the number of spin connection weights increases exponentially, while the number of momentum coupling weights increases linearly. During the annealing process, the number of required connection weights gradually decreases, while all momentum coupling weights are required for each iteration. The above hybrid storage can strike a balance between on-chip circuit cost and annealing speed.

The memory controller consists of control logic and 95 coefficient FIFO memories, manages the refresh, read, and write operations of the off-chip memory, and provides corresponding connection weights for 63 spin computing nodes.

The spin computing node is the computing power core of the circuit of the present invention. 63 spin computing nodes are interconnected in a tree network through a readout network, a write-back network and a result channel to form a highly parallel computing circuit. Each spin computing node contains 1024 fully connected spins, and the circuit of the present invention supports a total of 64512 spins. The spin computing node is controlled by instructions to calculate the spin local field and update the spin state. The spin computing node adopts a full pipeline circuit design and consists of an instruction decoder, a data decoder, a source selection unit, a local field unit and a state update unit. The current spin computing node receives the instruction stream generated by the top-level controller through the write-back network, and the instruction decoder and the data decoder extract real-time commands and operation data from the instruction stream respectively. Multiple two-input comparators are deployed in the instruction decoder and run in parallel to quickly compare the received instructions with predefined instructions, thereby reducing the time consumption of the annealing process. The source selection unit consists of a local field memory, a partial sum memory, a momentum memory, a parameter register stack, a linear feedback shift register LFSR, two multiplexers and a digital multiplier. The local field memory stores the local field values of the 1024 spins of the current spin calculation node. , external field With spin state The partial sum memory stores the local field partial sum value, and the momentum memory stores the momentum coupling weight The parameter register stack stores the discard rate values of the current and previous iterations. and momentum scaling factor , real-time annealing temperature , the number of spins assigned to the current spin calculation node, and other annealing parameters. The linear feedback shift register is responsible for generating pseudo-random numbers r for spin state updates and real-time momentum coupling weight calculations. When calculating real-time coupling weights When the momentum scaling factor will be loaded into the upper input port of the multiplier, discarding the rate and momentum coupling weight Loaded to the multiplexer connected to the input port of the multiplier. If the random number is exceeded, the momentum coupling weight will be transferred to the lower input port of the multiplier; otherwise, 0 will be loaded into the lower input port of the multiplier. Finally, the digital multiplier produces , and forwarded to the local field unit. When calculating the self-selected local field part and When , and sends the result to the state update unit for calculating the next state of the spin. These operations share the same digital multiplier, which helps reduce circuit costs. The local field unit first performs a multiplication operation, where the multiplier is the spin state -1 or 1, and then adds the data from the source selection unit and the external port. It is mainly composed of two multiplexers, an adder, two lookup tables LUT, two shift registers SR and several external ports. The external ports are respectively connected to the coefficient channel, the write-back network and the read-out network. The LUT stores the selection signals under different flip spin numbers for parallel computing mode, and the SR stores the flip spin state required for the current spin computing node. The local field unit dynamically selects the operand of the adder according to the received command in the serial computing mode, and dynamically selects the operand of the adder according to the LUT in the parallel computing mode. The state update unit calculates the next state of the spin based on the data from the local field unit and compares it with the previous state. If the two states are opposite, the new state and the corresponding index are sent to the top-level controller, and the number of such opposite state combinations is recorded by a counter.

The coefficient channel is responsible for transmitting the spin connection weight to the spin calculation node, and the spin connection weight is read from the off-chip memory by the coefficient FIFO memory. In addition, there are multiple data types in the Ising annealing process, such as annealing parameters, spin states, local field partial sums, flip spin indexes, etc. These data must be exchanged between users, top-level controllers and other subcircuits to achieve a complete Ising annealing process. Their transmission addresses, data formats, data volumes, and communication modes are very different. The read-out network and the write-back network realize the transmission of multiple data through opposite communication directions, cross switches, routing tables, and hybrid communication modes, reducing circuit costs. The calculation results of the spin calculation node are transmitted to the next-level spin calculation node through the result channel for parallel accumulation of multiple local field partial sums or counting the number of flip spins. In general, all data are transmitted in a step-by-step manner on multiple channels and networks of the circuit of the present invention, completely avoiding the global bus, simplifying the complexity of the entire system, and improving the circuit operation frequency. Compared with the prior art, the present invention has at least the following technical advantages:

(1) High circuit resource utilization: In terms of computing methods, the adaptive computing method evenly distributes spins to all spin computing nodes and dynamically determines the optimal computing method based on the number of spins required by different combinatorial optimization problems and the number of real-time flipped spins during the annealing process. In terms of circuits, each spin computing node dynamically selects operands based on the real-time changing number of spins. Multiple spin computing nodes can jointly complete the update of the next state of the spin, greatly improving the circuit resource utilization.

(2) The circuit supports large-scale spin processing, contains 63 spin processing nodes, and can process a maximum of 64,512 spins.

(3) Low circuit cost: A large number of spin connection weights are stored in cheap off-chip DDR memory, and only a small amount of momentum coupling weights and intermediate data are stored on-chip, which greatly reduces the on-chip cost; state updates and real-time shared momentum coupling weight calculations share the same digital multiplier; multiple types of data communications are only completed by read-out networks and write-back networks, reducing communication circuit costs.

For those skilled in the art, various other corresponding changes and deformations can be made according to the technical solutions and concepts described above, and all of these changes and deformations should fall within the protection scope of the claims of the present invention.

Claims (5)

1. A spin-scale adaptive Ising annealing processing circuit, characterized in that it includes: An interface, used to complete information exchange between a user and the Ising annealing processing circuit; The top-level controller is used to evenly distribute the annealing tasks to each spin computing node according to the adaptive computing method, so as to balance the workload of the spin computing nodes; Off-chip memory for storing spin connection weights; A storage controller is used to manage the refresh, read, and write operations of the off-chip memory and provide corresponding connection weights for each spin computing node; A spin calculation node, used for processing each assigned spin in a serial or parallel mode according to the adaptive calculation method; The coefficient channel is used to transmit the spin connection weights to the spin calculation nodes; A readout network, used to read out the calculation results to the outside or other spin calculation nodes; The write-back network is used to transmit the instruction stream generated by the top-level controller to the spin computing nodes; The result channel is used to transfer the calculation result of the spin calculation node to the next level spin calculation node; The adaptive calculation method includes two parts: spin allocation and calculation method determination; Spin Allocation: (ER) spins are evenly distributed to (ER) spin computing nodes, and the remaining spins are evenly distributed to the remaining R spin computing nodes; Calculation method determination: If F > L, each spin calculation node will be processed independently in serial calculation mode spins, and the remaining R spins will be processed collaboratively by all spin computing nodes in parallel computing mode; otherwise, each spin computing node will independently process all its assigned spins in serial computing mode; Among them, N is the total number of spins, E is the number of spin calculation nodes with multiplier accumulators, F is the number of flipped spins in the previous iteration, L is the depth of the hierarchical tree network, and L<<E, R is the remainder of N divided by E, that is, R=N%E. 2. The spin-scale adaptive Ising annealing processing circuit according to claim 1, characterized in that the top-level controller consists of a register file, an annealing unit, a data flow management unit, a state machine and an instruction generator. 3. According to claim 2, a spin-scale adaptive Ising annealing processing circuit is characterized in that E spin computing nodes are interconnected in a tree network through a readout network, a write-back network and a result channel; each spin computing node contains 1024 fully connected spins; the spin computing node is controlled by instructions to calculate the spin local field and update the spin state; the spin computing node adopts a full-pipeline circuit design, consisting of an instruction decoder, a data decoder, a source selection unit, a local field unit and a state update unit; the current spin computing node receives the instruction stream generated by the top-level controller through the write-back network, and the instruction decoder and the data decoder extract real-time commands and operation data from the instruction stream respectively; the instruction decoder compares the received instructions with the predefined instructions in parallel. 4. According to claim 3, a spin-scale adaptive Ising annealing processing circuit is characterized in that the source selection unit is composed of a local field memory, a partial sum memory, a momentum memory, a parameter register file, a linear feedback shift register, two multiplexers and a digital multiplier; the local field memory stores the local field values of each spin of the current spin calculation node , external field With spin state ; The partial sum memory stores the local field partial sum value, and the momentum memory stores the momentum coupling weight ; The parameter register stack stores the discard rate values of the current and previous iterations , momentum scaling factor , real-time annealing temperature , the number of spins assigned to the current spin calculation node; the linear feedback shift register is responsible for generating pseudo-random numbers r for spin state updates and real-time momentum coupling weight calculations; When calculating the real-time coupling weight When the momentum scaling factor will be loaded into the upper input port of the multiplier, discarding the rate and momentum coupling weight Loaded to the multiplexer connected to the input port of the multiplier; if the discard rate If the random number r is exceeded, the momentum coupling weight will be transferred to the lower input port of the multiplier; otherwise, 0 will be loaded into the lower input port of the multiplier; finally, the digital multiplier generates , and forwarded to the local field unit; When calculating the self-selected local field part and When the multiplier calculates , and sends the result to the state update unit to calculate the next state of the spin. 5. The spin-scale adaptive Ising annealing processing circuit according to claim 4, characterized in that the local field unit is composed of two multiplexers, an adder, two lookup tables LUT, two shift registers SR and several external ports; First, a multiplication operation is performed, where the multiplier is the spin state, and the spin state takes the value of -1 or 1; The data from the source selection unit and the external port are added, and the external port is respectively connected to the coefficient channel, the write-back network and the read-out network; the lookup table LUT stores the selection signals under different flip spin numbers for parallel computing mode, and the shift register SR stores the flip spin state required by the current spin computing node; the local field unit dynamically selects the operand of the adder according to the received command in the serial computing mode, and dynamically selects the operand of the adder according to the lookup table LUT in the parallel computing mode; the state update unit calculates the next state of the spin according to the data from the local field unit, and compares it with the previous state A comparison is made; if the two states are opposite, the new state and the corresponding index are sent to the top-level controller, and the number of opposite state combinations is recorded by a counter.