martinkiefer/scotch

Scotch: Generating FPGA-Accelerators for Sketching Algorithms

Scotch

Scotch is a framework for generating optimized FPGA-accelerators for sketching algorithms.

It provides three core features:

• ScotchDSL: A domain specific language + programming models to describe a variety of sketching algorithms
• Code Generators: ScotchDSL specifications are automatically translated into a VHDL architecture containing all necessary components to perform sketching.
• Auto-Tune: An automated tuning algorithms optimizes the size of the sketch summary with respect to provided constraints and resources on the FPGA

Scotch has a corresponding publication in PVLDB:

Martin Kiefer, Ilias Poulakis, Sebastian Breß, and Volker Markl. Scotch: Generating FPGA-Accelerators for Sketching at Line Rate. PVLDB, 14(3), 2021.

Requirements

• A recent Linux operating system. For the code generator in isolation, OSX will do either.
• Python 3.6+ is required. We used Python 3.6.
• The following Python modules are required (used version in brackets): antlr4-python3-runtime (4.7.2), numpy (1.170), pandas (0.25.0).
• The ANTLR4 parser generator is required to generate the ScotchDSL parser (4.7.2). A setup script is provided for your convenience that downloads the appropriate jar and generates the parser. See README in the ScotchDSL folder.
• An FPGA toolchain is required. Intel FPGAs with Quartus Prime are supported. We tested with Quartus Prime Pro 19.3 and Quartus Prime 19.1. Thus all *10 and *V product lines should be supported. Furthermore, we support support Xilinx /Vivado. We tested with Version 2020.1.
• CPU baselines require GCC and Boost. We used GCC 7 and Boost 1.53.
• GPU baselines require CUDA and Boost. We used CUDA 10.2 with GCC 6 and Boost 1.53.

Project Structure

ScotchDSL: Contains all code generator files and implementations of various algorithms in ScotchDSL.

Autotune: Contains all files regarding automated tuning.

Baselines: CPU and GPU baseline implementations.

Sketches: ScotchDSL implementations of sketching algorithms.

IO-Controllers: I/O controller examples.

Util: Miscallaneous little helpers. Contains scripts for scaling experiments.

Our reproducibility/availability wiki page can help to get you started.

scotch's Issues

Does the generated Sketch support reset?

Hi dear author.

First of all, thanks very much for your wonderful work! It is rare to see open-sourced hardware projects like this.

I am planing to use Scotch in my FPGA design which requires a CM-Sketch module. However, according to my knowledge the generated sketch does not have a reset logic, which is useful to reset all the counters to zero. Do I miss something?

What's more. May I ask how to readout the counters in the CM-Sketch array? In the tl.vhl I can only see this :

process(clk)
begin
if rising_edge(clk) then
sout1 <= parity(sketch_rd_data_out) xor sketch_rd_valid_out;
end if;
end process;

It seems that this is just a dummy logic to get some one-bit info from sketch array.

Any suggestions are welcome! Thank you again.