[Simulator] Hardware-Accelerated Hardware Simulation

[chhzh123]

The current HLS simulation is too slow and only has sequential semantics for dataflow programs. We may want to build our own simulators in Allo that can simulate various dataflow programs in parallel.

Some reference simulators include:

• TAPA: https://github.com/rapidstream-org/rapidstream-tapa
• LightningSim: https://github.com/sharc-lab/LightningSim
• hls::task: https://docs.amd.com/r/en-US/ug1399-vitis-hls/HLS-Task-Library

[Oh-Afterglow]

1/29

• Selected OpenMP (with its MLIR dialect omp) API for implementing the parallel simulator
• Learned the usage of omp dialect using LLVM Flang
  • Flang can emit MLIR code with omp operations from Fortran code using OpenMP
• Confirmed that the MLIR execution engine directly supports the omp dialect as well as the llvm dialect
  • Tried lowering omp to llvm, but found that omp is only meant to be compiled into LLVM IR
  • Made examples from Flang run on the execution engine successfully
• Written a pass to inject omp operations into the MLIR representation of Allo dataflow programs to enable the parallelism of different PE functions
• Created a lowering pipeline compatible with MLIR code including omp operations
  • Reference: https://discourse.llvm.org/t/help-lowering-affine-loop-to-openmp/72441/8
• Successfully simulated the tiled GEMM example
• Still working on the implementation of pipes (i.e. the inter-process communication through FIFO buffers)

[Oh-Afterglow]

2/9 Update

• Implemented pipes as lock-free circular queues
  • Updating head/tail pointers with omp.atomic.write while leaving other code unlocked
  • Maintaining memory consistency with omp.flush
  • Constructing the circular queue structure using allo.StructType
• Extended the lowering pass of allo.StructType
  • Added the support for StructType as function parameter
• Tested the simulation of the producer-consumer example
• Testing the passes on other examples
  • The pipe implementation pass works fine
  • The extended part of struct lowering pass is still under debugging

A late update on this old comment: this simulator prototype had passed all dataflow testcases that had no lowering issues before 2/14 and got merged in #292 and #308.

[chhzh123]

Link to #290 for dataflow switching in Feather

[Oh-Afterglow]

Preliminarily implemented a generator for FEATHER, including the NEST engine for pipelined local reduction and inter-layer forwarding plus the BIRRD network for reorder-in-reduction, using the dataflow model. The implementation passed the dataflow OMP simulator test of the GEMM case with configurations of different network sizes.

Here's several challenges or problems encountered, and the solutions for some of them:

1. In the original FEATHER RTL implementation a strict sequential ordering of PE operations is enforced natually with a clock signal. It's ensured that in any cycle only at most 1 NEST layer write to the bus and the layers occupy cycles in turn, thus the first stage of BIRRD always receive correct data for global reduction.
   Solution: To achieve a similar but relaxed ordering in the abstract dataflow model and its simulator without clocks, the NEST PEs only forward the last iAct for a local reduction after putting result on the bus (in the RTL version forwarding and computing happens simultaneously), so that the bus will not be preempted by the next layer due to data dependence.
2. The NEST PEs are designed to conduct multiple local reductions instead of only one. Since all local reductions are fully pipelined, as Fig. 9 in the paper shows, the 1st reduction of the last layer will overlap with the 2nd reduction of the first layer, which also forms an ordering. This is a special case for the problem 1, since the first layer is not data-dependent on the last one.
   Solution: Dummy FIFOs are introduced between the last and the first layer. The first layer will get iActs data from the last layer like in the common case, but won't use it for computation. (This may be not a good solution.)
3. There are 2 selections for bus implementation using FIFOs. The 1st one is to add a FIFO for each NEST PE in the same column to communicate with the corresponding egg. This will force the first BIRRD stage to traverse the AH FIFOs explicitly. However, traversing the FIFO array through a loop with AH being the parameterized bound is currently not possible, as mentioned in [BUG] df.arrays not accepting non-PID index variables as subscripts #325. The 2nd one is to break the single-source-single-sink semantic of FIFOs and use only 1 FIFO with multiple sources for a column. But this is incompliant with HLS C++ streams, and the stream implementation in the simulator does not support simultaneous writing.
   Solution: The multiple-source FIFO is chosen. This avoids adding the redundant FIFO traversing logic to the first BIRRD stage. Eggs can handle global reduction while being agnostic of the data provider layer, which is the same as the original implementation. And the solutions for problem 1 and 2 can fully prevent FIFO writing conflicts in the simulator.
4. Due to challenge 2, this design is not simulatable with HLS csim mode, since the latter attempts to completely execute all logic of a PE before continuing to the next one following the program order.
5. Due to challenge 3, csyn with vitis_hls is not possible. Other synthesis tools should be used.
6. The solution of challenge 3 introduced a more complicated memory sharing case. This made memory inconsistency a mostly suspected cause when stuck PEs were observed in a simulation.
   Solution: This cause can be excluded. According to OpenMP specification, an atomic write operation synchronizes the memory with the thread's local view immediately, and a flush before a read operation updates the thread's local view with the memory. So the current simulator implementation is correct. Actually the simulation got stuck because the problem 2 was not solved then and simultaneous writting to FIFO happened unexpectedly.