Shreedutt C. Hegde
Hardware and FPGA system design  

Challenges solved:

• Expensive cache flush time- due to ARM core generating 255-node tree from the main tree, and pushing it into the DRAM, for DMA-ing into the FPGA SRAM-solved by pre-processing the main tree, and storing it in a blocked fashion, to avoid on-the-fly tree generation and hence cache flush too.

• Interleave DMA start signals, and FPGA kernel start signals, as well as DMA and FPGA completion wait times, to ensure pipeline-like operation and least overall execution time.

Impact and significance:

• The FPGA kernel execution time for a leaf node search in an 8-level tree was 0.43 us, while ARM core took 0.6us for same search.

• Despite this fast kernel, the FPGA-assisted solution was ~4.6 times SLOWER than pure sequential search by ARM processor (70us vs 15 us), for 6 leaf node searches on the main tree.

       Why?

1. Memory Bound problem. There is hardly any computation, that can be parallelized, it is the fast access to data residing in main memory which is critical. A leaf node search in a 16 million node tree, would require 24 sequential comparisons-Nothing computationally intensive to be beaten

2. ARM runs at 600Mhz, FPGA at 250 Mhz. ARM also enjoys direct cached-access to the main memory (Disabling cache, resulted in ARM taking almost twice as much time)

3. DMA communication costs from DRAM to FPGA space hurt the FPGA based solution to the maximum (~68% of total execution time) along with the AXI-interconnect latencies incurred in ARM-to-FPGA control signaling (Why cry for this? It’s all in the microseconds range to beat the software, every microsecond of overhead hurts!)

Limiting factors for improving performance:

1. Currently the FPGA kernel made 2-stage (3 tree element) comparisons in parallel. Doing more stage comparisons in parallel, would make the kernel faster- But this was limited by the dual-ported SRAM of the FPGA, which could service only 2 tree data elements per clock cycle.

2. Put more kernels in the fabric, to run more searches in parallel- The 6 kernels are limited by 4 General Purpose Ports and 2 High Performance AXI Ports to interface with the ARM processor.

3. So this is a sequential problem, and speedup is limited by sequential bottleneck (Amdahl’s Law!). Solution- Increase the data set size(Gustafson’s Law!) .Problem? 512MB maximum DRAM in the Zedboard.

But amidst all this, FPGA heterogenous system are just not about speedup right? The critical evaluation parameter should have been speedup/Joule, which is where FPGAs prove beneficial with their very low static runtime power consumption. Accurate power consumption measurement for an embedded heterogenous board like Zedboard was tough, and so this parameter remained un-evaluated.