91³Ô¹ÏÍø

Figure 1 depicts a custom hardware resource as needed for a single fused instruction performing Montgomery reduction. A resource for Barrett reduction looks very similar, so both were merged and shared between the instructions. Furthermore, multiple instances of the Barret reduction block, along with adders and finite-field multipliers, were combined into a larger butterfly-alike hardware block as depicted in Figure 2, which is triggered by even more specialized single instructions.

The debugger snapshot in Figure 3 shows how the specialized butterfly instructions are utilized by the compiler in the innermost loop of the number-theoretic transform (NTT) function.

The innermost loop is implemented as a hardware loop (zlp). The loop body consisting of six instructions is software-pipelined, consisting of butterfly instructions, finite-field multiplications and additions, with memory accesses scheduled in parallel. 

For the Keccak permutation function, the situation is a bit more complicated. The bit-level logic operations of the hashing mechanism can still be fused into one big logic cloud. The interface of the function, however, takes an entire array of 25 64-bit state variables as an argument, which results in extensive load/store traffic on the general-purpose register. The general-purpose register file of the baseline processor (32 x 32-bit) is just not big enough to capture 25 64-bit values simultaneously, and additionally, it would be too expensive to add the number of parallel ports required by the Keccak operation.

Instead, we created a dedicated register file ¡°S¡± with 25 fields of 64 bits, and with dedicated 64-bit load/store access to the data memory. In addition, each register field has a direct port to the Keccak logic, which can thus access all 25 fields in parallel, as depicted in Figure 4.

The debugger snapshot in Figure 5 shows how the compiler schedules a single-cycle instruction triggering the Keccak logic, embedded in a single-instruction hardware loop, which is surrounded by memory load/store instructions to the special S register file.

Figure 6 is a screenshot of the nML viewer, a utility to graphically inspect the hierarchy of the instruction set. It shows how the custom Keccak instruction and the special finite-field instructions (grouped under ¡°kyber_instrs¡±) are integrated both in the single-issue 32-bit instruction format as well as in the parallel dual-issue 64-bit instruction format.

The new Tsec example model illustrates how ASIP Designer can be used to extend a RISC-V baseline architecture for higher performance.  The specialization for the Keccak state permutation and the reduction functions result in an 8.3x speed-up of the Kyber algorithm compared to the original RISC-V baseline implementation with DSP extensions, at a moderate gate-count increase by a factor 1.8x.