# Programming parallelism on FPGAs with Eclat

Loïc Sylvestre, Jocelyn Sérot, Emmanuel Chailloux

► To cite this version:

Loïc Sylvestre, Jocelyn Sérot, Emmanuel Chailloux. Programming parallelism on FPGAs with Eclat. 17th International Symposia on High-Level Parallel Programming and Applications (HLPP 2024), Massimo Torquati; Marco Danelutto, Jul 2024, Pisa, Italy. pp. 69-88. hal-04772531

HAL Id: hal-04772531

https://hal.science/hal-04772531v1

Submitted on 8 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Programming parallelism on FPGAs with ECLAT

Loïc Sylvestre · Jocelyn Sérot ·
Emmanuel Chailloux*

**Abstract** ECLAT is a general purpose OCAML-like programming language with synchronous semantics for designing reactive hardware applications on FPGAs. It is compiled down to hardware descriptions to realize computations as intrinsically parallel circuits able to interact with the physical world.

This paper presents a formalization of ECLAT with shared memory and mutability, handling concurrent memory accesses while preserving determinacy. The language is precise enough to express efficient circuits with fine control over throughput, parallelism and time-space trade-off. It also enables abstraction by letting the programmer implement, reuse and compose algorithmic skeletons such as *map* and *pipe*. The synchronous approach makes it possible to estimate the execution time of parallel programs by simple reasoning on source code for quick prototyping and optimization.

**Keywords** Language design and implementation, FPGAs, Performance prediction, Algorithmic skeletons, Synchronous programming

## 1 Introduction

Field-Programmable Gate Arrays (FPGAs) are digital circuits interconnecting generic logic cells, memory blocks and I/O blocks; all of these elements are configurable by logic synthesis to implement custom circuits. This architecture offers an interesting trade-off between Application-Specific Integrated Circuits (ASICs) and general-purpose processors. It exposes fine-grained parallelism

Loïc Sylvestre and Emmanuel Chailloux
Sorbonne Université, CNRS, LIP6, F-75005 Paris, France
E-mail: Loic.Sylvestre@lip6.fr, Emmanuel.Chailloux@lip6.fr

Jocelyn Sérot
Institut Pascal, UMR 6602 UCA/CNRS/SIGMA
E-mail: Jocelyn.Serot@uca.fr

<footnote>* This Work is partially supported by the Center for Research and Innovation on Free Software (IRILL).</footnote>
with very low latency in I/Os processing. This constitutes a valuable target for both embedded system design [5] and heterogenous computing.

FPGAs are classically programmed as synchronous circuits at the so-called Register Transfer Level (RTL) in Hardware Description Languages (HDLs) such as VHDL or VERILOG. The main advantage of RTL is predictability because any architectural detail (such as throughput, latency and parallelism) must be encoded in terms of register updates at each clock tick of a global clock.

A variety of *high-level synthesis* tools have been proposed to generate hardware descriptions from software-like (C/OpenCL) code [12]. However, one of the side effects of such automation is that many architectural details are hidden from the programmer [7]. This is a source of unpredictability, *e.g.*, for timing.

To trade this issue, we are currently developing the *high-level* programming language ECLAT (*declarative language*), which is tailored for the design of real-time hardware applications on FPGAs [16].

ECLAT is an OCAML-like language compiled to VHDL and whose formal semantics is based on the synchronous model of computation [4]. It reflects, at the language level, the tick of the physical clock driving the target FPGA: program execution is discretized as a sequence of computation steps called *clock cycles* (or *instants*). The duration of each cycle is fixed by the FPGA clock.

ECLAT programs can mix several programming styles, such as high-level hardware description, general purpose computation and interaction with the physical world. This paper focuses on general-purpose parallel computing on FPGAs with ECLAT. The contributions are:

* the design of ECLAT, including an operational semantics to model shared memory, mutability and concurrency in a deterministic manner;

* the implementation<fnref n="1" /> of these new features in the ECLAT compiler<fnref n="2" />;

* the exploration of space-time trade-off in ECLAT, by mixing fine-grained parallelism and shared memory, to obtain important gains of speed on an FPGA with regard to sequential implementations running on a CPU;

* the efficient implementation of algorithmic skeletons using ECLAT with performance prediction and optimization by simple reasoning on source code.

Section 2 formalizes the ECLAT language core and mentions practical extensions that are used in the rest of the paper. Section 3 presents the ECLAT support for array allocation in shared memory and mutability; the mix of synchrony and shared memory provides, for free, determinacy and fairness for concurrent memory accesses, which constitutes a basis for performance prediction. Follows an evaluation, in Section 4, which shows how to exploit fine-grained parallelism with ECLAT, while using shared memory, in order to achieve high performance on quite large inputs. Section 5 considers the parallel implementation of algorithmic skeletons (as higher-order functions operating on ECLAT arrays); it focusses on composability and performance prediction through a

<footnote n="1">¹ The artefact presented in this paper, including the source code for the benchmarks, is available online: https://github.com/lsylvestre/HLPP24</footnote>

<footnote n="2">² We mainly target Intel FPGAs, but also provide experimental backends for Xilinx FPGAs and the open-source synthesis tool-chain YOSYS.</footnote>
simple example, paving the way for understanding and optimizing more com-
plex skeleton-based ECLAT applications. Section 6 discusses related work, and
section 7 highlights future research perspectives.

## 2 The ECLAT language

This section presents<fnref n="3" /> ECLAT, a declarative programming language compiled to synchronous circuits for reconfiguring FPGAs. The FPGA target is crucial, here, because it exposes a physical clock that the language exploits to finely control timing, throughput and parallelism in the applications.

ECLAT is based on a core language named $\lambda_{cbv}$, which is a typed left-
to-right call-by-value $\lambda$-calculus with pairs and like immutable vectors, para-
metric polymorphism and a limited form of higher-orderness to be efficiently
compiled to a synchronous circuit.

ECLAT also features tail-recursion and coarse-grained parallelism, both re-
lying on the concept of *pause* [9]. A pause is a global synchronization barrier
used in ESTEREL-like synchronous languages to model time *logically* as a dis-
crete sequence of clock cycles. In ECLAT, each recursive function call performs
an implicit pause which delays the execution of the function body to the next
clock cycle. Following the path initiated by ESTEREL [6], the hardware imple-
mentation of ECLAT directly connects logical time to the clock of the FPGA.

2.1 Syntax and dynamic semantics of $\lambda_{cbv}$

The syntax of $\lambda_{cbv}$ is shown in the upper part of Fig. 1. We let $f, g, x, y$ and $z$ range over an infinite set of variables. Each program $\pi$ is an expression $e$, which computes an immediate value $\hat{v}$ of basic type $\hat{\tau}$, i.e., a constant or a pair of immediate values. Among constants, immutable vectors (*resp.* integers) have a size $s$ in number of elements (*resp.* in number of bits). Integers are signed. Values are constants, pairs, and functions. Local definition (*let*) and function abstraction (*fun*) deeply destructurate pairs of values matching a pattern $p$. Conditional (*if*) evaluates only one branch according to a condition.

Following a Hindley-Milner type discipline, a type scheme $\sigma$ associated
with a let-binding is a type where some variables ($\alpha$ for types, $\hat{\alpha}$ for basic
types and $\eta$ for sizes) are quantified to be instantiated (by types, basic types or
sizes respectively) when using this binding. All functions (including operators)
are unary$^4$; this is ensured at type level by enforcing functions to return an
immediate value $\hat{v}$ of basic type $\hat{\tau}$. Operators over vectors are:

* `vect_create<n>` : $\forall \hat{\alpha} \cdot \hat{\alpha} \rightarrow \hat{\alpha} \ vect<n>$ for creation with an initial value, e.g., `vect_create<n>(c)` evaluates to the array $\{c, \dots, c\}$ of size $n$,

* `vect_size`: $\forall \eta \cdot \forall \hat{\alpha} \cdot \hat{\alpha} \ vect<\eta> \rightarrow \text{int}$ for access to the size of the vector,

<footnote n="3">³ This presentation focuses on parallel programming in ECLAT and therefore omits two ECLAT constructs (named *register* and *exec*) [16], which are used for interacting with the physical I/Os in a (LUSTRE/SCADE like) synchronous dataflow programming style.</footnote>

<footnote n="4">⁴ For instance, the operator (+) has type $\forall \eta . (\mathit{int}<\eta> \times \mathit{int}<\eta>) \rightarrow \mathit{int}<\eta>.$</footnote>
* `vect_nth`: $\forall \eta \cdot \forall \hat{\alpha} \cdot (\hat{\alpha} \text{ vect<}\eta\>) \times \text{int} \rightarrow \hat{\alpha}$ for access to the element at the given computed index modulo the size,

* `vect_copy_with`: $\forall \eta \cdot \forall \hat{\alpha} \cdot (\hat{\alpha} \text{ vect<}\eta\>) \times \text{int} \times \hat{\alpha} \rightarrow \hat{\alpha} \text{ vect<}\eta\>$ for copy with update of the element at the given computed index,

* `vect_mapi`: $\forall \eta \cdot \forall \hat{\alpha} \cdot \forall \beta \cdot (((\text{int} \times \hat{\alpha}) \rightarrow \beta) \times \hat{\alpha} \text{ vect<}\eta\>) \rightarrow \beta \text{ vect<}\eta\>$ transforming a vector by mapping a function on indexes and elements.

In concret syntax, programs can have global declarations "let $x_1 = e_1$; ... let $x_n = e_n$;". Expressions can be over-parenthesized, e.g., $(f(g(x)))$. Tuples are provided as generalization of pairs. Size annotations for integer literals can be omitted (i.e., expression $n$ stands for the constant ($n:\text{int}<s$) with $s$ a fresh size variable). We let type `int` be an alias for `int<32>` and we use infix notation for binary operators as well as standard OCaml-like notations, e.g., let $f(p:\tau):\tau' = e$; stands for let $f = ((\text{fun } p \rightarrow e):\tau \rightarrow \tau')$;.

<figure><img src="image_2.png" /><figcaption>Fig. 1 Syntax and reduction semantics of $\lambda_{cbv}$</figcaption></figure>

The lower part of Fig. 1 defines the operational semantics of $\lambda_{cbv}$ as a reduction semantics in the style of Felleisen [8]. The reduction relation $e/\mu \rightarrow e'/\mu'$ rewrites configurations of the form $e/\mu$, where an expression $e$ is paired with a memory $\mu$. Memory is kept abstract in this section (it will be defined in section 3 when adding mutable arrays in shared memory).

An evaluation context $F$ is an expression with a hole $\square$. $F[e]$ is the expression obtained by substituting the hole $\square$ by expression $e$ in context $F$. The context $(v, \square)$ specifies the evaluation order: the right component of a pair cannot be reduced until the left component is a value. Rule `CONTEXT` reduces
the expression *e* in the hole of any context *F*[*e*] and propagates memory modifications (if any). Other rules specify, in a deterministic way, the behavior of each language feature. For example, reducing a let-binding or a function application performs a substitution without capture *e*[*p* ↦ *v*] of pattern *p* by value *v* in expression *e* (rules LET and FUN-APP). Operator application is defined by semantic function ϑ (rule OP-APP), e.g., ϑ(not, true, μ) = false/μ.

An important property of $\lambda_{cbv}$ is termination: for any well-typed configuration $e/\mu$, it exists a finite sequence of zero or more reductions $e/\mu \to^* e_n/\mu_n$ such that $e_n$ is stuck or a value.

Any $\lambda_{cbv}$ expression represents a combinational circuit computing outputs instantaneously. Operators are predefined logic gates. Constants are bit vectors (e.g., booleans are 1-bit vectors "0" and "1"). Each pair $(\hat{v}_1, \hat{v}_2)$ is a bit-vector concatenating the two projections $\hat{v}_1$ and $\hat{v}_2$. The *let* construct sequentially connects two sub-circuits. Each function abstraction $fun \to e$ is a circuit with one input *p* and one output that is the return value of the function. The input (*resp.* the output) is composed of several wires: one for each bit of the argument value (*resp.* the result). Function application is circuit instantiation, *i.e.*, inlining, which eliminates parametric polymorphism and higher-orderness.

Fig. 2 gives an example of circuit description in $\lambda_{cbv}$. This is a classical 1-bit full adder sequentially connecting two instances of a half adder.

<figure><img src="image_3.png" /><figcaption>Fig. 2 1-bit full-adder description in $\lambda_{cbv}$ and the corresponding circuit</figcaption></figure>

## 2.2 A synchronous general purpose language

The $\lambda_{cbv}$ language has limited expressiveness. It cannot describe, in particular, *sequential* circuits, i.e., circuits having an internal state. Such circuits are commonly described by hardware designers using Moore or Mealy *Finite State Machines* encoded using low-level patterns at the register transfer level. Following a different path, ECLAT extends $\lambda_{cbv}$ in a way that allows compute-oriented sequential circuits to be directly expressed as parallel algorithms, while keeping control over the low-level timing of these circuits.

The upper part of Fig. 3 defines the syntax of ECLAT as an extension of that of $\lambda_{cbv}$. It features two general purpose programming constructs, namely tail-recursion<fnref n="5" /> (*fix*) and parallel pair ($e_1 \parallel e_2$), both for which evaluation may span

<footnote n="5">⁵ A recursive function *fix* *f* (*fun* *p* → *e*) is a function *f* in which *f* is bound to its own definition *fun* *p* → *e* (*i.e.*, *f* can occur in *e*). In source programs, we use the classical derivated construct *let* *rec* *f* *p* = *e* *in* *e*′ defined as *let* *f* = *fix* *f* (*fun* *p* → *e*) *in* *e*′ (see Fig. 4).</footnote>
several cycles of a synchronizing clock. This notion of *clock* is incorporated in the language through the concept of *paused* expressions, which occur during evaluation (and never appear in source programs).

The lower part of Fig. 3 defines the operational semantics of ECLAT by an evaluation relation $e/\mu \Downarrow_n v/\mu'$ meaning: "the configuration $e/\mu$ evaluates to $v/\mu'$ in exactly *n* clock cycles (with $n \ge 0)$". This big-step relation $\Downarrow_n$ is defined by two rules, **EVAL-VAL** and **EVAL-PAUSE**, which instantaneously apply a sequence of zero or more reductions $\rightarrow^*$: if the redex is a value, evaluation terminates; if it is a *pause* of the form **pause** $e'$, then the execution time is increased by 1 and the reduction of $e'$ continues at the next cycle (in this case, we say that the evaluation is *non-instantaneous*).

Applying a recursive function $f$ binds the argument to the formal parameter of $f$, unfolds the fixpoint and places a *pause* behind the function body (rule FIX-APP). Reducing a parallel pair ($e_1 \parallel e_2$) is reducing $e_1$ (by applying rule CONTEXT in the context ($\square \parallel e$) until reaching either a paused expression or a value), then reducing $e_2$ in the same clock cycle (by applying rule CONTEXT in contexts ($v \parallel \square$) or (**pause** $e' \parallel \square$)). Pauses are moved up by applying rule PAUSE, except for two special cases aiming to synchronize parallel pairs (rules PAUSE-PAR1 and PAUSE-PAR2). Once both $e_1$ and $e_2$ have been reduced to values, a pair is instantaneously created (rule PAR).

<figure><img src="image_4.png" /><figcaption>**Fig. 3** Syntax and reduction semantics of ECLAT as an extension of $\lambda_{cbv}$ (Fig. 1)</figcaption></figure>

Let $\phi_{add}$ be: **fix** **add** (**fun** (a,b) -> **if** a = 0 **then** b **else** **add**(a-1,b+1)). Evaluating $\phi_{add}(2,2)/\mu$ for a given memory $\mu$ behaves as follows:

at cycle 0: $\phi_{add}(2,2)/\mu \rightarrow^* \text{**pause** } e_0/\mu$ where $e_0 = (\text{if } 2 = 0 \text{ then } 2 \text{ else } \phi_{add}(2-1,2+1))$, and then the pause is removed (by **EVAL-PAUSE**);

at cycle 1: $e_0/\mu \rightarrow^* \text{**pause** } e_1/\mu$ where $e_1 = (\text{if } 1 = 0 \text{ then } 3 \text{ else } \phi_{add}(1-1, 3+1))$, and then the pause is removed (by **EVAL-PAUSE**);

at cycle 2: $e_1/\mu \rightarrow^* 4/\mu$; therefore $\phi_{add}(2,2)$ evaluates to 4 in 2 cycles.
Fig. 4 illustrates how behaves ($e_1 \parallel e_2$). At lines 1-5 is defined a function `collatz` computing the stopping time of the *Collatz* sequence (also referred to as *Syracuse*) starting from an integer *n*. It declares a local tail-recursive function *f* performing one call per cycle. At line 6, function `collatz` is called twice in parallel with arguments 4 and 8. It evaluates as follows:

at cycle 0: `collatz(4)` reduces to `f(4,0)` and then `collatz(8)` to `f(8,0)`;

at cycle 1: `f(4,0)` reduces to `f(2,1)` and then `f(8,0)` reduces to `f(4,1)`;

at cycle 2: `f(2,1)` reduces to `f(1,2)` and then `f(4,1)` reduces to `f(2,2)`;

at cycle 3: `f(1,2)` reduces to 2 and then `f(2,2)` reduces to `f(1,3)`;

at cycle 4: `f(1,3)` reduces to 3 and then the program returns 2 + 3.

```
1   let collatz n =
2     let rec f (n,t) =
3       if n = 1 then t else
4         if n mod 2 = 0 then f(n/2,t+1) else f(3*n+1,t+1)
5     in f(n,0) in
6   let (x,y) = (collatz(4) || collatz(8)) in x + y
```

<caption>Fig. 4 A parallel computation expressed in ECLAT</caption>

Note that in $(e_1 \parallel e_2)$, $e_1$ and $e_2$ are reduced sequentially (from left to right) within the same clock cycle. This provides a deterministic *parallel evaluation* of $e_1$ to a value $v_1$ and $e_2$ to $v_2$, building the pair $(v_1, v_2)$. If expressions $e_1$ and $e_2$ are instantaneous, then expressions $(e_1, e_2)$ and $(e_1 \parallel e_2)$ are equivalent.

## 2.3 Compilation

Due to space limitation, the compilation process turning ECLAT programs into circuits cannot be presented in detail in this paper. But having a simplified view of the compiler ease to estimate the size of the resulting hardware. The basic principles of the compilation scheme can be summarized as follows:

1. lexical environments are made explicit by additional function parameters and then functions are globalized (by λ-lifting);

2. higher-order functions (*resp.* polymorphic functions) are specialized (*resp.* monomorphized) and therefore duplicated.

3. non-recursive functions are systematically inlined,

4. tail-recursive function calls are shared<fnref n="6" /> (i.e., not duplicated) except for parallel calls (e.g., Fig. 4, line 6), which are duplicated.

5. compiling construct $(e_1 \parallel e_2)$ leads to two automata for $e_1$ and $e_2$, which are local to the current state. The whole program becomes the (combinational) transition function of a Moore machine<fnref n="7" /> driven by the global clock.

<footnote n="6">⁶ Each tail-recursive function definition becomes a state in an underlying hierarchical automaton. Calling a tail-recursive function *f* becomes a transition to the corresponding state (this implements *pauses* from the semantics).</footnote>

<footnote n="7">⁷ ECLAT provides circuit parallelism, with no extra cost for synchronization (no lost cycle). The reduction order $(v \parallel \square)$ for parallel branches in the semantics is convenient for reasoning on the behavior of programs and it does not impact performance.</footnote>
Consider a sequence **let x = e₁ in e₂** where *e₁* and *e₂* are instantaneous. If there is a data dependency between *e₁* and *e₂* (i.e., if *x* does occur in *e₂*), a wire *x* connects *e₁* to *e₂* and therefore, the critical path (i.e., the Worst Case Execution Time) could increase, but the design remains synthesizable up to a limit imposed by the frequency of the physical clock. If there is no data dependency between *e₁* and *e₂*, both can be implemented as parallel hardware.

General recursion is not supported because it would limit scalability and exploitable parallelism; but it can be encoded by the programmer using explicit stacks implemented as vectors or arrays, the later being presented in sec. 3.

## 3 Mixing synchrony and shared memory

Hardware description languages such as VHDL support array types. Synthesis tools implement such arrays either as collections of logic elements or using on-chip RAM blocks. The former is only applicable to arrays of small size because it consumes a large number of logic elements both for storage and for the addressing circuitry. The latter requires that the source code is written using a specific pattern to be correctly recognized and handled by the synthesizer. This pattern induces extra clock cycles to access data stored in the RAM blocks.

This section presents how mutable arrays can be formalized in ECLAT to be implemented using RAM blocks. ECLAT takes advantage of the underlying synchronous model to safely support concurrent memory accesses, in a predictable and fair way, while exploiting physical parallelism at the circuit level.

### 3.1 Mutable arrays in ECLAT

The array operations provided in ECLAT are listed in the upper part Fig. 5. These operations come with a few ECLAT features that have not been presented in the last section (Fig. 1 and 3). This includes a type constructor $\hat{\tau} \text{ array}
$, which represents arrays of length *s* with elements of basic type $\hat{\tau}$.

Operator `create
` (of type scheme $\forall \hat{\tau} \cdot \text{unit} \rightarrow \hat{\tau} \text{ array}<s$)) creates an array of length *n* with unspecified values of a given type $\hat{\tau}$. Operator `length` instantaneously returns the length of its array argument. Operators `get` and `set` allow for reading and modifying arrays. Each array creation returns a location *l*, which is a value, associated with a data structure located in memory. Each location is protected by a lock, which is explicitly manipulated by the `%acquire` and `%release` primitives. No location nor `acquire/release` operations appear in source programs; these are hidden in the definitions of `get` and `set`. Arrays are not immediate values (i.e., constants and pairs of immediate values) unlike vectors (of basic type `\hat{\tau} \text{ vect}
`) presented in sec. 2.1.

In concrete syntax, we simply write `create e` by letting the compiler statically evaluate a simple arithmetic expression `e` to an integer for inferring the length of the array to be created. The sequence $e_1; e_2$ stands for `let_ = e_1 in e_2` with `_` a wildcard pattern. The macro expression `parfor x = e_a to e_b do e done` builds the expression `let_ = (e_i || ... || e_j) in ()` with $e_a$ (`resp. e_b`) an arithmetic expression statically evaluated to `i` (`resp. j`) and $e_k \stackrel{\text{def}}{=} (\text{let } x = k \text{ in } e)_{k \in \{i, \dots, j\}}$.
<figure><img src="image_5.png" /><figcaption>**Fig. 5** Syntax and semantics of array operations (as an extension of Fig. 1 and 3)</figcaption></figure>

The behavior of array operations in ECLAT is formalized on the lower part of Fig. 5. It is based on the operational semantics of ECLAT (previously defined in Fig. 1 and 3) and mainly consists in refining the semantic function $\vartheta$ used to specify, by cases, the behavior of each ECLAT operator.

A memory $\mu$ (kept abstract in the last section) is a partial function from memory locations to values. Memory locations are denoted with meta-variable $\ell$. We note $\mu(\ell)$ (resp. $\mu[\ell \mapsto v]$) the value stored at location $\ell$ in $\mu$ (resp. the new memory obtained by assigning a value $v$ to location $\ell$ in $\mu$).

Array creation returns a location $\ell$ mapped to a value representing an array in the memory (rule $\vartheta$-CREATE). In the semantics, this value is encoded as two nested pairs $(\mathit{lock}, (N, \mathit{content}))$ where:

* $\mathit{lock}$ is a boolean indicating if the lock associated with the array is held,

* $N$ is the length of the array,

* $\mathit{content}$ represents the $N$ elements of the array as a tuple. For example, an array of integers will be encoded as `(false, (4, (0,0,0,0)))`.

The role of the two pauses performed by `get` and `set` (cases $\vartheta$-GET and $\vartheta$-SET) is to accurately reflect the behavior of the hardware implementation (a synchronous Moore machine) that is generated by the ECLAT compiler<fnref n="8" />.

Concurrent memory accesses are safe because of the lock mechanism, which is specified by cases `ACQUIRE` and `RELEASE`. When the lock associated with location $\ell$ is already held, any other access to $\ell$ is delayed until the lock is released (cases $\vartheta$-GET-WAIT and $\vartheta$-SET-WAIT). As there is one lock per array, parallel accesses to different arrays are executed “simultaneously”, i.e., in the same sequence of clock cycles. For instance, the expression defined on the left side of Fig. 6 behaves as depicted in the chronogram on the right side:

<footnote n="8">⁸ The address of the element to be read in the RAM block is set *at next clock tick*. Then, the RAM block (which also behaves as a Moore machine) makes the read value available one clock cycle later.</footnote>
**at cycle 0:** after sequentially creating the two arrays, the left branch of the parallel (x) acquires the lock associated with array a (which is noted $A_a$ in the chronogram) and starts a sequence of two pauses (which are noted “-”) as specified by ARRAYSET in Fig. 5; then, the right branch (y) does the same with array b ($A_b$);

**at cycle 1:** x performs its second pause, then y performs its second pause;

**at cycle 2:** x releases the lock of a ($R_a$); then y releases the lock of b ($R_b$).

<figure><img src="image_6.png" /><figcaption>Fig. 6 ECLAT expression simultaneously executing two independent array accesses</figcaption></figure>

<table><tr><td>cycles:</td><td>0</td><td>1</td><td>2</td></tr><tr><td>x:</td><td>A<sub>a</sub>; -</td><td>-</td><td>R<sub>a</sub></td></tr><tr><td>y:</td><td>A<sub>b</sub>; -</td><td>-</td><td>R<sub>b</sub></td></tr></table>

## 3.2 Concurrent programming

The semantics of ECLAT provides the programmer with a predictable mechanism for dealing with concurrency:

* **left-to-right reduction order:** if two expressions $e_{\text{left}}$ and $e_{\text{right}}$ start at the same cycle and are put in parallel (e.g., ($e_{\text{left}} \parallel e_{\text{right}}$)), then $e_{\text{left}}$ always reduces before $e_{\text{right}}$ (though the implementation, which statically encodes this reduction order in synchronous dataflow style, is intrinsically parallel);

* **atomicity of sequential composition:** if an access to $\ell$ is followed by expression e, then e always reduces before any concurrent access waiting for $\ell$.

For example, there is no data race in the program defined in Fig. 7. We have the guarantee that it always evaluates to 43, as illustrated in the execution trace:

**at cycle 0:** the array is created; then the first binding (x) acquires the lock and pauses (-); then the second binding (y) tries to acquire the lock but cannot (X) because the lock is already held by x.

**at cycle 1:** x is paused (the array write progresses); then y is reduced but it has to wait because the lock is already held by x.

**at cycle 2:** x releases the lock and atomically continues as far as possible: it acquires the lock again and pauses; then y has to wait because the lock is already held by x.

**at cycle 3:** x is paused (the array read progresses); then y has to wait because the lock is already held by x.

**at cycle 4:** x releases the lock and returns value 44; then y acquires the lock and pauses.

Note that this strict ordering of operations does not prevent the programmer from writing programs whose behavior cannot be predicted statically. For example, in the following expression, the writing order (and thus the result) depends on the duration of the two calls to `collatz` (defined in Fig. 4):

```python
let _ = ( (collatz(i); set((a,0),1))
           || (collatz(j); set((a,0),42)) ) in get(a,0)
```
<figure><img src="image_7.png" /></figure>

<table><caption>**Fig. 7** ECLAT program and its execution trace with atomic sequential composition</caption><thead><tr><th></th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><th>cycles:</th><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>x:</th><td>A<sub>a</sub>;-</td><td>-</td><td>R<sub>a</sub>;A<sub>a</sub> -</td><td>-</td><td>R<sub>a</sub></td><td></td><td></td></tr><tr><th>y:</th><td>X</td><td>X</td><td>X</td><td>X</td><td>A<sub>a</sub>;-</td><td>-</td><td>R<sub>a</sub></td></tr></tbody></table>

The trade-off between expressiveness and predictability therefore remains in the hand of the programmer.

When programming in ECLAT, one might question the fairness of the mechanism for concurrent memory accesses. The lock mechanism of ECLAT is intrinsically fair with regard to the following criterion: let $n$ parallel expressions ($e_1 \parallel e_2 \parallel \cdots e_n$) performing concurrent memory accesses and $i < j < k < n$. If $e_j$ holds a lock and both $e_i$ and $e_k$ wait for this lock, then $e_k$ will always take the lock before $e_i$. This comes from the left-to-right reduction order property (sec. 3.2) because at each cycle, $e_i$ is reduced before $e_j$, and thus before $e_j$ releases the lock, which is then available when reducing $e_k$.

This is exemplified with the program defined in Fig. 8. Each time an array access starts, it acquires the lock ($A_a$) for two cycles until the lock is released ($R_a$). Any other access to $a$ while the lock is hold is delayed. This directly comes from the behavior of the ECLAT parallel construct ($e_1 \parallel e_2$): at each clock cycle, $e_1$ is instantaneously reduced until it becomes a pause or a value, then $e_2$ is instantaneously reduced until it becomes a pause or a value, and there is a synchronization at the end of the cycle, resulting in a deterministic parallelism. The chronogram in Fig. 8 gives the corresponding execution trace. An interesting point occurs at cycles 7-8:

**at cycle 7:** no array access is executed; indeed, $x$ cannot acquire the lock because $z$ already holds it since cycle 5; then $y$ cannot acquire the lock; then $z$ releases the lock and continues with $f(2)$;

**at cycle 8:** $x$ acquires the lock (which has been released by $z$ at cycle 7) and pauses; then $y$ cannot acquire the lock: this is exactly the same configuration as at cycle 1.

<figure><img src="image_8.png" /><figcaption>**Fig. 8** Fair interlacing of concurrent memory accesses in an ECLAT program</figcaption></figure>
Note that construct ($e \parallel e'$) is not commutative (this is a specificity of ECLAT), but is associative. Reducing $((e_1 \parallel e_2) \parallel e_3)/\mu$ is reducing $e_1/\mu$ to $e'_1/\mu_1$ and $e_2/\mu_1$ to $e'_2/\mu_2$, and then $e_3/\mu_2$ to $e'_3/\mu_3$. Reducing $(e_1 \parallel (e_2 \parallel e_3))/\mu$ is reducing $e_1/\mu$ to $e'_1/\mu_1$, and then $e_2/\mu_1$ to $e'_2/\mu_2$ and $e_3/\mu_2$ to $e'_3/\mu_3$.

# 4 Evaluation

This section illustrates the ability to exploit in ECLAT both shared memory and fine-grained parallelism with significant performance gains compared to sequential code running on a CPU. It also shows how the programmer can easily estimate timing performance from ECLAT source code.

**Experimental setup** We target an Intel Max10 FPGA embedded on a Terasic DE10-Lite board. This circuit has a frequency of 50 MHz; it comprises 50K logic elements (LEs) and 1,638 Kbits of on-chip RAM blocks. Each ECLAT program is compiled to VHDL using the ECLAT compiler. All of the ECLAT programs presented here meet the timing requirements of the target (i.e., they can safely run using the global 50 MHz clock). The generated VHDL code is synthesized using the Quartus 22.1 Lite toolchain, which indicates resource usage (i.e., both the number of LEs and the number of RAM blocks used by the design). Execution time estimation is measured both by software-RTL simulation using GHDL<fnref n="9" /> and synthesis. Speedups are given with regard to sequential OCAML code running on an Intel core i7 CPU with 16 GB of RAM and a frequency of 2.2 GHz (i.e., 44 times faster than the global clock of the Max10 FPGA). OCAML code is compiled to native code using the OCAML compiler ocamlopt with optimizations enabled (-O3).

## 4.1 *Game of life* - first version

Fig. 9 is an implementation of Conway's Game of Life (Gol) using ECLAT. Note that this ECLAT program is also a valid OCAML program. Function `array_life` (lines 22-28) computes the next generation of a world of cells (being either alive or dead depending on the number of alive neighboring cells). The world is represented as an array of boolean cells. The higher-order function `array_mapi` (lines 15-20) has type $\forall \eta \cdot \forall \hat{\alpha} \cdot \forall \hat{\beta} \cdot ((((\mathit{int} \times \hat{\alpha}) \rightarrow \hat{\beta}) \times \hat{\alpha} \arrayltarrow \eta) \times \hat{\beta} \arrayrtarrow \eta)) \rightarrow \mathit{unit}$. It applies a function `f` to each element of a source array `src` and fills a destination array `dst`.

Function `array_mapi` performs a direct call to the local recursive function `aux` (taking one cycle), and then one read (2 cycles) plus one write (2 cycles) plus a recursive call (1 cycle) for each of the *N* iterations. The resulting execution time is $1 + \sum_{i=0}^{N-1}(2 + T(f_i) + 2 + 1)$ where $T(f_i)$ is the execution time of `f` applied to the *i*-th array element.

For processing one cell (i.e., reading it and modifying it in memory), the eight neighbors have also to be read, resulting in a throughput of $5 + 8 \times 2 = 21$ cycles per cell. When synthesized on the Max10 FPGA (clocked at 50 MHz),

<footnote n="9">⁹ http://ghdl.free.fr</footnote>
Fig 11 compares the performance of `vect_life` on FPGA for a world of size $n^2$ to that obtained with the previously mentioned `array_life` running as an OCAML program on a CPU. Fig. 11a gives the speedup and Fig. 11b the number of LEs and the corresponding percentage of LE usage (up to 50K LEs on the Max10 FPGA). The curves perfectly illustrate the kind of time-space trade-off that can be obtained by using ECLAT. The maximum observed speedup is significant: ×15,000 for a world of 5,000 cells. Beyond this limit, the design does not fit in the Max10 FPGA board we use<fnref n="11" />.

<figure><img src="image_9.png" /><figcaption>Fig. 11 Time-space trade-off in the `vect_life` implementation of GoL</figcaption></figure>

## 4.3 Game of life - version 3

To overcome the size limitation of the fine-grain parallel version described in sec. 4.2, a possible solution is to represent the world not as a single vector but as an *array* of vectors, each vector representing a line. With this formulation, lines will be stored in shared memory, and fine-grained parallelism can be exploited to process individual lines.

The corresponding implementation, named `vect_array_life`, is given in Fig. 12. Note that function `next_cell_with_lines(j,cell,line0,line1, line2)` (which is called in Fig. 12, line 5, but not given by lake of space) is very similar to function `next_cell` (line 6-10, Fig. 9): it determines if the current `cell` located at index *j* in line `line1` becomes dead or alive in the next generation, knowing the neighboring lines (`line0` and `line2`).

For a world of $N$ lines, `vect_array_life` reads $N+1$ lines, independently of the number $W$ of cells per lines. The transformation is performed in-place, there are $N$ array writes. The overall execution time is exactly $(2+2+1)N+1 = 5N+1$ cycles to process an entire world of size $N \times W$. The execution time and the number of RAM blocks grows linearly with $N$, while the number of LEs grows with $W$ exactly as in Fig. 11b. Note that `vect_array_life` is 10 times slower than `vect_life` for a same number of cells per line, but the world it processes can be 200 times larger.

Fig. 13 summarizes the performances (for both execution time and LEs/RAM usage) of all versions of GoL described in this section.

<footnote n="11">¹¹ High-end FPGAs have much more LEs, e.g., 2.8 million LEs in the Intel Stratix 10 (i.e., 56 times more than the Max10).</footnote>
<figure><img src="image_10.png" /><figcaption>Fig. 12 GoL, version 3 – the world is an array of vectors (i.e., a vector per line)</figcaption></figure>

<table><caption>Fig. 13 Space-time trade-off for different GoL implementations</caption><thead><tr><th>implementation</th><th>largest size</th><th>LEs</th><th>RAM</th><th>throughput</th></tr></thead><tbody><tr><td>Bakhteri et al. [3] (VERILOG)</td><td>64 × 64</td><td>68K</td><td>none</td><td>4,096 cells each cycle</td></tr><tr><td>GoL, v2 (vect_life)</td><td>72 × 72</td><td>47K</td><td>none</td><td>5,184 cells each cycle</td></tr><tr><td>GoL, v1 (array_life)</td><td>1,024 × 512</td><td>2K</td><td>1Mbit</td><td>1 cell each 21 cycles</td></tr><tr><td>GoL, v3 (vect_array_life)</td><td>2,048 × 512</td><td>49K</td><td>1Mbit</td><td>2,048 cells each 5 cycles</td></tr></tbody></table>

## 5 Developing parallelism skeletons with ECLAT

This section presents parallel implementations of *map* and *pipe* algorithmic skeletons using ECLAT. It focusses on composability and gives an example of performance prediction, experimentally corroborated.

The *map* skeleton is classically used to apply a given function *f* to each element of an array. A parallel implementation of *map*, called *par_map*, is given in Fig 14 (lines 12-18). It takes a slice length *p*, a function *f*, a source array *src*, and a destination array *dst*. It applies *f* to the elements of *src*, traversing *p* slices of the source array in parallel (a call to *map_slice* per slice) using the macro-construct **parfor** presented in sec. 3. If the length of *src* is not a multiple of *p*, the remaining elements are processed sequentially (line 18). The result array *dst* must be passed as an argument since, as already indicated, ECLAT functions cannot return arrays (which are not immediate values).

<figure><img src="image_11.png" /><figcaption>Fig. 14 A parallel implementation of *map*</figcaption></figure>
Let us add a new notation $f e_1 @@ e_2$ that stands for $f(e_1, e_2)$. Function `map` (lines 20-22) is a composable extension of `par_map`, avoiding passing the result array explicitly. For this, `map` takes (in addition to `p`, `f` and `src`) a continuation function `k`. It locally allocates a destination array `dst` (line 21), calls `par_map(p,f,src,dst)` and then applies `k` to `dst`. For example, applying two maps in sequence with function `f` and then `g` (for a given degree of parallelism `p`) is expressible as: `map(p,f,src) @@ fun a -> map((p,g,a),k)`.

In Fig. 15 is defined another parallel implementation `mapFarm`, using a so-called worker farm for applying on request the `f` function to the elements of the `src` array. This is well-suited when `f` has an irregular execution time depending on the elements of `src`. Workers communicate via a shared variable `r`, which is an array of length 1 containing the index of the next array element to be processed. Each time a worker is available, it: (1) reads the index given by `r`; (2) increments `r`; (3) processes one element, this until the integer `i` referenced by `r` reaches the end of the source array. The important point is that steps (1) and (2), i.e., reading and writing `r` (lines 3-5), are always performed atomically (as explained in sec. 3.2).

```hsharp
1 let worker (f,r,src,dst) =
2 let rec loop() =
3 let i = get(r,0) in
4 if i >= length src then () else
5 let (((),x) = (set((r,0),i + 1)
6      || get(src,i)) in
7 (set(dst,i,f(x)); loop())
8 in loop() ;;
```

```hsharp
let mapFarm((p,f,src),k) =
let r = create 1 in
set((r,0),0);
let dst = create (length src) in
parfor _ = 0 to p-1 do
    worker(f,r,src,dst)
    done;
k(dst) ;;
```

<caption>Fig. 15 Parallel implementation of map using a worker farm</caption>

In Fig. 16 is defined a `pipe3` skeleton. Functionally, `pipe3((f1,f2,f3,src),k)` is equivalent to `map(1,f1,src) @@ fun a1 -> map(1,f2,a2) @@ fun a2 -> map((1,f3,a2),k)`, but these successive `maps` (or `stages`) are parallelized. The implementation described here could easily be generalized by hand to achieve more parallelism (i.e., more stages). On the left side of Fig. 16 is defined a function `semi_pipe`, which consumes the elements $x_i$ of `src` if their position `i` is less than the index referenced by `rI` and otherwise actively waits. Function `f` is applied to each $x_i$ consumed. Then, `semi_pipe` assigns the resulting value in `dst` (line 9) and increments the shared variable `r0` (line 10) to notify that `dst` is ready to be processed up to index `i`. On the right side of Fig. 16, `pipe3` creates intermediate arrays and shared variables (the latter being initialized to 0, except for `r0`, which takes value $n = length src$ to notify that `src` is ready to be consumed), calls the `semi_pipes` in parallel, and then `k`.

*Performance prediction* A key aspect of the synchronous semantics of ECLAT is the ability to predict the execution time of parallel programs. Let's illustrate this with an example. The `par_map` skeleton (defined in Fig. 14) calls `map_slice(a,b,f,src,dst)`, `p` times in parallel. Each of these calls comprises
<figure><img src="image_12.png" /><figcaption>Fig. 16 ECLAT implementation of a three-stage pipeline</figcaption></figure>

one direct call to function aux (taking one clock cycle) followed by one read (2 cycles), one call to f, one write (2 cycles) and one tail-recursive call (1 cycle) per iteration. Let $T(f_i)$ be the execution time of f when applied to the i-th element of array src and let N be the length of src. The execution time of map_slice (in cycles) is:

$$T_{\text{map\_slice}}(a, b) = 1 + \sum_{i=a}^{b-1} (2 + T(f_i) + 2 + 1)$$

For the sake of simplicity, assume f is stateless<fnref n="12" /> and N is a multiple of p. Due to the fairness of execution (explained in sec. 3.2), the execution time of map_par is the maximum execution time among each $T_{\text{map\_slice}}$ plus an amount of time $T_{\text{stalls}}$ (or lost cycles) spent in sequentializing concurrent accesses<fnref n="13" />:

$$T_{\text{map\_par}} = \max_{i=0}^{p-1} \left( T_{\text{map\_slice}}(i \times N/p, (i+1) \times N/p) \right) + T_{\text{stalls}}$$

If the computation time dominates the access time, then $T_{\text{stalls}}$ becomes negligible. Note that $T_{\text{stalls}}$ is clearly less than $4N$, i.e., the cost of sequentially traversing src ($N$ reads) and updating dst ($N$ writes). The chronogram in Fig. 17, gives the beginning of the execution of map_par for a regular computation such that $T(f_i) = T_f$ and $T_f = 2p - 4$. There are $2p - 2$ stalls ($X$) at initiation (since each call to map_slice simultaneously tries to read src, but only one acquires the lock ($A_{src}$) at a time. Note that in this specific case, after initiation, there are no stalls anymore. From this we can deduce that, for any stateless function f such that $T_f \ge 2p - 4$, we have $T_{\text{stalls}} = 2p - 2$ cycles. In other words, if $T_f \ge 2p - 4$, then the computation of f dominates accesses.

This theoretical result is verified in practice. For example, for $N = 3, 200$ and $p = 16$ and f such that $T_f = 2p - 4 = 28$ cycles, the measured execution time of par_map is 6,631 cycles, i.e. $(1+\max_{i=0}^{p-1}(2+28+2+1)N/p)+(2 \times p - 2)$.

<footnote n="12">¹² The programmer is free to compose complex behaviors (e.g., global array accesses from the function f to be parallelized): this remains deterministic, with a trade-off between expressiveness and predictability.</footnote>

<footnote n="13">¹³ Each mapslice reads src and write dst concurrently.</footnote>
<figure><img src="image_13.png" /><figcaption>Fig. 17 Initiation of map_par with $T(f_i) = T_f = 2p - 4$ (stalls are noted $\times$)</figcaption></figure>

This is 15.93 times better than for $p = 1$, and therefore optimal with respect to the degree of parallelism. Fig. 18 gives the measured speedups (on the left) and execution times (on the right) for map_par depending on $p$ and $T_f$ with regard to $p = 1$. This clearly suggests that, if the ratio $T_f/p$ is low, then the accesses dominate the computation and the speedup does not increase with $p$ anymore. This can be used to deduce that, for instance, it is useless to parallelize $f$ more than eight times if $T_f = 12$, because the resulting $\times 7.99$ speedup is optimal.

<figure><img src="image_14.png" /><figcaption>Fig. 18 Measured speedups and execution times for map_par in function of $p$ and $T_f$</figcaption></figure>

## 6 Related work

ECLAT is a descendant of the MACLE language [15] that has been used for hardware accelerating OCAML functions on an FPGA, in combination with a softcore-based implementation of the OCAML virtual machine. The ECLAT compiler adapts the MACLE compilation scheme to correctly implement the cycle-accurate semantics of ECLAT. In particular, constructs *let* and $(e_1 \| e_2)$ induce no extra clock cycle in ECLAT, in contrast to MACLE.

ECLAT is part of a long-standing tradition of Functional Hardware Description Languages. CASH [2], for example, is subset of HASKELL compiled to RTL. Computations have to be encoded as Mealy machines, which requires knowledge of both HASKELL and structural hardware design.

CEMENT [17] extends an HDL core with control structures in imperative style while preserving cycle-accuracy and predictability. These constructs are used to explicitly synchronize pipeline stages or communicate with external modules (such as RAM blocks) responding in several cycles. The tool incorporates dynamic monitoring to detect timing violations (e.g., concurrent accesses) during software-RTL simulation. ECLAT pushes this approach further by providing a cycle-accurate programming language.

Synchronous languages SCADE and LUSTRE V6 have functional arrays with predefined parallel skeletons (called *iterations*) [4]. Reads and updates (by copy)
are performed within the clock cycle. This is similar to ECLAT immutable vectors. ECLAT mutable arrays behave differently, due to FPGA design constraints: concurrent accesses must be sequentialized and communication with memory components induces synchronizations on clock ticks.

Whereas semantics in mainstream parallel programming (including scheduling and execution time) is usually informal, operational semantics have been proposed to model both the parallel and functional behavior of skeletons-based parallel libraries [1]. The formal semantic framework they proposed is based on a labeled transition system, which can be used to prove properties of programs. Our semantics framework is more programming-oriented. This is a similarity with BSML [10], which also has a small-step operational semantics and has been used to implement skeleton libraries. In BSML, every communication step must be followed by a synchronization step. This aims to provide language abstractions (such as higher order functions, pattern matching and exceptions) without sacrificing scalability and predictability of performance.

Reduction semantics have been used to model timing in cycle-accurate reactive languages such as ESTEREL [9] and ReactiveML [13]. As in our work, each cycle encompasses a sequence of small-step reductions. In these languages, given two processes *p* and *q*, reducing (*p*||*q*) can be carried (□||*p*) and (*q*||□). By contrast, ECLAT enforces a left-to-right reduction order for (*e*₁||*e*₂).

Recent works such as FPX [14] have tackled the difficulty of produce time and space-efficient code for FPGA architectures involving a host CPU from parallel software code. FPX is a framework to accelerate general-purpose Data Stream Processing (DSP). It provides a parametrizable Domain-Specific Language (DSL) embedded in Python, in which the application programmer can define dataflow operators as sequential programs and compose them to form the DSP application (that is a graph of dataflow operators). The programmer is no longer responsible for the low-level implementation details, which is obtained by code generation (using OpenCL as intermediate representation) combined with a runtime library implementing efficient data-flow components.

# 7 Conclusion

This paper has presented ECLAT, an OCAML-like programming language for implementing hardware applications on FPGAs. ECLAT unifies functional, parallel and synchronous programming under the global clock of the target FPGA. The semantics of the language is deterministic, by following the synchronous hypothesis [11]: all programming constructs reduce instantaneously, except tail-recursive function calls (which *pause* for one cycle) and memory accesses (which *pause* for two cycles, the concurrent accesses being sequentialized).

At compile time, functions defined with the `let` keyword are duplicated (by inlining) while those defined with `let rec` are shared (with dynamic dispatching of the callers for function return). Pauses on tail-calls allow the programmer to decrease the width of the combinatorial parts of the circuit.

This programming model enables performance prediction to a large extent while being quite intuitive for software programmers. It is expressive enough
to exploit fine-grained parallelism and explore the space-time trade-off inherent to FPGA programming, resulting in significant speedups with regard to sequential CPU execution. Moreover, it enables abstraction, by letting the programmer define and compose higher-order functions, including algorithmic skeletons such as *map* and *pipe*, with predictable performance.

We are currently working on enabling skeleton-based FPGA programming in a hardware implementation of the OCAML virtual machine written in ECLAT [16]. As future work, we plan to provide in ECLAT a Foreign Function Interface to use RTL code. We will also access external SDRAM memory from ECLAT to program real-time FPGA applications with more data and scale up.

## References

[1] M. Aldinucci and M. Danelutto, "Skeleton-based parallel programming: Functional and parallel semantics in a single shot," *Computer Languages, Systems & Structures (CLSS)*, vol. 33, no. 3-4, pp. 179-192, 2007.

[2] C. Baaij, M. Kooijman, J. Kuper, et al., "CLash: Structural descriptions of synchronous hardware using haskell," in *Euromicro Conference on Digital System Design (DSD): Architectures, Methods and Tools*, IEEE, 2010, pp. 714-721.

[3] R. Bakhteri, J. Cheng, and A. Semmelhack, "Design and implementation of cellular automata on FPGA for hardware acceleration," *Procedia Computer Science*, vol. 171, pp. 1999-2007, 2020.

[4] A. Benveniste, P. Caspi, S. A. Edwards, et al., "The synchronous languages 12 years later," *Proceedings of the IEEE*, vol. 91, no. 1, pp. 64-83, 2003.

[5] C. Bernardeschi, L. Cassano, and A. Domenici, "SRAM-based FPGA systems for safety-critical applications: A survey on design standards and proposed methodologies," *Journal of Computer Science and Tech. (JCS&T)*, vol. 30, pp. 373-390, 2015.

[6] G. Berry, "A Hardware Implementation of Pure Esterel," *Sadhana, Academy Proceedings in Engineering Sciences, Indian Academy of Science*, vol. 17, no. 1, 95-130, 1992.

[7] Y.-k. Choi, P. Zhang, P. Li, et al., "HLScope+: Fast and accurate performance estimation for FPGA HLS," in *IEEE/ACM International Conference on Computer-Aided Design (ICCAD)*, IEEE, 2017, pp. 691-698.

[8] M. Felleisen and R. Hieb, "The revised report on the syntactic theories of sequential control and state," *Theoretical computer science*, vol. 103, no. 2, pp. 235-271, 1992.

[9] S. P. Florence et al., "A calculus for Esterel: if can, can. if no can, no can.," *Proc. of the ACM on Prog. Languages (PACMPL)*, vol. 3, no. POPL, pp. 1-29, 2019.

[10] F. Gava and F. Loulergue, "Semantics of a functional BSP language with imperative features," in *Advances in Parallel Computing*, vol. 13, Elsevier, 2004, pp. 95-102.

[11] L. Gonnord, L. Henrio, L. Morel, et al., "A survey on parallelism and determinism," *ACM Computing Surveys*, vol. 55, no. 10, pp. 1-28, 2023.

[12] Y.-H. Lai, E. Ustun, S. Xiang, et al., "Programming and synthesis for software-defined FPGA acceleration: status and future prospects," *ACM Transactions on Reconfigurable Technology and Systems (TRETS)*, vol. 14, no. 4, pp. 1-39, 2021.

[13] L. Mandel and M. Pouzet, "ReactiveML: a reactive extension to ML," in *Principles and practice of declarative programming (PPDP '05)*, 2005, pp. 82-93.

[14] A. Ottimo, G. Mencagli, and M. Danelutto, "Boosting general-purpose stream processing with reconfigurable hardware," *The Journal of Supercomputing*, pp. 1-31, 2024.

[15] L. Sylvestre, E. Chailloux, and J. Sérot, "Accelerating OCaml programs on FPGA," *International Journal of Parallel Prog. (IJPP)*, vol. 51, no. 2, pp. 186-207, 2023.

[16] L. Sylvestre, J. Sérot, and E. Chailloux, "Hardware implementation of OCaml using a synchronous functional language," in *Practical Aspects of Declarative Languages (PADL)*, Springer, 2024, pp. 151-168.

[17] Y. Xiao, Z. Luo, K. Zhou, et al., "Cement: Streamlining FPGA hardware design with cycle-deterministic eHDL and synthesis," in *Field Programmable Gate Arrays (FPGA '24)*, 2024, pp. 211-222.