Reading list

[rachitnigam]

Tracking various relevant papers and articles.

[rachitnigam]

FPGA Programming for the masses:

• "Writing an application at a behavioral level and leaving its destiny in the hands of a synthesis tool is commonly considered a bad design practice."
• "Following PAR [...] Users can refer to the timing analysis report to determine which critical paths fail to meet the timing requirements and then fix them in the source code. Most of the synthesis errors mean the user must go back to the source code and repeat the whole process."
• (Altera OpenCL-to-FPGA framework's) A template-based design methodology is used where the application-independent communication and memory infrastructure is locked down as a static part of the system and only the application-dependent kernel part is synthesized. This hierarchical, partition-based approach reduces synthesis time.

[sampsyo]

Nice! Here are a couple more overviews in a similar vein:

• Best-Effort FPGA Programming: A Few Steps Can Go a Long Way, from Jason Cong et al. This paper has a handful of case studies showing how to manually apply a small set of hardware-focused optimizations to an ordinary (software) program using HLS directives to get pretty good performance.
• Parallel Programming for FPGAs, which is a whole book about using Vivado HLS to get high-performance designs.

[rachitnigam]

High level languages for FPGA programming:

• Chisel
• Spatial
• Kiwi
• Esterel
• IBM Liquid Metal (Lime): Retrospective

[rachitnigam]

Pragmas: Brief descriptions and issues that our type system can solve.

• dependence: "IMPORTANT!: Specifying a false dependency, when in fact the dependency is not false, can result in incorrect hardware. Be sure dependencies are correct (true or false) before specifying them."

[rachitnigam]

Formal semantics for HDLs:

• The semantic challenge of Verilog HDL
• SecVerilog
• Kami
• A Formal Executable Semantics of Verilog

[rachitnigam]

Types! Capabilities! Greek symbols!

• Calculus of Capabilities: Surprisingly easy read, with good explanations for the typing rules. Two major things to take away from this paper: (1) We need to implement regions and region inference for the "scope system" (where arrays can be consumed multiple times). The paper claims that this algorithm already exists, but I haven't looked into it. (2) If we want to have polymorphic in the arrays, the capability system will also need to be polymorphic. This makes the type system quite a bit more complex since the capabilities have complicated subtyping relationships that are easy to write in math but hard (?) to implement.

[rachitnigam]

http://halide-lang.org/: Halide is a programming language designed to make it easier to write high-performance image and array processing code on modern machines.

Halide has some interesting abstractions for fast array and image processing. Worth taking a look at it to see if we can learn some interesting abstractions for seashell.

[sampsyo]

On Halide:

• The original PLDI paper is a joy to read.
• Darkroom is a Halide-like language for hardware generation from an overlapping set of authors.
• Rigel is a sort of sequel to Darkroom.
• There's also an unpublished paper on "Halide-HLS", which generates Vivado HLS input code from a Halide program.

[sampsyo]

Bonsai is the closest related work I know of at the intersection of type systems and program synthesis. Its goal is to find bugs in the soundness of type systems by synthesizing programs that are well-typed but fail at run time.

[sa2257]

Vaguely relevant papers in OOPSLA and MICRO 18?

1. AnyDSL: A Partial Evaluation Framework for Programming High-Performance Libraries https://2018.splashcon.org/event/splash-2018-oopsla-anydsl-a-partial-evaluation-framework-for-programming-high-performance-libraries https://anydsl.github.io

2. Rethinking the Memory Hierarchy for Modern Languages https://www.youtube.com/watch?v=XDpttL5_JIQ http://people.csail.mit.edu/sanchez/papers/2018.hotpads.micro.pdf

3. TAPAS: Generating Parallel Accelerators from Parallel Programs https://www.youtube.com/watch?v=Z6p-hClfg8k

And our own

4. An Architectural Framework for Accelerating Dynamic Parallel Algorithms on Reconfigurable Hardware https://www.youtube.com/watch?v=SKMGP3VaPWY https://www.csl.cornell.edu/~tchen/files/parallelxl-micro18.pdf

[rachitnigam]

Best Effort FPGA programming

• A study to demonstrate that HLS-based FPGA can be easy? Haven't convinced myself of this yet, but might be an interesting user-study approach.

Generating Configurable Hardware from Parallel Patterns

• Compiling functional parallel patterns to hardware. Has several relevant citations to other imperative PLs that compile to hardware in section 2.

[rachitnigam]

https://hipacc-lang.org/.

Another Halide-like programming language for writing image processing kernels. The halide-HLS paper points out that HIPAcc generates C which it feeds to Vivado HLS to generate FPGA designs. Also, Halide-HLS itself seems to use this workflow.

[rachitnigam]

Lava: Circuit design in haskell: Seems to provide some interesting FP primitives to build circuit. From a cursory glance, the primitives and composition mechanisms seem more interesting and higher level than VHDL but not at the algorithmic design level (I might be wrong about that).

[sampsyo]

Just for even more breadth in funky/modern HDLs, PyRTL is another Python-embedded, operator-overloading-heavy example from Santa Barbara. The page also has a nice list of "Related Projects" (including PyMTL) at the bottom of the page.

[rachitnigam]

NESL programming language: http://www.cs.cmu.edu/~scandal/nesl.html

[sa2257]

Papers Nitish shared from his work with Intel HLS on T2S, a language like Halide for spatial architectures. https://arxiv.org/ftp/arxiv/papers/1711/1711.07606.pdf

[rachitnigam]

From Xilinx manual: "A common issue when designs are first synthesized is report files showing the latency and interval as a question mark “?” rather than as numerical values. If the design has loops with variable loop bounds Vivado HLS cannot determine the latency"

We should be careful when implementing #63.

[rachitnigam]

Matlab HDL: https://www.mathworks.com/products/hdl-coder/features.html#generating-hdl-code

[rachitnigam]

EASY: Efficient Arbiter SYnthesis from Multi-threaded Code

The authors created a new pass for the LegUp-LLVM tool chain that allows them to eliminate unnecessary arbiters from a hardware design. LegUp has a simple, conservative method to figure out how many arbiters a specific design and memory partition scheme needs. The paper uses the MSFT Boogie verifier to prove unique access to memories by different threads (which seem to be equivalent to unrolled loops). When the tool can prove unique access, it eliminates the corresponding arbiter connection from the design.

The technique is not precise, i.e., it cannot find the optimal arbitration scheme and relies on SMT to prove uniqueness which might take arbitrarily long.

UNVERIFIED: Our type system is probably more precise than what they have since we support a strict subset of iteration patterns.

[rachitnigam]

SOAP: Structural Optimization of ArithmeticExpressions for High-Level Synthesis: Haven't read yet. They claim:

For the first time, we bring rigorous approaches fromsoftware static analysis, specifically formal semantics and abstractinterpretation, to bear on source-to-source transformation for high-level synthesis.

[rachitnigam]

HardCaml: Jane Street's library for producing FPGA designs in OCaml.

[rachitnigam]

FPGAs for the Masses. Section 2 has a nice introduction the state of HLS tools. Note that this is different from a similarly titled paper above.

[rachitnigam]

Silica: Language from Stanford Pat Hanrahan's group. The basic idea is taking python co-routines and turning them into FSMs that execute up to each yield in the program control flow. Essentially, a yield acts like a cycle boundary and the compiler can schedule all the other co-routines to execute cooperatively every cycle.

[rachitnigam]

Reconfigure.io is building a Go based HLS-as-a-service tool. Their compiler, Rio, uses LLVM to do the usual HLS scheduling stuff. The subset of Go used focuses on using channels and go routines. Tool seems beta.

[rachitnigam]

Thesis on optimizations for HLS optimizations. Papers worth reading to understand semantics for loops in HLS. Haven't read them myself.

https://github.com/Junyi-Liu/benchmarks-HLS

[sa2257]

Some papers which try to avoid complexities of HLS

• https://doi.org/10.1109/FCCM.2018.00029 uses machine learning to predict actual results from HLS reports
• https://doi.org/10.1145/3268344 proposes a new framework to better map HLS to FPGA
• Best effort programming paper uses https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7446058 to claim HLS is hard. But it's not very convincing IMO.
• http://www.csl.cornell.edu/~zhiruz/pdfs/lamda-fccm2019.pdf talks about how hard DSE is

[sa2257]

Adding in Bluespec reference manual http://www.bluespec.com/forum/download.php?id=157

[rachitnigam]

This is now embedded in https://rachitnigam.com/files/pubs/dahlia.pdf