• space search
• FPGA
• scheduler
• sudoku
• openCL

We propose an OpenCL framework able to solve problems modelled as state-space search for FPGA devices.
Users willing to use our framework have to implement only the OpenCL kernels to manage the communication with the host application and a kernel function that, given a state of the exploration, produces all the states reachable from it.
We also allow the user to define a replication factor NW.
The framework is able to grant a linear speedup if the problem generates enough tasks to make the pipeline work at full capacity.
When working at full capacity, the framework analyzes NW new exploration states every clock cycle of the FPGA.

We studied how parallel computation can be achieved on FPGA, applying common methodologies of structured parallel programming.
In particular, we implement some solutions to obtain an all-to-all communication mechanism between different OpenCL compute units.
To develop the framework, we perform experiments on a Terasic’s HAN Pilot Platform, which mounts an Intel Arria 10 Soc FPGA.

As an application, we propose a pretty efficient brute force sudoku solver able to produce a new board every clock cycle and make the most from the framework.