High-level synthesis (HLS) tools are able to parallelise regular tasks on FPGAs efficiently. However, some applications show a dynamic behaviour such that their execution paths depend directly or indirectly on the input data. These applications usually use irregular memory access patterns to retrieve data from memory or save the results to the output data structures. Implementing these algorithms in HLS is a challenge and usually requires task-specific approaches.

Most of the current HLS synthesis tools utilises compile-time code analysis to expose the concurrency in the code. Then the exposed concurrency is scheduled to be executed in parallel on FPGA hardware.

The ability and efficiency of performing these two tasks (i.e., static code analysis and scheduling) depend mainly on the given algorithm’s data access pattern. If the data access pattern is regular and deterministic, it is feasible to schedule the code blocks at compile time for maximum performance. However, finding an optimum point may need extensive computations.

If the data access pattern is not regular and cannot be predicted during the static scheduling process, then the efficiency of transforming code concurrency into hardware parallelism reduces. The irregular data access occurs when memory access is not known at compile-time, mainly because of its dependency on the data under process. In other words, the irregular applications show a dynamic behaviour that can only be determined at run-time. Examples of irregular algorithms are graph algorithms, data analytics, and sparse matrix computations.
Several research activities have been focusing on describing and synthesising regular and irregular algorithms in HLS efficiently.

Although synthesising regular algorithms in HLS is well matured and already used in several commercial tools, addressing irregular algorithms in HLS is still a big challenge. According to the research results, there are three potential ways to cope with rare algorithms in HLS.

1- Using dynamic schedulers
2- Using proper data structures
3- Modifying the algorithm