Number-Theoretic-Transform (NTT) is a variation of Fast-Fourier-Transform (FFT) on finite fields. NTT is being increasingly used in blockchain and zero-knowledge proof applications. Although FFT and NTT are widely studied for FPGA implementation, we believe CycloneNTT is the first to solve this problem for large data sets (2^24, 64-bit numbers) that would not fit in the on-chip RAM. CycloneNTT uses a state-of-the-art butterfly network and maps the dataflow to hybrid FIFOs composed of on-chip SRAM and external memory. This manifests into a quasi-streaming data access pattern minimizing external memory access latency and maximizing throughput. We implement two variants of CycloneNTT optimized for DDR and HBM external memories. Although historically this problem has been shown to be memory-bound, CycloneNTT's quasi-streaming access pattern is optimized to the point that when using HBM (Xilinx C1100), the architecture becomes compute-bound. On the DDR-based platform (AWS F1), the latency of the application is equal to the streaming of the entire dataset log(N) times to/from external memory. Moreover, exploiting HBM's larger number of channels, and following a series of additional optimizations, CycloneNTT only requires log(N)/6 passes.

This work takes an architectural approach to systematically characterize components and mechanisms that are the main sources of low operating clock frequency when implementing a typical pipelined general purpose processor on an FPGA. Several previous works have addressed specific implementation inefficiencies, however mostly on a case-by-case basis. Accordingly. there is a need to systematically characterize the sources of inefficiency in soft processor designs. Such a characterization serves to deepen our understanding of FPGA implementation trade-offs and can serve as the starting point for developing FPGA-friendly designs that achieve higher performance and/or lower area. We start with a typical 5-stage pipelined architecture that is optimized for custom logic implementation and that focuses on correctness, modularity, and speed of development.

This work studies branch predictor implementations for general purpose, pipelined, single core soft processors. It shows that the existing designs do not map well onto reconfigurable hardware since they were optimized for custom logic implementation. This work then proposes an accurate and fast branch predictor that uses few resources on FPGAs. The proposed predictor uses: (1) an FPGA-friendly pattern based direction predictor, (2) a return address stack, (3) in-fetch target address calculation instead of a branch target buffer, and (4) instruction pre-decoding. Experimental measurements using a subset of the SPECCPU2006 workloads show that the presented FPGA-friendly branch predictor delivers high performance while operating at approximately 259 MHz using only 147 ALUTs and one BRAM on an Altera Stratix IV FPGA.

This work introduces a new branch predictor design that increases the perceived predictor capacity without increasing its delay by using a large virtual second-level table allocated in the second-level caches. Virtualization is applied to a state-of-the-art multi-table branch predictor. We evaluate the design using instruction count as proxy for timing on a set of commercial workloads. For a predictor whose size is determined by access delay constraints, accuracy can be improved by 8.7%. Alternatively, the design can be used to achieve the same accuracy as a non-virtualized design while using 25% less dedicated storage.

This work explores instruction scheduler designs for single-issue, out-of-order soft processors targeting irregular workloads. It shows the effect of scheduler size, scheduling policy and back-to-back scheduling on performance, area, and frequency. It is shown that for a modern, high-end FPGA (Altera Stratix III) the best performance is achieved by a small, 4-entry instruction scheduler with an age-based instruction selection policy and back-to-back scheduling. A combined scheduler and register renamer is shown to operate at 303 MHz.

Generating realistic and responsive traffic that reflects different network conditions is a challenging problem associated with performing valid experiments in network testbeds. In this work, we preset Caliper, a highly precise traffic generation tool, built on NetThreads, a flexible platform that we have created for developing packet processing applications on FPGA-based devices and the NetFPGA in particular. We will demonstrate the effect of ad-hoc inter-departure times on a commodity NIC compared to precisely timed inter-departures with Caliper. Both NetThreads and Caliper are available as free software to download.

As a step torward a viable, single-issue out-of-order soft core, this work presents copy-free checkpointing (CFC), an FPGA-friendly register renaming design. CFC supports speculative execution by implementing checkpoint recovery. Compared against the best conventional register renaming implementation CFC requires 7.5x to 6.4x fewer LUTs and is at least 10% faster.