Array Partitioning

[Victorlzd]

Problems with ssdm

The ssdm functions work with 1D arrays but when applied to 2D
it doesn't work. By looking in the LLVM-IR we found that the
ssdm function is always called on a 1D array. I didn't found
a way to work around this problem

Meta programming

The solution for partitioning without using the ssdm functions
is to use template meta programmation to implement in c++ the
behaviour of a partitioned array.

We had two ideas to implement this :

• recursive template structure
• tuples using some boost::hana stuff

Problems with tuples

The try with tuples did not go far because there is an error
with current sycl implementation when using some functions like
std::make_tuple inside lambdas. This error make tuples unusable for
the partitioning problem for the moment.

Problems with recursive template structure

The first problem with recursive template structure is that if the
index is not known at compile time the subscript operator has a o(N)
complexity because all cases have to be tested and performance would
even worse than before. So to be effective all the loop using the array
have to be unrolled

Problems with loop unrolling

The implementation we found for loop unrolling use tuples so it suffers
the same problem with lambdas. With this implementation we can unroll a loop
but we cannot unroll a loop which is inside an unrolled one. By discussing
with Alexandre we learned that to be effective with partitioned array we
need to unroll the loop (for all implementations). So it is mandatory to
find a solution to this problem in order to use partitioned array.

How to know if partitioning works

We discussed this with Alexandre and the conclusion is that the only way
to know if the array is partitioned is to look at the resource use and
timing of the hardware result. This method is purely empirical, so finding
the good examples is essential. The problem is if the example is to simple
the compiling process will be able to perform too much optimizations.
For example the table below describes a case where when the loop is unrolled,
the compiler seems to do the partitioning by itself. This example don't
allow any conclusion about the array partitioning implementations. I tried
with a more complex example, a cache for the edge detection algorithm on FPGA.
But I didn't achieve to make it working due to the problems above.

classic for loop	FF	LUT	DSP	BRAM	URAM	Cycle
reference	3785	5766	36	10	0	4270
ssdm	5685	4198	20	2	0	470
struct inherit array	35663	8000	36	2	0	3270
meta_programing	1862	11021	4	4	0	5147

unrolled for loop	FF	LUT	DSP	BRAM	URAM	Cycle
reference	1605	2008	8	2	0	148
ssdm	compilation error
struct inherit array	compilation error
meta_programing	1605	2008	8	2	0	148