Parallelisation, probabilistic acceleration give 10kx speed boost

Article By : Vivek Nanda

Fujitsu Labs' prototype computing architecture uses conventional semiconductors to solve combinatorial optimisation problems 10,000 times faster.

« Previously: Tough decisions
 

By prototyping its architectural concept in FPGA, Fujitsu Laboratories has demonstrated that conventional semiconductors can be used to rapidly solve combinatorial optimisation problems. The company used a couple of tricks to achieve the 10kx performance boost:

1. Parallelisation at the basic optimisation circuit level
The architecture uses a basic optimisation circuit, based on digital circuitry, as a building block. Multiple building blocks are driven, in parallel, in a hierarchical structure (see Figure 2) such that it minimises the volume of data moved between basic optimisation circuits, making it is possible to implement them in parallel at high densities using conventional semiconductor technology.

Yet, thanks to a fully connected structure that allows signals to move freely within and between basic optimisation circuits, the architecture is able to handle a wide range of problems.

 

Figure 2: The architecture uses a basic optimisation circuit as a building block.
 

2. Acceleration technology within the basic optimisation circuit
The basic optimisation circuit uses techniques from probability theory to repeatedly search for paths from a given state to a more optimal state. This includes a technique that calculates scores for the respective evaluation results of multiple candidates at once, and in parallel, when there are multiple candidates for the next state, which increases the probability of finding the next state (see Figure 3, left).

It also includes a technique that, when a search process becomes stuck as it arrives at what is called a "local minimum," it detects this state and facilitates the transition to the next state by repeatedly adding a constant to score values that increases the probability of escaping from that state (see Figure 3, right). As a result, you can quickly expect an optimal answer.

 

Figure 3: Acceleration using basic optimisation circuits.
 

Fujitsu Laboratories' development roadmap includes having, by its fiscal 2018, prototype computational systems that can handle real-world problems of 100,000 bits to one million bits. The lab believes this will validate the path toward practical implementation.