\section{Microarchitecture}\label{sec:micro}

This section describes Manticore's microarchitecture and its efficient FPGA implementation.
We prototype Manticore on a Xilinx UltraScale+ FPGA (the Alveo U200 datacenter FPGA card).
The ideas, however, are general and apply to other FPGAs and ASIC implementations.

\figRef{manticore_array} depicts an example 6-core Manticore grid.
Manticore operates as a coprocessor for a \emph{host} (e.g., an x86 processor), which loads programs on Manticore and handles exceptions or termination.
The host communicates with the grid by reading and writing specific registers and has full access to Manticore's DRAM.
\begin{figure}[h]
    \includegraphics[width=\linewidth]{figures/noc.pdf}
    \caption{
        A Manticore grid of processors on a uni-directional 2D torus NoC.
        The cores and the NoC reside in the \emph{compute} clock domain, while all other components reside in the \emph{control} clock domain.
        The privileged core is connected to a cache and can access off-chip DRAM.
    }
    \label{fig:manticore_array}
\end{figure}

\subsection{Pipeline Implementation}

Each core is implemented with a simple 14-stage pipeline.
The pipeline is simple because we remove expensive bookkeeping logic (e.g., interlocks and scoreboards) and delegate them to the compiler.
The logical pipeline is the usual five stages: fetch, decode, execute, memory access, and writeback.
Each stage is internally pipelined to achieve a high clock frequency.
A block diagram of the pipeline is available in the Appendix (\figRef{manticore_micro}).
RTL code contains structures of various bit widths that are typically narrower than a conventional processor's 32-bit word size.
Manticore uses a 16-bit datapath to match the native width of the FPGA's hard DSP units.
This further simplifies the hardware and enables higher clock frequencies.

Instructions are fetched over two cycles from a dedicated instruction memory mapped to a 4096$\times$64 URAM.
URAMs are large 36~KiB on-chip memories.

Deep pipelines require a large register file to avoid stalls.
We use a \emph{2048-element} register file in which all registers are exposed to the compiler to avoid expensive renaming logic in hardware (similar to the Raw machine~\cite{waingold_baring_1997}).
We implement the register file using BRAMs.
BRAMs are configurable 4.5~KiB on-chip memories that support multiple addressing modes.
We use a 2048$\times$17 addressing mode where the lower 16 bits contain the register value, and the most-significant bit contains an \emph{overflow bit} used by wide addition instructions.
The size of the register file requires additional pipelining for reads.
This makes decoding three stages long.
Some instructions can read four values from the register file and write a single result.
This requires four read ports and one write port, which BRAMs do not natively support\footnote{BRAMs and URAMs have one read port and one write port.}.
We use four identical BRAMs that are write-mirrored to read four values simultaneously.

The execute stage consists of two computational units pipelined over four stages.
The ALU handles most standard instructions using a hardened FPGA DSP.
The custom function unit (CFU) is implemented as a small 32$\times$256 memory made of LUTRAMs.
LUTRAMs are FPGA primitives used to implement shallow memories.
A 1-bit 4-input boolean function is canonically defined by the 16 bits of its truth table.
Manticore's datapath is 16 bits wide, so we extend this idea to a wider 16-bit truth table using $16 \times 16 = 256$ bits of memory per function.

Scratchpads are mapped to a URAM, with two cycles to access and one cycle to reshape.
We reshape a 4096$\times$64 URAM into a 16384$\times$16 memory by using byte-strobes on the write path and multiplexers on the read path.

\subsection{Network-on-Chip}\label{sec:noc_if}

The cores communicate over a uni-directional torus NoC with buffer-less switching and dimension-ordered routing~\cite{hoplite}.
We chose this design to reduce routing congestion on the FPGA and to support a high clock frequency.

Switches do not queue messages and immediately route them.
A switch drops the input message if the target link is busy.
The compiler statically schedules \textcode{Send} instructions to avoid data loss.
Manticore's deterministic execution makes this possible.

Links carry 27 bits of payload, and a few\footnote{Varies based on the grid size, e.g., 8 bits for a 15$\times$15 grid.} bits to specify the target core address.
Arriving messages at a core are queued and received only when the core finishes a \vcycle (see \figRef{isa_overview}).
We use the instruction memory and its unused write port as the queue to save resources.
We do this by encoding an incoming message as an instruction and pushing it to the end of the instruction memory.
The core then executes it like any other at the end of a \vcycle (see \figRef{manticore_micro} in the Appendix).

\subsection{Global Stall}\label{sec:global_stall}

In our current implementation, the privileged core is connected to a 128 KiB direct-mapped, write-allocate, write-back cache backed by a DRAM bank.
The cache is implemented using 4 URAMs and has a fixed latency whether an access misses or hits.
A cache miss triggers a DRAM access, which stalls all cores and the NoC until the DRAM access is complete.
Therefore, from the compiler's point of view, a global memory access appears to all cores as a fixed latency operation independent of DRAM latency.

Implementing the stall by routing a global signal from the cache to each core does not scale to hundreds of cores.
Instead, we take advantage of the FPGA's clock gating primitives to achieve this functionality.
All parts of Manticore that operate in strict lockstep (the cores and the NoC) reside in the \emph{compute} clock domain.
The rest of the logic that deals with non-determinism resides in the \emph{control} clock domain (see \figRef{manticore_array}).
The two domains are frequency-matched and phase-aligned.
The logic in the control domain has the ability to \emph{halt} or \emph{resume} the compute clock with a global clock buffer.
\figRef{manticore_array} highlights these two clock domains.

We took great care in implementing the clock gating logic to minimize its effect on scalability.
For instance, there is no logic delay from the clock enable signal to the clock buffer that receives it.
The result is that clock gating logic is nearly independent of the number of cores.

With global clock gating, computation is frozen on a cache request and resumed once it completes.
The same mechanism is used to stall the compute domain when an exception occurs so that exceptions are precise.
Control is then transferred to the host machine and computation resumes at the host's command.

\section{Conclusion}\label{sec:conclusion}

RTL simulation is essential for hardware design, and faster simulation offers many benefits to hardware designers.
However, current approaches force a designer to choose between an FPGA prototype's long compile times and fast execution, or an RTL simulator's fast turnaround and slow speed.
RTL simulation is slow because even state-of-the-art simulators struggle to exploit RTL circuits' abundant fine-grained parallelism to improve their performance due to the high cost of frequent communication and synchronization on modern processors.

This work presented Manticore, a prototype, hardware-accelerated RTL simulator.
Manticore exposes a \emph{deterministic} hardware interface that allows its compiler to \emph{statically} schedule programs across hundreds of simple processors.
This approach eliminates costly runtime synchronization and enables efficient parallel simulation of RTL circuits.
Our FPGA prototype of Manticore demonstrated a peak speedup of 27.9$\times$ faster simulation rate (geomean 5.3$\times$) over a state-of-the-art software RTL simulator for Verilog workloads.
This initial Manticore system demonstrates the performance benefits of exploiting fine-grained parallelism in RTL code.

\section{Introduction}\label{sec:introduction}

The long-anticipated end of Moore's Law and Dennard Scaling has dramatically increased commercial and academic interest in computational accelerators~\cite{groq_think_fast,catapult_v2,hennessy_new_2019,catapult_v1,tpu_v2,cerebras_stencil,tpu}.
As with any hardware artifact, accelerators require many iterations of design, debugging, testing, and software development.
Detailed hardware simulation is at the heart of this activity, and a simulation's turnaround time and throughput can directly affect designer productivity and product quality.

Designers, however, face a dilemma.
Software RTL simulators offer much faster turnaround and better visibility into the hardware than prototypes (e.g., on FPGAs).
Simulation, however, runs much slower than hardware, which can be a bottleneck when simulating a large design, running a long execution, or performing extensive testing.

Since the advent of multicore, parallelism is the preferred approach to improve software performance.
RTL simulation appears to offer many opportunities for parallelism.
Indeed, hardware description languages (HDL) such as Verilog or VHDL~\cite{flake_verilog_2020} contain parallel constructs for describing parallel hardware components that run independently and synchronize only at clock edges.
However, designers want circuits that run at high clock frequencies, which constrains the number of gates between clock edges.
Therefore, a realistic RTL design comprises many \emph{tiny}, independent computation tasks.
The resulting fine-grain parallelism interacts poorly with multicore processors because frequent synchronization and communication are (relatively) costly.

This work explores a different approach to improving RTL simulation performance.
We design and construct \emph{Manticore}, an architecture for parallel RTL simulation (i.e., a simulator accelerator).
Manticore leverages a \emph{static bulk-synchronous parallel} (BSP~\cite{valiant_bridging_1990}) execution model that virtually eliminates dynamic overheads of RTL simulation through static scheduling.
Similar to computers such as MIT's Raw machine~\cite{waingold_baring_1997}, Manticore relies entirely on its compiler to statically schedule resources and communication.
Because RTL code rarely exhibits long divergent code paths, static scheduling is feasible.
The resulting scheduled communication and synchronization run without overhead, so fine-grain interactions among cores are efficient.
Moreover, static scheduling dramatically simplifies the microarchitecture, significantly increasing the parallelism possible on a chip.

Manticore's compiler accepts single-clock RTL designs and generates binary code that runs on a Manticore coprocessor.
Compilation time is comparable to software compilers, offering software development-like turnaround but a significantly faster simulation rate.
We prototyped Manticore on an FPGA, and it outperforms Verilator~\cite{snyder_verilator_2020} (the fastest open-source RTL simulator) running on a Xeon processor by up to 27.9$\times$ (geomean 5.3$\times$), despite running at a fraction of the Xeon processor's clock speed.
Hardware-accelerated simulation offers a designer a path out of the dilemma above by optimizing ``time to result.''
Small experiments and tests can run on a software simulator with very fast turnaround.
More extensive experiments and tests can run on Manticore, with slightly slower compile times but much faster execution.
And hardware prototypes can be reserved for full-system simulation, operating system bring up, and software development.

The chief contributions of this work are:
\begin{itemize}
  \item The application of a static BSP execution model to RTL simulation,
  \item The Manticore architecture that supports fine-grain parallelism in the simulation of RTL through static BSP,
  \item A compiler that finds parallelism in RTL code and statically schedules it to run effectively on Manticore,
  \item A high-performance FPGA prototype of Manticore,
  \item An extensive evaluation analyzing the superior performance of Manticore over state-of-the-art software RTL simulation.
  \item A demonstration that the fine-grain parallelism in RTL simulation can be effectively exploited.
\end{itemize}
We will open-source Manticore's compiler and hardware upon publication.

The paper is organized as follows:
\secRef{background} discusses RTL simulation and quantitatively explores the inherent limitation of general-purpose processors for exploiting its fine-grained parallelism.
\secRef{static_bsp} presents the static BSP execution model.
\secRef{design} presents Manticore's architecture.
\secRef{micro} discusses a high-performance implementation of Manticore.
\secRef{compiler} presents the compilation techniques used to exploit Manticore's hardware.
\secRef{evaluation} evaluates Manticore's performance and design decisions.
\secRef{discussion} discusses limitations and future directions.
\secRef{related_work} surveys closely related work.
Finally, \secRef{conclusion} concludes.
\section{Compiler}\label{sec:compiler}

Manticore's hardware is co-designed with its compiler, which is responsible for extracting parallelism, custom function synthesis, and instruction scheduling.
\figRef{compiler_flow} sketches the compilation process.
The compiler operates on two related intermediate representations (IR): netlist and lower assembly.
Both use static single assignment and can be interpreted in software.
The lower interpreter is a full-fledged ISA simulator parameterized by the hardware configuration.
We used the interpreters extensively to validate the compiler passes.

\begin{figure}[h]
  \centering
  \includegraphics[width=\linewidth]{figures/compiler.pdf}
  \caption{
    Manticore compiler.
    Frontend in red, backend in green.
    A host communicates with the Manticore co-processor through a runtime shown in blue.
  }
  \label{fig:compiler_flow}
\end{figure}

We based the Verilog frontend on Yosys~\cite{yosys}.
We extended Yosys to support basic system calls such as \textcode{\$display} and \textcode{\$stop} that are required for simulation.
After parsing the Verilog input, the frontend performs a few optimizations and emits netlist assembly.
Because of the semantics of RTL code, instructions in netlist assembly are unordered and have arbitrary-width operands.

The backend orders the instructions and applies simple optimizations (dead code elimination, constant folding, and common sub-expression elimination).
We then transform the netlist assembly instructions into an equivalent sequence of lower assembly instructions whose operands match Manticore's 16-bit data path.
Initially, the lower assembly is a monolithic sequence of instructions (a single process).
After further optimizations, the compiler partitions the instructions into multiple processes.
The compiler then optimizes each process by fusing chains of bitwise logic instructions into custom instructions.

The final steps of compilation are scheduling and register allocation.
Scheduling ensures that there are no data hazards in the pipeline by inserting \textcode{NOp} instructions to respect data dependencies.
In addition, the \textcode{Send} instructions must be scheduled to ensure timely message delivery.
The compiler then maps virtual registers in the assembly program to machine registers and emits binary code.
The binary is then loaded into Manticore over the NoC by a runtime running on a host x86.
The Appendix contains more details about the runtime (\secRef{runtime_appendix}).

The compiler is 18K lines of Scala.
The Yosys Verilog frontend passes are about 2K lines of C++.
The runtime is built on top of the Xilinx runtime library (XRT) with about 800 lines of C++ code.

\subsection{Extracting Parallelism}\label{sec:parallelization}

Partitioning instructions across the cores is the most critical step in achieving good parallel performance.
Despite the absence of runtime synchronization in Manticore, data movement is still costly and communication will limit scalability.
Our parallelization algorithm is aware of this cost and attempts to reduce NoC traffic while distributing work across cores such that each core executes roughly the same number of instructions.

The compiler parallelizes a single monolithic assembly process in two steps:
\begin{inlineenum}
  \item \emph{Split} the monolithic process into a maximal number of tiny processes.
  \item \emph{Merge} the split processes so that the total number of processes does not exceed the number of available cores.
\end{inlineenum}

Splitting closely follows the approach described in \secRef{static_bsp_rtl} and illustrated in \figRef{parsim}.
The compiler first creates a DAG representation of the monolithic process.
It then uses a backward traversal to partition all nodes reachable from the sinks to form independent smaller processes.
In creating the parallel processes, the compiler ensures that instructions that access the same memory region (e.g., an unpacked array in Verilog) end up in the same process to avoid moving large amounts of data every \vcycle.
Additionally, all privileged instructions must execute in the same process.
Partitioning can duplicate DAG nodes across multiple cores, maximizing parallelism at the expense of increased computation.

If we view the maximal set of split processes as a graph whose nodes denote processes and edges denote communication, then merging is a hyper-graph partitioning problem.
Existing partitioning tools~\cite{KaHyPar, metis} assume a \emph{linear} cost function, so merging two nodes adds their weight or cost.
However, optimizations such as data sharing and duplicate code elimination make merging non-linear, so we instead developed a heuristic algorithm.

The compiler estimates the execution time of a process as the total number of instructions it executes, including \textcode{Send}s, but excluding the \textcode{NOp}s used to schedule data hazards and received messages.
A vital goal of merging processes is to avoid overloaded cores (i.e., forming stragglers) by equalizing the execution time of all processes.
The compiler iteratively picks two merge candidates that minimize the increase in merged execution time.
It starts from the process with the shortest execution time and merges it with another process with which it communicates.
This process is chosen to produce the smallest increase in execution time.
Intuitively, by starting from the smallest processes and constructing larger ones, we can balance the execution time of the processes and simultaneously reduce communication (hence avoid network contention).

Merging can continue even after reaching the number of available cores because it can reduce execution time.
For instance, merging processes \textcode{p1} and \textcode{p2} that read a value produced by process \textcode{p3} could lower the execution time of \textcode{p3} because it executes one fewer \textcode{Send} instruction.
Furthermore, since splitting the DAGs may duplicate code, common sub-expression elimination in a merged process could reduce the number of instructions.

After the merge, the compiler assigns the process that contains privileged instructions to the privileged core.
All other processes are mapped to cores using a random assignment.
\secRef{placement} evaluates other alternatives.

\subsection{Custom Function Synthesis}\label{sec:cf_insert}
Manticore's instructions all have the same latency and programs are branch-free, so shorter programs are faster than longer ones.
Custom function synthesis is the process of collapsing long chains of bitwise logic operations common in RTL simulation into a shallow sequence of 4-input custom functions.
This process is conducted on each partitioned process independently.
Instruction fusion borrows ideas from classical minimum-area, bit-level logic synthesis and applies them to word-level programs.

We start from a process' dependence graph and prune all non-logic vertices.
This leaves us with a set of connected components, each containing only logic operations.
We exhaustively extract all 4-input \emph{maximum fanout-free cones} (MFFC) from each component using cut enumeration~\cite{cong_cut_1999}.
An MFFC is a tree rooted at a terminal instruction such that no intermediate result is used by an instruction outside the cone.
Multiple MFFCs can represent the same function and differ only in their representation.
We use logic equivalence checking to group all MFFCs by the function they compute.

Finally we use a mixed-integer linear programming (MILP) formulation to maximize instruction savings by selecting the best set of non-overlapping MFFCs, while considering that some MFFCs are used at multiple places and yield more savings.
Each MFFC is then replaced with a single custom function.
The MFFCs' truth tables are used to configure each core's CFU at boot time.

\subsection{Scheduling, Routing, and Register Allocation}\label{sec:scheduling}

The compiler uses a simple list scheduling algorithm to schedule data hazards.
It performs an abstract cycle-accurate simulation of one \vcycle with a model of a core's pipeline and the NoC.
An instruction is scheduled when its predecessors (in the DAG) are scheduled and executed.
Additionally, a \textcode{Send} instruction can be issued only when it will not collide with any other messages on its path.
If we cannot issue an instruction in a scheduling step, the compiler delays it with a \textcode{NOp} instruction.

A simple linear-scan register allocator works well with practically no spills because of the large register file.

Furthermore, we optimize redundant register moves by allocating the same machine register to both the current and next values of an RTL register (e.g., in \figRef{parsim}, \textcode{+} and \textcode{-} values use the same machine register when possible)~\cite{Wimmer:2010}.

\section{Limitations and Future Work}\label{sec:discussion}

Our current prototype has $\approx$ 7~MiB of instruction memory (our FPGA is memory-limited), which may limit simulation capacity.
ASICs can easily provision tens of MiBs of SRAM~\cite{darwin}, greatly increasing simulation capacity.
However, if a single device's total on-chip memory cannot accomodate the working set, then the work must be partitioned across multiple Manticore grids (e.g., in a rack).
Manticore's reliance on static scheduling does not limit its implementation to a single FPGA, as it is possible to maintain determinism in a distributed system~\cite{groq_maintaining_determinism}.

Manticore currently supports only one privileged core.
This is an important limitation since all memories that do not fit in scratchpads are pinned to the privileged core, which can easily become a bottleneck.
Our choice of a single privileged core was due to the ill-placed DRAM banks in our FPGA.
A privileged core must be connected to a DRAM bank and cache, but the four DRAM banks in our FPGA are not adjacent.
This makes floorplanning to achieve a high frequency very challenging and we decided to limit ourselves to Manticore's single-bank performance for now.
ASIC implementations would not have this floorplanning issue.

Manticore's compiler currently supports only single-clock designs, but this is not a limitation of static BSP.
In fact, multiple \emph{synchronous} clocks can be simulated with static BSP as they have a \emph{fixed} phase relation.
Verilator can also handle such designs.
In contrast, \emph{asynchronous} clocks do not have a fixed phase relation and are out of the scope of full-cycle simulation\footnote{\cite{vlt_async_clocks} subverts Verilator's static schedule with timestamped clocks to simulate multiple asynchronous clock domains.}.
Manticore's strict static execution model disallows asynchronous clocks entirely.

Waveform debugging is an essential tool in a digital designer's arsenal.
It is possible to collect waveforms by using global stores, but this would result in excessive overhead.
We have an initial design of hardware support for out-of-band waveform collection, but we leave its evaluation for future work.

\section{Related Work}\label{sec:related_work}

\subsection{FPGA Prototypes and Emulation Platforms}

\emph{FPGA prototypes} achieve interactive simulation speeds by mapping RTL circuits to \emph{gates} on an FPGA.
Prototypes can run full software stacks for trillions of clock cycles but require significant engineering effort and lack visibility.
FireSim~\cite{FireSim} is an open-source FPGA prototyping platform, widely used as an \emph{architectural} simulator for exploring RISC-V designs at datacenter-scale using cloud FPGAs.
\emph{Emulation platforms} are RTL simulators for very large designs~\cite{designing_a_modern_hardware_emulation_platform}.
They provide excellent visibility into hardware state by mapping RTL circuits to \emph{instructions} that run on a processor grid.
Interconnecting multiple custom processor grids (in a rack) generally greatly increases simulation capacity.
However, commercial emulation platforms cost millions of dollars~\cite{emu_compare}.

Although Manticore is implemented on an FPGA, its simulation runs in software (a program running on Manticore) rather than being mapped to an FPGA.
Consequently, Manticore's compile times are a few minutes, whereas FPGA prototypes take hours to days to compile.
Manticore is a first step towards an open-source alternative to commercial emulation platforms.

\subsection{Parallel RTL simulation}

There is considerable research on accelerating RTL simulation using parallelism, especially GPUs.
Much of this work demonstrates significant speedups relative to commercial \emph{event-driven} simulators.
By contrast, Manticore is a \emph{full-cycle} simulator, so it is not comparable to these systems.
Most of this work focused on reducing the runtime overhead of monitoring value changes, for example, GCS~\cite{Chatterjee:2009, GCS, GCS:journal} or Qian and Deng~\cite{Qian:2011}.
They improved simulation rates by orders of magnitude, to $\approx$ 5--37~kHz, over single-threaded commercial simulators.
Since Manticore is full-cycle, it immediately offers simulation rates above 150~kHz (see \figRef{manticore_scaling}).

RTFlow~\cite{RTLFlow} is a GPU-accelerated RTL simulator that exploits stimulus-level parallelism to speed up simulation by running many independent simulations on a GPU.
RTLFlow improves execution speed by up to 40$\times$ over Verilator for many stimuli, but it runs an order magnitude slower than Verilator with a single stimulus.
Manticore is faster than Verilator with a single stimulus.

Zhang~\cite{zhang2020opportunities} called for a renewal in GPU-accelerated RTL simulation research by leveraging recent advances in GPU-compute APIs designed for machine learning.

\subsection{Sequential RTL Simulation}

Most efforts in improving RTL simulation on CPUs focused on reducing the runtime overhead of event-driven simulation.
ESSENT~\cite{essent_dac,essent_iccad} is a cycle-accurate simulator that employs a coarsened, conditional, singular, static (CCSS) execution model~\cite{essent_dac}.
CCSS is a novel, hybrid approach that minimizes the overhead of runtime checks in event-driven simulation, especially in the presence of low activity factors.
ESSENT is single-threaded and accelerates simulation of RISC-V cores (CPUs have low activity factors) by 1.5--11.5$\times$ over Verilator.
However, it is not clear how ESSENT performs with spatial designs that exhibit high activity factors, especially since it is single threaded~\cite{essent_micro}.
Manticore's performance is independent of a design's activity factor.

Cuttlesim~\cite{Cuttlesim} is a cycle-accurate simulator for Kôika~\cite{Koika}, a rule-based HDL derived from Bluespec Verilog~\cite{Bluespec}.
Cuttlesim uses the high-level semantics of Kôika to generate C++ code optimized for sequential performance.
It reports 2--3$\times$ faster simulation than the equivalent RTL code running Verilator.

\subsection{Deterministic Acceleration}

Manticore's design philosophy is similar to VLIW processors and other Raw machines~\cite{waingold_baring_1997}.
A more recent example is Groq's ML accelerator~\cite{groq_maintaining_determinism, groq_think_fast}.
The Groq chip has deterministic hardware datapaths that enable precise reasoning and control by software.
Like RTL simulation, machine learning exhibits rare long-lived divergent code paths, which makes static scheduling feasible.

\section{The Static BSP Execution Model}
\label{sec:static_bsp}

This section proposes our \emph{Static BSP} execution model.
Static BSP is a low-overhead execution model for parallel RTL simulation.
It is inspired by Valiant's bulk-synchronous parallel (BSP) execution model~\cite{valiant_bridging_1990}.
\figRef{isa_overview} outlines the components of static BSP.
Like the original BSP model, ours consists of a system of networked processors that alternate between phases of local computation and cross-processor communication.

\begin{figure}[b]
  \includegraphics[width=\linewidth]{figures/bsp.pdf}
  \caption{
    The static BSP execution model.
    Each core performs a local computation and then sends its result to the cores that need it for the next computation phase.
    Cores wait (with compiler-inserted \textcode{NOp}s) until all communication completes before starting new computation.
  }
  \label{fig:isa_overview}
\end{figure}

\subsection{Runtime Synchronization Freedom}

The original BSP model relied on a \emph{runtime barrier} to synchronize at the end of communication (before processors start a new computation phase).
Static BSP eliminates this runtime barrier with a \emph{compile-time schedule}.
Static BSP requires hardware to expose a \emph{deterministic} interface so that a compiler can schedule computation and communication.
The compiler replaces runtime barriers with delay operations (e.g., \textcode{sleep} in \figRef{isa_overview}) that ensure all processes start the next phase at the same time.

\subsection{Applying Static BSP to RTL Simulation}
\label{sec:static_bsp_rtl}

To parallelize RTL simulation, we partition the RTL netlist DAG (the bottom of \figRef{parsim}) into multiple independent graphs by creating a DAG per sink node.
The computation in each graph consumes multiple \emph{current} register values and produces exactly one value in a \emph{next} register.
The DAGs are independent and so can be evaluated in parallel.
Once all DAGs are simulated, the computed \emph{next} values become the input to the DAGs that consume them, and a new simulation cycle starts.
However, in practice computation and communication always overlap.

RTL simulation can be statically analyzed and scheduled because RTL code rarely has long-lived divergent code paths.
This enables a conservative, yet efficient schedule of divergent code paths while maintaining determinism.

In the context of RTL simulation, we call a complete iteration of the computation \emph{and} communication phases a \emph{virtual cycle} (\textbf{\vcycle}).
We do so to distinguish between \emph{RTL cycles} (\vcycle) and the \emph{clock cycles} of the processor that is running the simulation.

\section{Background}\label{sec:background}

RTL simulation is performed at two granularities: \emph{timing-accurate}, or \emph{cycle-accurate}.
Timing-accurate simulation timestamps value changes to model gate delays accurately.
By contrast, cycle-accurate simulation captures value changes only at clock edges.
Early in the design process, when logic delays are unknown, cycle-accurate and timing-accurate simulation are equivalent.

Cycle-accurate simulators are implemented in two ways: \emph{event-driven}, or \emph{full-cycle}.
An event-driven simulator observes signal values and \emph{dynamically} schedules operations, which avoids needless re-evaluation of unchanging circuit elements.
By contrast, full-cycle simulators use a single compile-time schedule to ensure values are computed in the correct order.

This work focuses on full-cycle, cycle-accurate simulation.
Full-cycle is generally faster than event-driven simulation despite the unnecessary work since the cost of monitoring and scheduling events can outweigh the benefit of supressing unnecessary execution~\cite{essent_dac}.

\begin{figure}
    \centering
    \includegraphics[width=0.9\linewidth]{figures/parsim_example.pdf}
    \caption{
        An example single-clock netlist (top) and its DAG representation (bottom).
        Circles represent gates and rectangles represent registers.
    }
    \label{fig:parsim}
\end{figure}

\subsection{Verilator RTL simulator}

This section describes Verilator~\cite{snyder_verilator_2020}, our baseline software RTL simulator.
Verilator is a popular open-source, full-cycle simulator widely used by academia and industry.
It is believed to be faster than commercial and other open-source simulators~\cite{snyder_verilator_2020}.
It performs full-cycle simulation by generating a C++ simulation model.
Verilator produces C++ code from an abstract syntax tree (AST) of inlined and optimized RTL code.
The generated C++ is highly optimized; Verilator maximizes performance with branch prediction hints, short-circuitable branch conditions, and memory prefetches.

Hardware description languages model circuits in the form of a \emph{netlist}.
A netlist is a directed graph whose nodes are circuit cells (gates, registers, and memory banks) and whose edges are the wires connecting them.
A netlist graph can be made acyclic by splitting the state nodes (e.g., registers) into a \emph{next} and \emph{current} value.
For example, the top part of \figRef{parsim} contains a netlist in which circles represent gates and rectangles represent registers.
The corresponding directed acyclic graph (DAG) is at the bottom where the \emph{next} and \emph{current} values are denoted by \textcode{+} and \textcode{-}, respectively.

Simulating RTL executes the netlist DAG while respecting precedence relations.
A simulated cycle concludes when all \emph{next} register values are computed using the \emph{current} register values.
The \emph{current} values are then updated from the newly computed ones, and the process repeats.
The DAG, moreover, fully expresses the inherent parallelism of an RTL circuit as an interpreter can simulate independent paths through the graph in parallel.

Verilator uses such a DAG to parallelize RTL simulation.
To do so, Verilator partitions its DAG into \emph{macro-tasks}, the atomic units of work that run asynchronously.
It then combines these tasks into larger units appropriate for multicore parallelism.
Initially, each DAG node comprises a macro-task.
Verilator increases the granularity of computation by combining smaller macro-tasks that share an edge into a single task using Sarkar's algorithm~\cite{Sarkar:87}.
Doing so eliminates the communication of values along the edge, but can increase the critical path of the macro-task graph since the nodes in a macro-task execute sequentially.
Verilator repeatedly merges the macro-task that produces the smallest increase in the critical path.
It does so until it reaches a heuristic threshold for the critical path.
Verilator then statically assigns macro-tasks to a pool of threads.
At runtime, a macro-task can start its execution when its preceding macro-tasks finish.
Atomic fetch-and-add operations (i.e., user-space spin-locks) synchronize the macro-tasks.

\subsection{Parallel Simulation Performance}

Despite its sophisticated optimization, Verilator is often unsuccessful at exploiting multicore parallelism.
\figRef{verilator_threads} illustrates the mismatch between RTL simulation and modern computers.
It reports the parallel performance of nine RTL workloads (described in \secRef{evaluation}) on Verilator.
The experiment ran on a Xeon E5-2680~v3 processor with 12 physical cores.
Two of the benchmarks experience an insignificant 2$\times$ speedup, while others' performance degrade sharply (up to 100$\times$ slowdown).

\begin{figure}[t]
    \includegraphics[width=\linewidth]{figures/verilator_threads.pdf}
    \caption{
        Verilator's multi-threaded performance normalized to single-thread execution (log-scale).
    }
    \label{fig:verilator_threads}
\end{figure}

\begin{figure}[t]
    \includegraphics[width=\linewidth]{figures/verilator_dyn_instr_single.pdf}
    \caption{
        Verilator's pipeline behavior (\textcode{vta}).
        Empty pipeline slots are broken down into the ones caused by I-cache misses (frontend), data hazards (core), and data memory stalls.
        The left vertical axis shows the percentage of empty pipeline slots.
        The right vertical axis shows instruction count normalized to single-thread execution.
    }
    \label{fig:verilator_dyn_instr_single}
\end{figure}

We profiled the workloads to understand this performance degradation.
A few benchmarks are initially processor I-cache bound (e.g., \textcode{vta} in \figRef{verilator_dyn_instr_single}).
These are the only ones to achieve a modest speedup with more CPU threads.
By partitioning work across threads, each core executes less code, increasing instruction locality and reducing I-cache misses.
However, as the number of CPU threads increases, data memory stalls rise sharply, accounting for about 70\% of all empty CPU pipeline slots.
Additionally, the CPU's dynamic instruction count increases on all benchmarks by a factor of 3--100$\times$.
The increased instruction counts reflect the instructions executed by spin-loop synchronization, which grows with the number of cores because of increased lock contention.
The cost of frequent synchronization quickly overshadows the performance gains from parallel execution or improved cache locality (see \figRef{verilator_dyn_instr} in the Appendix).

For the similar reasons to why full-cycle outperforms event-driven simulation, we propose to improve the performance of RTL simulation using \emph{compile-time synchronization} to eliminate runtime overhead.
Doing so requires a co-designed architecture to handle the fine-grain computation and communication.
This work presents a compiler-synchronized execution model for RTL simulation and our hardware architecture that implements it.

\section{Evaluation}\label{sec:evaluation}

\begin{figure*}[th]
  \centering
  \includegraphics[width=\linewidth]{figures/speedup.pdf}
  \caption{
    Manticore's and Verilator's speedup normalized against Verilator's single-thread performance (log\textsubscript{2} scale).
    Verilator is multithreaded but achieves a speedup over its single-thread execution only for the \textcode{mc} and \textcode{vta} benchmarks.
    The numbers above the Verilator bars are the measured average CPU frequency during simulation.
    The peak speedup is 27.9$\times$ with a geometric mean speedup of 5.3$\times$ for a 15$\times$15 grid.
  }
  \label{fig:manticore_speedup}
\end{figure*}

\subsection{Test Environment}
We run Verilator 4.222 with an Intel Xeon E5-2680 v3 on Ubuntu 20.04.
FPGA results are from the Alveo U200\footnote{Static shell platform \textcode{xilinx\_u200\_gen3x16\_xdma\_2\_202110\_1}} datacenter FPGA using Vivado 2022.1 and XRT 2.13.466.

\subsection{FPGA Prototype}

We first evaluate the physical design of Manticore's FPGA implementation.
\tabRef{freq} reports the achieved frequency for various Manticore grids.
The smaller grids can operate at \emph{very} high speeds (close to 500MHz).
There is abrupt degradation at the 12$\times$12 grid, which is explainable by the FPGA's physical layout.
The U200's rectangular floorplan is divided into (1)~a static shell connected to the PCIe bus and (2)~a  user logic region.
The vendor placed the shell at the center-right side of the chip, and it is immovable.
User logic consequently has a C-shaped floorplan (Appendix \secRef{floorplanning_appendix} contains die-shots).
With fewer than 160 cores, Manticore fits at the top of the chip, undisturbed by the shell.
Additional cores spread around the shell, which makes timing closure difficult.
We guide the place and route tool through floorplanning of designs with more than 160 cores.
This significantly improves quality of results.
Details are described in the Appendix (\secRef{floorplanning_appendix}).

\begin{table}[h]
  \centering
  \resizebox{0.9\columnwidth}{!}{%
    \begin{tabular}{ c c c c c c c }
      \toprule
      \textbf{Grid}   & \textbf{8$\times$8} & \textbf{10$\times$10} & \textbf{12$\times$12} & \textbf{15$\times$15} & \textbf{16$\times$16} \\
      \midrule
      \textbf{Auto}   & 500                 & 485                   & 480                   & 395                   & 180                   \\
      \textbf{Guided} & --                  & --                    & 500                   & 475                   & 450                   \\
      \bottomrule
    \end{tabular}
  }
  \caption{Achieved clock frequency (MHz) on U200 using automatic and guided floorplanning.}
  \label{tab:freq}
\end{table}

Each core uses less than 0.021\% of the U200's resources.
Available URAMs limit the number of cores to 398\footnote{Out of 800 available URAMs, 4 are allocated to the cache.}~\cite{ug1120} (\tabRef{utilization} in the Appendix contains details).

\subsection{Benchmarks}

We evaluate Manticore's performance with nine RTL workloads (we wrapped these benchmarks in simple, assertion-based Verilog test drivers):

\begin{itemize}
  \item \textbf{bc} is a bitcoin miner~\cite{bitcoin}.
  \item \textbf{mm} is a 16$\times$16 integer matrix-matrix multiplier.

  \item \textbf{cgra} is a latency-insensitive, coarse-grained reconfigurable array of 64 floating-point processing elements.

  \item \textbf{vta} is a ML accelerator~\cite{vta}.
        We use a larger\footnote{\textcode{blockIn=64} and \textcode{blockOut=64} instead of 16.} spatial implementation as the default configuration is too small to benefit from hardware acceleration.
        We divide buffer sizes by 4, so they fit in Manticore's scratchpads.
  \item \textbf{rv32r} consists of 16 in-order pipelined RISC-V processors~\cite{riscv-mini} communicating over a ring network.

  \item \textbf{jpeg} is a pipelined JPEG decoder~\cite{jpeg}.
  \item \textbf{blur} is a stencil computation accelerator~\cite{stencil:2014}.
  \item \textbf{mc} is a Monte-Carlo simulation stock option price evolution predictor with fixed-point arithmetic~\cite{monte-carlo}.

  \item \textbf{noc} is a 2D 4$\times$4 uni-directional torus network-on-chip with wormhole routing and four virtual channels.
\end{itemize}
The state in all benchmarks is fully contained in on-chip scratchpads, so the compiler can accurately predict performance.
We evaluate global stalls separately (\secRef{eval_stall}).

\subsection{End-to-End Performance}

\figRef{manticore_speedup} compares Manticore and Verilator's best performance normalized to Verilator's single-thread performance.
We disable waveform dumps and unnecessary printing to get undiluted performance metrics.
Furthermore, we exclude initialization overhead to reflect \emph{steady state} performance of long-running simulations.
Initialization typically takes $<1$s but requires multiple transitions between the host and the FPGA (see \secRef{runtime_appendix} for details).

Despite running at a fraction of the Xeon's clock speed, Manticore outperforms single-thread Verilator, by a factor of up to 27.9$\times$, for all workloads except \textcode{jpeg}.
The low performance of \textcode{jpeg} results from two factors.
First, \textcode{jpeg} is substantially smaller than other benchmarks (\tabRef{compile_time} in the Appendix) and does not contain enough parallelism.
The compiler can improve its single-core performance by only $\approx$17\% through parallelism as it contains unbalanced code paths.
Second, there is a significant clock frequency and IPC difference between Manticore and Xeon.
With only a handful of cores running at $\approx$500~MHz and a resulting \emph{aggregate} IPC of 1.17, Manticore cannot compete with the Xeon's $\approx$3.3~GHz multiple-issue pipeline that executes instructions at an average IPC of 2.25.

In summary, without sufficient parallelism, Manticore's low-frequency processors cannot match the performance of a Xeon processor.
On the other hand, the other measurements demonstrate that with enough parallelism, Manticore makes up for its lower single-thread performance and considerably outperforms Verilator.
Moreover, Manticore does better with large designs as Verilator's IPC generally drops as design size increases, whereas Manticore's \emph{aggregate} IPC increases.

\subsection{Scaling to 100s of Cores}

With task-parallel workloads such as RTL, it is not immediately clear how performance might improve as the number of cores increases.
\figRef{manticore_scaling} offers some insight.
The virtual critical-path length (\emph{VCPL}) is the total number of instructions (including \textcode{NOps}) in the slowest core (i.e., the straggler).
In the absence of dynamic behavior (off-chip DRAM accesses), the VCPL is proportional to execution time (or inverse of simulation rate).

Scaling stagnates at 225 (15$\times$15) cores for almost all benchmarks.
Larger grids yield little benefit for the benchmarks.
Increased performance might result from better compilation techniques or increased single-core performance (e.g., increasing clock speed with an ASIC implementation).

\begin{figure}
  \centering
  \includegraphics[width=\linewidth]{figures/scaling.pdf}
  \caption{
    Manticore's VCPL scaling (lower is better).
    Scaling past 225 cores yields diminishing returns.

  }
  \label{fig:manticore_scaling}
\end{figure}

\subsection{Compiler Techniques}\label{sec:compiler_evaluation}

The rest of the evaluation focuses on compilation techniques.

\subsubsection{Communication-Aware Partitioning}

The balanced partitioning algorithm (B) described in \secRef{parallelization} merges the split processes while keeping communication costs low.
As a baseline, we compare it against a communication-oblivious, longest processing-time first partitioning algorithm (L) to observe the benefits of modeling communication.
Both algorithms are heuristic and use the same cost estimation method, but differ in their merge strategy.
Furthermore, both algorithms are oblivious to the effects of instruction scheduling (which occurs after partitioning) as neither counts the \textcode{NOp}s inserted for data hazards and NoC contention.

\figRef{manticore_parallel} compares the two approaches for a 15$\times$15 Manticore grid, with VPCL normalized to that of L.
We subdivided the VCPL into the fraction of cycles spent on computing (\textcode{compute}), sending messages (\textcode{send}), or doing nothing (\textcode{NOp}) in the straggler.
The numbers above each bar denote the number of cores used.
Modeling communication is essential.
B significantly reduces the total number of \textcode{Send}s (see \tabRef{sends}), reduces the number of \textcode{NOp}s in the straggler, and generally outperforms (except for \textcode{vta}) the communication-oblivious algorithm (L) despite using fewer cores.
As an example of the critical role of the partitioning algorithm, note that B reduces the VCPL by more than 50\% in \textcode{bc}. Without B, the speedup in \figRef{manticore_speedup} would have been 60\% instead of 325\%.

\begin{table}[!h]
  \centering
  \setlength{\tabcolsep}{2pt}
  \resizebox{\columnwidth}{!}{%
    \begin{tabular}{ c c c c c c c c c c }
      \toprule
      {$\times$1000} & \textbf{mm} & \textbf{mc} & \textbf{vta} & \textbf{noc} & \textbf{cgra} & \textbf{rv32r} & \textbf{bc} & \textbf{blur} & \textbf{jpeg} \\
      \midrule
      \textbf{{L}}   & 23.3        & 23.6        & 13.6         & 25.6         & 18.9          & 16.9           & 7.7         & 5.0           & 1.0           \\
      \textbf{{B}}   & 8.5         & 3.9         & 9.8          & 16.6         & 7.4           & 2.8            & 3.1         & 2.7           & 0.1           \\
      \%             & -63.6       & -83.5       & -28.0        & -35.3        & -60.6         & -83.3          & -59.5       & -47.1         & -94.1         \\
      \bottomrule
    \end{tabular}
  }
  \caption{
    Total \textcode{Send} instructions ($\times$1000) produced by \emph{L} and \emph{B}.
    \emph{B} consistently reduces communication.
  }
  \label{tab:sends}
\end{table}

\begin{figure}[!h]
  \centering
  \includegraphics[width=\linewidth]{figures/parallel.pdf}
  \caption{
    Comparison of the communication-oblivious, longest processing-time first algorithm (\emph{L}) and the communication-aware algorithm from \secRef{parallelization} (\emph{B}) in the straggler on a 15$\times$15 grid.
    VCPL is normalized to the VCPL of L. The numbers above each bar show the total number of cores used.
  }
  \label{fig:manticore_parallel}
\end{figure}

\subsubsection{Process-to-Core Placement}\label{sec:placement}

Communication latency can be further reduced by assigning communicating processes to nearby cores on the torus NoC.
We tried to find an optimal process-to-core assignment using a MILP formulation with objective functions such as minimizing the maximum or total link utilization.
However, the problem became intractable with a grid size larger than 4$\times$4, even with commercial solvers.
Because of the uni-directional design of the torus, exchanging any two processes' core assignments changes the cost of \emph{all} communication links.
This forces the solver to enumerate all $16!$ possible assignments for a 4$\times$4 grid, which makes the solution intractable.

Alternatively, we used a tractable heuristic: recursively bi-partitioning the set of processes to minimize inter-partition communication.
Counterintuitively, the bi-partitioning solutions were not systematically better than random placement.
We analyzed this unexpected behavior and realized that most cores within the 90\textsuperscript{th} percentile of the straggler's \vcycle are compute-bound.
Consequently, changes to process-to-core mapping could produce less than 10\% performance improvement since they affect only communication-bound cores

\subsubsection{Custom Instructions}

We initially formulated custom instructions to \emph{cheaply} compensate for the lack of instruction-level parallelism (due to our single-issue pipeline) by exploiting bit-level parallelism seemingly abundant in RTL.
\figRef{manticore_cf} shows the VCPL of each benchmark normalized to the VCPL without custom instructions.
The VCPL is broken down into custom instructions, \textcode{NOps}, and other types of instructions.
The numbers above each bar show the reduction in total number of instructions over \emph{all} cores (excluding \textcode{NOps}).
This reduction is 2.9--17.8\%, yet the VCPL (end-to-end) reduction is less than 10\% in all benchmarks.
Custom instructions reduce the \emph{total} instruction count, but may not benefit the straggler (e.g., in \textcode{jpeg}).
Eliminating the CFU from hardware would save one BRAM and a few tens of LUTs.
However, this would not allow larger Manticore grids since the URAMs are the limiting resource.

\begin{figure}
  \centering
  \includegraphics[width=\linewidth]{figures/cf.pdf}
  \caption{
    Savings in \vcycle due to custom instructions.
    The \vcycle is broken down into three instruction types and normalized to not using any custom functions.
    The numbers above each bar represent the reduction in non-\textcode{NOp} instructions over all cores.
  }
  \label{fig:manticore_cf}
\end{figure}

\begin{figure}
  \centering
  \includegraphics[width=\linewidth]{figures/cache.pdf}
  \caption{
    The total number of cycles (lower is better) spent simulating a FIFO (left) and a RAM (right).

    Numbers are normalized to the cycles needed to run the 1~KiB design.
    The numbers inside other bars denote the cache hit rate.
  }
  \label{fig:manticore_cache}
\end{figure}

\subsubsection{Compile Time}

The prototype compiler is built in Scala for robustness and compile times are in the order of minutes (max. 17m).
This offers software development-like turnaround times for hours-long simulations.
Most of the compilation time is spent in parallelization.
A detailed discussion and breakdown is presented in \secRef{compile_time_appendix}.

\subsection{Global Stall}\label{sec:eval_stall}
We evaluate the impact of going off-chip with two RTL microbenchmarks running on a 1$\times$1 Manticore grid at 500~MHz: (1)~a FIFO, and (2)~a RAM.
The evaluated FIFO and RAM are 1~KiB, 64~KiB, and 512~KiB.
The FIFO sequentially reads/writes its memory, whereas the RAM accesses its memory with pseudo-random addresses (using a simple XOR-shift-128 generator).
Each program runs for 16Mi \vcycles performing one load and one store operation per \vcycle.
We use hardware performance counters to log the total number of cycles, stalled cycles, cache hits, and cache misses.
For each microbenchmark, the 1~KiB configuration serves as a baseline since this memory fits in the scratchpad, and there are no global stalls.
The 64~KiB represents a middle point in which the state does not fit in the scratchpad but is fully contained within the 128~KiB cache.
Lastly, the 512~KiB configuration corresponds to the scenario in which the state is spread between the on-chip cache and off-chip DRAM.
\figRef{manticore_cache} demonstrates that large FIFOs have a high hit rate and are not stall-limited (i.e., FIFOs have excellent cache locality).
By contrast, large RAMs suffer as the number of off-chip accesses increases, which is the case in this experiment with completely random accesses.
Finally, we observe that cache accesses come at a cost even if they hit since we conservatively stall the execution on every such access.

\section{Appendix}\label{sec:appendix}

This appendix contains supplementary material that elaborates on points raised in the body of this paper.

\subsection{Verilator's Performance}\label{sec:verilator_appendix}

We profiled nine benchmarks with Intel's VTune profiler to study Verilator's performance.
We measured the fraction of empty CPU pipeline slots (bubbles) caused by three types of events:
\begin{itemize}
  \item \textbf{front-end} bubbles caused by instruction cache misses,
  \item \textbf{core} bubbles due to software dependencies (i.e., data hazard) or insufficient functional units, and
  \item \textbf{memory} bubbles caused by cache misses.
\end{itemize}

\figRef{verilator_dyn_instr} shows these metrics for each benchmark.
The height of a plot shows the CPU's underutilized pipeline slots on the left axis (lower is better).
The dark line shows the dynamic instruction count normalized to single-thread execution on the right axis (lower is better).
In all benchmarks, as the parallelism increases, the simulation becomes memory-bound and experiences a sharp increase in instruction count.

\subsection{Microarchitecture}

\figRef{manticore_micro} outlines the pipelined implementation of one core.
The pipeline is 14 stages deep and is logically divided into the typical five functions: fetch, decode, execute, memory access, and writeback.
The CFU is implemented as 16 LUTRAMs.

The pipeline's frontend (right side of \figRef{manticore_micro}) is responsible for receiving messages during simulation.
Each message is translated on the fly to a \textcode{SET} instruction and is written into instruction memory.
A \textcode{SET} instruction updates a register with an immediate value.
A state machine controls the execution of the pipeline, which is kept in strict lock-step with all other cores.
The compiler inserts sleep instructions to coordinate communication between cores.
An additional state machine handles incoming messages from the bootloader (see \secRef{bootloader_appendix}) and fills the instruction memory before the simulation starts.

\subsection{Runtime}\label{sec:runtime_appendix}

Manticore's runtime is a program running on the host processor that takes a binary generated by the compiler and runs it on the Manticore hardware accelerator connected to the host.
The runtime copies the program binary into FPGA DRAM, then instructs the hardware bootloader (see \figRef{manticore_array}) to copy the program into the local instruction memories.
While the code executes, the runtime continuously polls the hardware state registers to handle exceptions or terminate execution.

\subsubsection{Bootloader}\label{sec:bootloader_appendix}
Bootloading starts with a soft reset that brings all cores to a \emph{boot state}.
The soft reset only changes a few state registers in each core; it does not reset the register files or the scratchpads.

Cores continuously push \textcode{NOps} through their pipelines and snoop the NoC for instructions when in the boot state.
A hardware bootloader (see \figRef{manticore_array}) module reads the program binary from DRAM and streams the instructions to each core in sequence.
Cores store the incoming instructions in their instruction memory.
The cores then wait for a message from the NoC that contains a core-specific countdown value.
At that point, the cores initialize a local timer with their specific countdown and start execution when the timer counts down to 0.
The countdown starts all cores simultaneously despite the non-deterministic time required to read a program binary from DRAM.

\figRef{manticore_micro} shows the instruction stream format that a core receives.
This stream consists of a header that encodes the number of instructions in a program and a footer comprised of three words:
\begin{enumerate}
  \item \verb+EPILOGUE_LENGTH+ denotes the total number of messages the core expects to receive at every \vcycle.
  \item \verb+SLEEP_LENGTH+ denotes the sleep period length (see \textcode{sleep} in \figRef{isa_overview}).
  \item \verb+COUNT_DOWN+ is the last word received that initiates a countdown to the start.
\end{enumerate}

\begin{figure}
  \centering
  \includegraphics[width=\linewidth]{figures/compile_time.pdf}
  \caption{
    Breakdown of compilation time:
    Yosys (\textcode{yss}), assembly parsing (\textcode{prs}), basic optimizations (\textcode{opt}), parallelization (\textcode{prl}), custom function extraction (\textcode{cf}), scheduling (\textcode{sch}), others (\textcode{otr}).
  }
  \label{fig:compile_time}
\end{figure}

\subsubsection{Exceptions}

Manticore's hardware design and execution model make it possible to pause the execution, perform some computation on the host, and resume the execution on the FPGA.
An example can illustrate this.
Consider the following Verilog statement:

\verb+if (count != 0) $display("got

\noindent This statement is executed as a global store instruction predicated by the condition \verb+count != 0+ that stores \verb+count+ to the global memory.
The \verb+$display+ system call is translated to an \textcode{EXPECT} instruction that throws an exception when \textcode{count} is non-zero.
When Manticore raises the exception, the grid stalls globally, and the host flushes the cache and reads the value of \textcode{count} from the FPGA DDR memory.
The runtime prints this value for the user.
Currently, our compiler only supports basic Verilog system calls.
We plan to support arbitrary DPI (Verilog Direct Programming Interface) calls through this mechanism.
However, crossing the host-device boundary is very expensive and should be avoided as much as possible.

\subsection{Floorplanning}\label{sec:floorplanning_appendix}

The U200 is a large \emph{multi-die} FPGA that contains three SLRs\footnote{Super Logic Regions, Xilinx terminology for a single die.}.
Inter-SLR connections are significantly more costly than intra-SLR ones.
While Vivado can find an efficient floorplan of Manticore's torus structure when the full design fits in a single SLR, it fails to do so when SLR crossings are necessary (see \figRef{floorplan}).

We get around this limitation by using a floorplanning script to guide Vivado.
Cores do not directly access the shell and communicate only with their corresponding switch through a pipelined path.
Therefore, cores do not need to respect a torus topology, so we spread half the cores in the top SLR and the other half in the bottom SLR.
However, the NoC switches must be connected in a torus structure, so we constrain them to the narrow rectangular region in the central SLR.
We constrain Vivado to use a set of dedicated hard registers available for crossing SLRs for each core-to-switch connection.
We also co-locate the privileged core, cache, bootloader, and clock control logic in the central SLR as they access the shell.
Finally, we minimize clock skew between the compute and control clock domains by assigning the clock buffers and clock roots to the same clock region.
These optimizations enable a 15$\times$15 grid to run at 475 MHz.

\subsection{Compile Time Analysis}\label{sec:compile_time_appendix}

\tabRef{compile_time} reports the compilation times of each benchmark for both Manticore and Verilator (single-thread and multi-thread).
Manticore's compiler is written in Scala and runs on the JVM, whereas Verilator is written in C++.
\figRef{compile_time} contains a detailed breakdown of compilation steps and their contribution to the total time.
Most of the compile-time is spent in parallelizing RTL code.
We expect to improve compilation time (it is currently unoptimized).

\begin{table}
  \centering
  \setlength{\tabcolsep}{1.5pt}
  \resizebox{\linewidth}{!}{%
    \begin{tabular}{l c c c c c c c }
      \toprule
      \multirow{2}{*}{\textbf{Bench}} & \multirow{2}{*}{$|E|$} & \multirow{2}{*}{$|V|$} & \multirow{2}{*}{\textbf{\# instr}} & \multirow{2}{*}{\textbf{LoC}} & \multicolumn{3}{c}{\textbf{Compile Time}}                                                \\
      \cmidrule{6-8}
                                      &                        &                        &                                    &                               & \textbf{Manticore}                        & \textbf{Verilator} & \textbf{Verilator -j24} \\
      \midrule
      \textbf{jpeg}                   & 1005                   & 131                    & 2905                               & 6542                          & 17s                                       & 7s                 & 3s                      \\
      \textbf{blur}                   & 9649                   & 751                    & 5975                               & 3869                          & 59s                                       & 22s                & 15s                     \\
      \textbf{bc}                     & 8135                   & 4630                   & 21699                              & 276                           & 2m26s                                     & 40s                & 27s                     \\
      \textbf{mm}                     & 89102                  & 6659                   & 56568                              & 64963                         & 9m42s                                     & 7m5s               & 2m55s                   \\
      \textbf{rv32r}                  & 60430                  & 4497                   & 65488                              & 31761                         & 6m41s                                     & 1m56s              & 29s                     \\
      \textbf{noc}                    & 114364                 & 6927                   & 80718                              & 39363                         & 17m39s                                    & 3m23s              & 36s                     \\
      \textbf{cgra}                   & 57532                  & 4615                   & 82682                              & 104498                        & 8m36s                                     & 2m15s              & 37s                     \\
      \textbf{mc}                     & 52330                  & 9182                   & 102295                             & 30353                         & 13m34s                                    & 1m13s              & 16s                     \\
      \textbf{vta}                    & 56142                  & 7037                   & 114474                             & 190818                        & 15m44s                                    & 2m33               & 26s                     \\
      \bottomrule
    \end{tabular}
  }
  \caption{
    Manticore, single-thread compile Verilator and 24-thread compile Verilator (-j24) compilation times.
    $|E|$ and $|V|$ respectively denote the number of edges and nodes in the graph obtained by splitting each benchmark into a maximal set of independent processes (see \secRef{parallelization}).
    \textbf{\# instr} denotes the number of lower assembly instructions before splitting in the single monolithic process.
    \textbf{LoC} denotes the Verilog/SystemVerilog lines of code for each benchmark.
    The benchmarks are sorted by \textbf{\# instr}.
  }
  \label{tab:compile_time}
\end{table}

\subsection{FPGA resource utilization}\label{sec:utilization_appendix}

\tabRef{utilization} reports FPGA resource utilization for a single core.
The dominant resource is the URAM, as two are required per core (one for the instruction memory and one for the local scratchpad).
This limits the total number of cores on the U200 to 398.
However, as discussed in the evaluation, a 225-element grid is usually the breaking point in scaling (see \figRef{manticore_scaling}).
As all cores may not use their scratchpad memory, one optimization is a heterogeneous implementation where some cores lack a scratchpad and rely on only a large register file so that other cores can have more local memory.
We leave heterogeneous processor grids to future work.

\begin{table}
  \centering
  \resizebox{1\columnwidth}{!}{%
    \begin{tabular}{c c c c c c c c}
      \toprule
      \textbf{}   & \textbf{LUT} & \textbf{LUTRAM} & \textbf{FF} & \textbf{BRAM} & \textbf{URAM} & \textbf{DSP} & \textbf{SRL} \\
      \midrule
      \#          & 545          & 128             & 1358        & 4             & 2             & 1            & 102          \\
      \textbf{\%} & 0.05         & 0.02            & 0.05        & 0.19          & 0.21          & 0.01         & 0.02         \\
      \bottomrule
    \end{tabular}
  }
  \caption{
    Resource utilization of a single core on the U200.
    Percentages are the faction of the total resources available on an U200.
  }
  \label{tab:utilization}
\end{table}

\begin{figure*}
  \includegraphics[height=0.93\textheight, angle=180]{figures/verilator_dyn_instr_90r.pdf}
  \caption{
    Verilator performance on an Intel Xeon E5-2680 v3.
    Breakdown of CPU empty pipeline slots on the left axis and executed instruction (normalized to single-thread) on the right axis.
  }
  \label{fig:verilator_dyn_instr}
\end{figure*}

\begin{figure*}
  \centering
  \includegraphics[height=0.93\textheight]{figures/microarch_90r.pdf}
  \caption{
    Microarchitecture of a core in Manticore's processor grid. Details are omitted for legibility.
  }
  \label{fig:manticore_micro}
\end{figure*}

\begin{figure*}
  \centering
  \includegraphics[height=0.90\textheight]{figures/floorplan_compare.pdf}
  \caption{
    Floorplan of Manticore's physical implementation on U200.
    Vivado's automatic floorplanning is at the top and our guided floorplanning is at the bottom.
    The cores are colored in green, the NoC in red, and the control clock domain in yellow.
    The fixed shell is marked as an orange box in each floorplan.
    The clock speed is considerably higher with the guided floorplans.
  }
  \label{fig:floorplan}
\end{figure*}
\section{Appendix}\label{sec:appendix}

This appendix contains supplementary material that elaborates on points raised in the body of this paper.

\subsection{Verilator's Performance}\label{sec:verilator_appendix}

We profiled nine benchmarks with Intel's VTune profiler to study Verilator's performance.
We measured the fraction of empty CPU pipeline slots (bubbles) caused by three types of events:
\begin{itemize}
  \item \textbf{front-end} bubbles caused by instruction cache misses,
  \item \textbf{core} bubbles due to software dependencies (i.e., data hazard) or insufficient functional units, and
  \item \textbf{memory} bubbles caused by cache misses.
\end{itemize}

\figRef{verilator_dyn_instr} shows these metrics for each benchmark.
The height of a plot shows the CPU's underutilized pipeline slots on the left axis (lower is better).
The dark line shows the dynamic instruction count normalized to single-thread execution on the right axis (lower is better).
In all benchmarks, as the parallelism increases, the simulation becomes memory-bound and experiences a sharp increase in instruction count.

\subsection{Microarchitecture}

\figRef{manticore_micro} outlines the pipelined implementation of one core.
The pipeline is 14 stages deep and is logically divided into the typical five functions: fetch, decode, execute, memory access, and writeback.
The CFU is implemented as 16 LUTRAMs.

The pipeline's frontend (right side of \figRef{manticore_micro}) is responsible for receiving messages during simulation.
Each message is translated on the fly to a \textcode{SET} instruction and is written into instruction memory.
A \textcode{SET} instruction updates a register with an immediate value.
A state machine controls the execution of the pipeline, which is kept in strict lock-step with all other cores.
The compiler inserts sleep instructions to coordinate communication between cores.
An additional state machine handles incoming messages from the bootloader (see \secRef{bootloader_appendix}) and fills the instruction memory before the simulation starts.

\subsection{Runtime}\label{sec:runtime_appendix}

Manticore's runtime is a program running on the host processor that takes a binary generated by the compiler and runs it on the Manticore hardware accelerator connected to the host.
The runtime copies the program binary into FPGA DRAM, then instructs the hardware bootloader (see \figRef{manticore_array}) to copy the program into the local instruction memories.
While the code executes, the runtime continuously polls the hardware state registers to handle exceptions or terminate execution.

\subsubsection{Bootloader}\label{sec:bootloader_appendix}
Bootloading starts with a soft reset that brings all cores to a \emph{boot state}.
The soft reset only changes a few state registers in each core; it does not reset the register files or the scratchpads.

Cores continuously push \textcode{NOps} through their pipelines and snoop the NoC for instructions when in the boot state.
A hardware bootloader (see \figRef{manticore_array}) module reads the program binary from DRAM and streams the instructions to each core in sequence.
Cores store the incoming instructions in their instruction memory.
The cores then wait for a message from the NoC that contains a core-specific countdown value.
At that point, the cores initialize a local timer with their specific countdown and start execution when the timer counts down to 0.
The countdown starts all cores simultaneously despite the non-deterministic time required to read a program binary from DRAM.

\figRef{manticore_micro} shows the instruction stream format that a core receives.
This stream consists of a header that encodes the number of instructions in a program and a footer comprised of three words:
\begin{enumerate}
  \item \verb+EPILOGUE_LENGTH+ denotes the total number of messages the core expects to receive at every \vcycle.
  \item \verb+SLEEP_LENGTH+ denotes the sleep period length (see \textcode{sleep} in \figRef{isa_overview}).
  \item \verb+COUNT_DOWN+ is the last word received that initiates a countdown to the start.
\end{enumerate}

\subsubsection{Exceptions}

Manticore's hardware design and execution model make it possible to pause the execution, perform some computation on the host, and resume the execution on the FPGA.
An example can illustrate this.
Consider the Verilog statement \verb+if (count != 0) $display("got
This statement is executed as a global store instruction predicated by the condition \verb+count != 0+ that stores \verb+count+ to the global memory.
The \verb+$display+ system call is translated to an \textcode{EXPECT} instruction that throws an exception when \textcode{count} is non-zero.
When Manticore raises the exception, the grid stalls globally, and the host flushes the cache and reads the value of \textcode{count} from the FPGA DDR memory.
The runtime prints this value for the user.
Currently, our compiler only supports basic Verilog system calls.
We plan to support arbitrary DPI (Verilog Direct Programming Interface) calls through this mechanism.
However, crossing the host-device boundary is very expensive and should be avoided as much as possible.

\subsection{Floorplanning}\label{sec:floorplanning_appendix}

The U200 is a large \emph{multi-die} FPGA that contains three SLRs\footnote{Super Logic Regions, Xilinx terminology for a single die.}.
Inter-SLR connections are significantly more costly than intra-SLR ones.
While Vivado can find an efficient floorplan of Manticore's torus structure when the full design fits in a single SLR, it fails to do so when SLR crossings are necessary (see \figRef{floorplan}).

We get around this limitation by using a floorplanning script to guide Vivado.
Cores do not directly access the shell and communicate only with their corresponding switch through a pipelined path.
Therefore, cores do not need to respect a torus topology, so we spread half the cores in the top SLR and the other half in the bottom SLR.
However, the NoC switches must be connected in a torus structure, so we constrain them to the narrow rectangular region in the central SLR.
We constrain Vivado to use a set of dedicated hard registers available for crossing SLRs for each core-to-switch connection.
We also co-locate the privileged core, cache, bootloader, and clock control logic in the central SLR as they access the shell.
Finally, we minimize clock skew between the compute and control clock domains by assigning the clock buffers and clock roots to the same clock region.
These optimizations enable a 15$\times$15 grid to run at 475 MHz.

\subsection{Compile Time Analysis}\label{sec:compile_time_appendix}

\tabRef{compile_time} reports the compilation times of each benchmark for both Manticore and Verilator (single-thread and multi-thread).
Manticore's compiler is written in Scala and runs on the JVM, whereas Verilator is written in C++.
\figRef{compile_time} contains a detailed breakdown of compilation steps and their contribution to the total time.
Most of the compile-time is spent in parallelizing RTL code.
We expect to improve compilation time (it is currently unoptimized).

\begin{table}
  \centering
  \setlength{\tabcolsep}{1.5pt}
  \resizebox{\linewidth}{!}{%
    \begin{tabular}{l c c c c c c c }
      \toprule
      \multirow{2}{*}{\textbf{Bench}} & \multirow{2}{*}{$|E|$} & \multirow{2}{*}{$|V|$} & \multirow{2}{*}{\textbf{\# instr}} & \multirow{2}{*}{\textbf{LoC}} & \multicolumn{3}{c}{\textbf{Compile Time}}                                                \\
      \cmidrule{6-8}
                                      &                        &                        &                                    &                               & \textbf{Manticore}                        & \textbf{Verilator} & \textbf{Verilator -j24} \\
      \midrule
      \textbf{jpeg}                   & 1005                   & 131                    & 2905                               & 6542                          & 17s                                       & 7s                 & 3s                      \\
      \textbf{blur}                   & 9649                   & 751                    & 5975                               & 3869                          & 59s                                       & 22s                & 15s                     \\
      \textbf{bc}                     & 8135                   & 4630                   & 21699                              & 276                           & 2m26s                                     & 40s                & 27s                     \\
      \textbf{mm}                     & 89102                  & 6659                   & 56568                              & 64963                         & 9m42s                                     & 7m5s               & 2m55s                   \\
      \textbf{rv32r}                  & 60430                  & 4497                   & 65488                              & 31761                         & 6m41s                                     & 1m56s              & 29s                     \\
      \textbf{noc}                    & 114364                 & 6927                   & 80718                              & 39363                         & 17m39s                                    & 3m23s              & 36s                     \\
      \textbf{cgra}                   & 57532                  & 4615                   & 82682                              & 104498                        & 8m36s                                     & 2m15s              & 37s                     \\
      \textbf{mc}                     & 52330                  & 9182                   & 102295                             & 30353                         & 13m34s                                    & 1m13s              & 16s                     \\
      \textbf{vta}                    & 56142                  & 7037                   & 114474                             & 190818                        & 15m44s                                    & 2m33               & 26s                     \\
      \bottomrule
    \end{tabular}
  }
  \caption{
    Manticore, single-thread compile Verilator and 24-thread compile Verilator (-j24) compilation times.
    $|E|$ and $|V|$ respectively denote the number of edges and nodes in the graph obtained by splitting each benchmark into a maximal set of independent processes (see \secRef{parallelization}).
    \textbf{\# instr} denotes the number of lower assembly instructions before splitting in the single monolithic process.
    \textbf{LoC} denotes the Verilog/SystemVerilog lines of code for each benchmark.
    The benchmarks are sorted by \textbf{\# instr}.
  }
  \label{tab:compile_time}
\end{table}

\subsection{FPGA resource utilization}\label{sec:utilization_appendix}

\tabRef{utilization} reports FPGA resource utilization for a single core.
The dominant resource is the URAM, as two are required per core (one for the instruction memory and one for the local scratchpad).
This limits the total number of cores on the U200 to 398.
However, as discussed in the evaluation, a 225-element grid is usually the breaking point in scaling (see \figRef{manticore_scaling}).
As all cores may not use their scratchpad memory, one optimization is a heterogeneous implementation where some cores lack a scratchpad and rely on only a large register file so that other cores can have more local memory.
We leave heterogeneous processor grids to future work.

\begin{figure}
  \centering
  \includegraphics[width=\linewidth]{figures/compile_time.pdf}
  \caption{
    Breakdown of compilation time:
    Yosys (\textcode{yss}), assembly parsing (\textcode{prs}), basic optimizations (\textcode{opt}), parallelization (\textcode{prl}), custom function extraction (\textcode{cf}), scheduling (\textcode{sch}), others (\textcode{otr}).
  }
  \label{fig:compile_time}
\end{figure}

\begin{table}
  \centering
  \resizebox{1\columnwidth}{!}{%
    \begin{tabular}{c c c c c c c c}
      \toprule
      \textbf{}   & \textbf{LUT} & \textbf{LUTRAM} & \textbf{FF} & \textbf{BRAM} & \textbf{URAM} & \textbf{DSP} & \textbf{SRL} \\
      \midrule
      \#          & 545          & 128             & 1358        & 4             & 2             & 1            & 102          \\
      \textbf{\%} & 0.05         & 0.02            & 0.05        & 0.19          & 0.21          & 0.01         & 0.02         \\
      \bottomrule
    \end{tabular}
  }
  \caption{
    Resource utilization of a single core on the U200.
    Percentages are the faction of the total resources available on an U200.
  }
  \label{tab:utilization}
\end{table}

\begin{sidewaysfigure*}
  \includegraphics[width=\linewidth,angle=0]{figures/verilator_dyn_instr.pdf}
  \caption{
    Verilator performance on an Intel Xeon E5-2680 v3.
    Breakdown of CPU empty pipeline slots on the left axis and executed instruction (normalized to single-thread) on the right axis.
  }
  \label{fig:verilator_dyn_instr}
\end{sidewaysfigure*}

\begin{sidewaysfigure*}
  \includegraphics[width=\linewidth]{figures/microarch.pdf}
  \caption{
    Microarchitecture of a core in Manticore's processor grid. Details are omitted for legibility.
  }
  \label{fig:manticore_micro}
\end{sidewaysfigure*}

\begin{figure*}
  \centering
  \includegraphics{figures/floorplan_compare.pdf}
  \caption{
    Floorplan of Manticore's physical implementation on U200.
    Vivado's automatic floorplanning is at the top and our guided floorplanning is at the bottom.
    The cores are colored in green, the NoC in red, and the control clock domain in yellow.
    The fixed shell is marked as an orange box in each floorplan.
    The clock speed is considerably higher with the guided floorplans.
  }
  \label{fig:floorplan}
\end{figure*}
\section{Manticore Architecture}\label{sec:design}

We now describe Manticore, an architecture whose fully-deterministic runtime behavior satisfies static BSP's requirements.

\subsection{Key Ideas}

We now list Manticore's most salient features which permit deterministic behavior.
\begin{itemize}
  \item Manticore consists of multiple simple cores that communicate over a statically-scheduled network-on-chip (\emph{NoC}) (\figRef{manticore_array}).
  \item Cores communicate through \emph{message passing} since shared memory's dynamic performance and communication make static scheduling difficult.
  \item A compiler controls how messages are scheduled and routed between cores to ensure deterministic delivery.
  \item Instructions are \emph{statically partitioned} across cores and stored in fixed-latency on-chip memories.
  This eliminates frontend stalls, assuming each program partition fit a core's instruction memory.
  \item Manticore replaces branches with \emph{predication} and executes all code paths.

  \item Each core accesses only the program state stored in its register file and local, fixed-latency scratchpad memory.

  The scratchpad holds the small (few KiBs) on-chip memories typically found in RTL designs (FIFOs, etc.).
  \item When the program state will not fit in the scratchpads (e.g., large processor caches or memories), a \emph{privileged core} accesses an off-chip DRAM memory using a \emph{global stalling} mechanism to ensure all cores and the NoC remain in lockstep.
\end{itemize}

\subsection{Instruction Set}\label{sec:isa}

We briefly describe unconventional aspects of the ISA specific to RTL simulation.

Each core supports 32 programmable \emph{functions}, which accelerate chains of bitwise logic operations with up to four inputs.
For example, consider the expression \verb+(a&0xf)|(b)|(c&0x3)|(d^0x1)+, with \textcode{a}, \textcode{b}, \textcode{c}, and \textcode{d} being operands\footnote{Taken from picoRV32, a multi-cycle RISC-V processor.}.
A \emph{single} custom instruction can replace these six instructions (see \secRef{cf_insert}).
Programmable functions are loaded into a processor at boot time.

The \textcode{Expect rs1, rs2, eid} instruction raises an exception \textcode{eid} if the values of registers \textcode{rs1} and \textcode{rs2} differ.
Exceptions are used to invoke services from the host processor (e.g., \textcode{\$display} and \textcode{\$stop} in Verilog).
Exceptions, like global memory accesses, stall the execution of all cores and the NoC until they are resolved.
Instructions capable of globally stalling the execution are \emph{privileged} and reserved for a single core to permit an efficient implementation (see \secRef{global_stall}).

Each core has a scratchpad memory (up to 128KiB) for local load and store operations.
Loads execute unconditionally, but stores are predicated.
Global load and store (predicated) instructions are privileged and access large, off-chip memories using 48-bit addresses.
From the perspective of a compiler, both global and local memory instructions have the same predictable access latencies since the long off-chip latency is masked by stalling all cores and the NoC until an access completes.

The producer of a value initiates communication with a \textcode{Send} instruction, the only way cores communicate.
The \textcode{Send rt, rs, tid} instruction invoked by a core \textcode{sid}, requests target core \textcode{tid} to update its register \textcode{rt} with the value of register \textcode{rs} from core \textcode{sid}.
The register update is delayed\footnote{The delay is compiler-enforced (it is not architectural).} until the end of a \vcycle, as depicted in \figRef{isa_overview}.