logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-07062021-151745


Tipo di tesi
Tesi di laurea magistrale
Autore
GUGLIELMO, WILLIAM
URN
etd-07062021-151745
Titolo
Parallel State Space Search for FPGA OpenCL Applications
Dipartimento
INFORMATICA
Corso di studi
INFORMATICA
Relatori
relatore Prof. Danelutto, Marco
Parole chiave
  • FPGA
  • openCL
  • scheduler
  • space search
  • sudoku
Data inizio appello
23/07/2021
Consultabilità
Tesi non consultabile
Riassunto
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.
File