Optimisation and evaluation of the CraterLake FHE accelerator on FPGA

Optimisation and evaluation of the CraterLake FHE accelerator on FPGA Sergi Soler Arrufat In partial fulfilment of the requirements for Bachelor’s degree in Mathematics and Bachelor’s degree in Informatics Engineering at Universitat Politècnica de Catalunya · Barcelonatech Supervised by: Arvind Daniel Sanchez Miquel Moretó Planas April 2024 Facultat de Matemàtiques i Estadística ii Acknowledgements I would like to express my deepest gratitude to Prof Arvind and Prof Daniel Sanchez for hosting me at CSAIL and providing me with the opportunity to research in a topic that is in the intersection of many of my interests. I would also like to thank Fares Elsabbagh, Tianhao Huang, Jiazheng Liu, Nikola Samardzic and Jianming Tong for the help they have provided me during this project. I also extend my most sincere gratitude to Miquel Moretó at BSC for his supervision and help with the project, and also Joan Cabré and Xavier Martorell for their help in using the FPGAs. This project would not have been possible without the help (financial and otherwis) of many institutions. I specially thank CFIS and Fundació Privada Mir-Puig for their assistance during all my bachelor’s and specially during this stay and Generalitat de Catalunya, the European Commission and Banco Santander for their financial help for this stay. iii iv Abstract Fully Homomorphic Encryption (FHE) allows performing computations on encrypted data without revealing it to the computing party. Compared to no encryption, it has a computing overhead of many orders of magnitude with general purpose hardware. Specialised hardware for acceleration of FHE is a current research topic. This work explores the port, optimisation and evaluation of the NTT unit of the CraterLake FHE accelerator from its original ASIC target to an FPGA. A variety of different optimisation ideas are evaluated, among them changing the latency of multiplications, changing the way that configuration data is fed to the unit and segmenting it. For a fixed 64- element width, a variety of combinations of said changes is evaluated, and best versions for different objectives are found. The resource usage is studied for different module input widths, as well as the performance of one specific optimisation combination. For frequency optimisation, a 3.5x improvement in maximum achievable frequency is reached compared to an unoptimised port. For single-transform time optimisation, a 45% reduction in total transform time is achieved compared to the unoptimised port. Keywords: Homomorphic encryption, hardware acceleration, Number- Theoretic Transform, FPGA, Bluespec SystemVerilog AMS classification: 68W35, 68P35, 68P27 v Resumen La criptografía completamente homomorfa (FHE por sus siglas en inglés) permite computar sobre datos encriptados sin revelarlos al agente que realiza la computación. Comparado con computar sobre datos no encriptados, utilizarla en maquinario de propósito general supone un sobrecoste computacional de múltiples órdenes de magnitud. El maquinario especializado para acelerar FHE es una línea actual de investigación. Este trabajo explora el traslado, optimización y evaluación de la unidad NTT del acelerador de FHE Crater- Lake, desde su soporte original para chips ASIC a placas FPGA. Varias ideas para optimizarlo son evaluadas, entre ellas cambiar la latencia de las multiplicaciones, cambiar la forma en que los datos de configuración se proporcionan a la unidad y segmentarla. Para un ancho fijado de 64 elementos, una variedad de combinaciones de las anteriores ideas es evaluada y se encuentran versiones idóneas para distintos objetivos. El uso de recursos es estudiado para varios anchos de entrada del módulo, además del rendimiento para una combinación específica de optimizaciones. En el caso de optimizar para mejor frecuencia, se logra una mejora de 3.5x en la frecuencia con respecto a la versión no optimizada. En el caso de optimizar para menor tiempo, se alcanza una reducción del 45% respecto en la versión no optimizada. Palabras clave: criptografía homomorfa, aceleración por maquinario, NTT, FPGA, Bluespec SystemVerilog vi Resum La criptografia completament homomorfa (FHE per les seves sigles en anglès) permet computar sobre dades encriptades sense revelar-les a l’agent que fa la computació. Comparat amb computar sobre dades no encriptades, utilitzarla en maquinàri de propòsit general suposa un sobrecost computacional de múltiples ordres de magnitud. El maquinàri especialitzat per a accelerar FHE és una linia actual d’investigació. Aquest treball explora el trasllat, optimització i evaluació de la unitat NTT de l’accelerador de FHE CraterLake, des del seu suport original per a xips ASIC a plaques FPGA. Diverses idees per optimitzar-lo són evaluades, entre elles canviar la latència de les multiplicacions, canviar la forma en que les dades de configuració es proporcionen a la unitat i segmentar-la. Per a un ample fixat de 64 elements, una varietat de combinacions de les anteriors idees és evaluada i es troben versions idònies per a diferents objectius. L’ús de recursos és estudiat per a diversos amples d’entrada del mòdul, a més del rendiment per a una combinació específica d’optimitzacions. En el cas d’optimitzar per a millor freqüència, s’assoleix una millora de 3.5x en la freqüència respecte a la versió no optimitzada. En el cas d’optimitzar per a menor temps, s’assolex una reducció del 45% respecte a la versió no optimitzada. Paraules clau: criptografia homomorfa, acceleració per maquinàri, NTT, FPGA, Bluespec SystemVerilog vii viii Contents Abstracts v English ................................. v Spanish ................................. vi Catalan ................................. vii Contents ix Acronyms xiii 1 Introduction 1 1.1 Motivation............................. 1 1.2 Document structure . . . . . . . . . . . . . . . . . . . . . . . 2 2 Background 4 2.1 Fully Homomorphic Encryption . . . . . . . . . . . . . . . . . 4 2.1.1 Learning with errors and construction of current FHE schemes.......................... 6 2.2 Theoretical optimisations for FHE schemes . . . . . . . . . . . 7 2.2.1 Montgomery Reduction . . . . . . . . . . . . . . . . . 7 2.2.2 Residue number system . . . . . . . . . . . . . . . . . 9 2.2.3 Number-theoretic transform . . . . . . . . . . . . . . . 9 2.3 Hardware acceleration . . . . . . . . . . . . . . . . . . . . . . 12 2.3.1 CPU vs ASIC and FPGA accelerators . . . . . . . . . 12 2.3.2 Hardware logic . . . . . . . . . . . . . . . . . . . . . . 14 2.3.3 FPGAblocks....................... 16 2.4 Hardware description languages . . . . . . . . . . . . . . . . . 17 2.4.1 SystemVerilog . . . . . . . . . . . . . . . . . . . . . . . 17 2.4.2 Bluespec SystemVerilog . . . . . . . . . . . . . . . . . 20 2.4.3 Minispec ......................... 24 2.5 FPGA to host communication . . . . . . . . . . . . . . . . . . 25 2.5.1 Connectal......................... 25 ix CHAPTER 1. INTRODUCTION have reduced the overhead significantly, it is still not feasible to implement those schemes in software for practical applications. In order to allow FHE to be used in real-life applications, hardware accelerators, that is, processors specifically tailored to the operations used in this workload, are being developed. Hardware accelerators can target two main deployment platforms: ASIC, i.e., being “printed in silicon” or FPGAs, a kind of reprogrammable board, each with its advantages and disadvantages [8]. The limitations and capabilities of both these models are quite different, and therefore what might be a good design for one of these two targets might not even be feasible for the other. One of those accelerators is CraterLake [9], developed at the Massachusetts Institute of Technology (MIT). CraterLake was developed with ASIC as a target and was optimised for it. It was therefore not clear whether its design ideas could effectively be used in FPGAs. This thesis has as its objective to evaluate whether CraterLake could usefully be ported to an FPGA target. In order to do this, this report centres around the NTT unit of the accelerator, which accounts for the majority of its operations and is therefore a good starting point for it. The NTT unit is used for modular polynomial multiplication, which is usually one of the main performance bottlenecks in current FHE schemes. The objective of this thesis is to get the NTT unit of CraterLake working in an FPGA with acceptable or good performance, as that would indicate that CraterLake could realistically be adapted to this platform. In order to reach this objective, the module was first ported to the new infrastructure and language that was to be used for FPGA. It was then evaluated without major changes to its architecture and from there optimsations were made to it to make it more efficient in an FPGA. Different combinations of possible optimisations have been considered and evaluated, and the results of that work are presented in this report. 1.2 Document structure This report is structured as follows: • Chapter 2 exposes and explains the underlying concepts needed to understand this report • Chapter 3 gives a survey of related work in this field • Chapter 4 explains the project methodology and planning used in this thesis 2 1.2. DOCUMENT STRUCTURE • Chapter 5 explains the proposed changes to the accelerator as well as the factors that motivate them • Chapter 6 explains the experimental methodology used in the tests and benchmarks of the port • Chapter 7 exposes the results from the different benchmarks and compares and evaluates the different optimisations and versions proposed • Chapter 8 analyses the sustainability implications of this project • Chapter 9 exposes the conclusions of this project • Chapter 10 proposes future work to continue this line of research 3 Chapter 2 Background In order to make this report approachable without deep knowledge in every one of the areas that its topic revolves around, a basic background in each of them will be given. There are two main axes to the theoretical background. The first would be the mathematical/cryptographic side. A basic knowledge of Homomorphic Encryption is needed to understand the overall architecture and design decisions of an accelerator. This is covered in section 2.1. The second axis would be the one that revolves more around computer architecture. Its various topics comprise the rest of sections in this chapter. 2.1 Fully Homomorphic Encryption Classic encryption solves the problem of maintaining data confidentiality in transit and at rest. However, it does not allow for operating on that data. As briefly presented in the Introduction this poses some problems. Ideally we would want to evaluate functions over ciphertext in order to solve this problem. Expressed semi-formally, that could be stated as follows: Let the set of plaintexts be Pand the corresponding set of ciphertexts C, the set of keys K. Let e:P × K −→ C;x7→ e(x, k) be the encryption function, which we will denote for a given key kas ek:P −→ C;x7→ ek(x):=e(x, k) and respectively dand dkfor the decryption function. Given a set of functions F, we would want an application M:F −→ ˜ F, f 7→ ˜ f 4 2.1. FULLY HOMOMORPHIC ENCRYPTION such that: ∀x∈ P,∀k∈ K,∀f∈ F y:=f(x),˜x:=ek(x) we have that ˜y=˜ f(˜x), dk(˜y) = y The actual formal definitions are more involved than what has been presented here. Two additional properties that one might desire are compactness, which means that the complexity of decryption ˜ydoes not depend on the complexity of fand function-privacy, which means that the ciphertext does not leak information about f. [7] One example that fits the given “informal” definition but does not meet those two properties, would be one that does ˜ f(˜x)7→ (˜x, f)and the decryption function for it first decrypts ˜xand then applies f. It is quite evident that this scheme does not allow for any useful outsourcing of computation and, additionally, it is leaking the function to evaluate, making it no better than just sending fand evaluating locally. xy ˜y ˜x f dk ˜ f ek Figure 2.1: Diagram of the encryption With those properties, there are actually some classic cryptographic systems that work, given that we sufficiently restrict F. RSA [10] for example allows for multiplications of ciphertexts due to its construction. However, finding schemes that expanded Fto “all efficient functions” was an unsolved problem for many years. Non-compact schemes have been around since the early 1980s but until 2009 a compact solution was not devised. Gentry’s PhD thesis [6] described the first scheme that met all those properties, and thus was the first instance of Fully Homomorphic Encryption (FHE). 1Gentry’s scheme, as many others later, are based on having adding a certain error or noise to the message but in such a way that it can hopefully be removed at decryption. As operations are performed on the ciphertext (and specially with multiplications), the noise grows until it is no longer 1The ‘Fully’ here refers to the fact that any ‘efficient’ function can be evaluated, as opposed to RSA for example where only multiplications were possible 5 CHAPTER 2. BACKGROUND possible to decrypt the ciphertext correctly. Many schemes can be tuned to allow for a larger amount of noise (and therefore more operations), but this increases the ciphertext size (and therefore also decryption complexity and would make it non-compact), Gentry’s breaking idea was Bootstrapping. If one is able to evaluate the decryption function of a scheme homomorphically and an additional NAND gate, any function of arbitrary size can be evaluated homomorphically. This is because homomorphically evaluating the decryption function “resets” the noise of the message 2and NAND gates can be used to build whatever function one wants to evaluate. Gentry showed one such scheme in his thesis, but its actual performance and complexity made it useful only as a proof of concept. Since Gentry’s original scheme new ones have been developed, increasing the efficiency by many orders of magnitude. Of interest here, due to being the target CraterLake and its predecessor F1 [11] are BGV [12] and HEAAN/CKKS [13]. The concrete details of the schemes will not be given here as they are not needed for the report, but they both rely on the same underlying problem, called Learning With Errors, which will motivate the design of the accelerators later on. An idea of this problem and how it motivates the use of the Number-Theoretic Transform will be given in the next sections. 2.1.1 Learning with errors and construction of current FHE schemes The Learning With Errors (LWE) problem [14] and its related ring version [15] form the basis of many current FHE schemes. A generalisation (General LWE, abbreviated as GLWE) that covers both problems is given in [12] and an adaptated version of it is reproduced here: Definition (GLWE): Given a security parameter λ, let n:= n(λ)be an integer dimension, f(x):=xd+ 1 with d:=d(λ)a power of 2, and q:=q(λ)≥2a prime integer, all a function of λ. Let R:=Z[x]/hf(x)ibe the ring of integer polynomials modulo f,Rq:=R/qR and χ:=χ(λ)a distribuition over R. The GLWEn,f,q,χ problem is to distinguish the following two distributions: 2Again, this is a gross simplification and the actual formal justification can be found in either [6] or, for a more approachable introduction, [7] 6 2.2. THEORETICAL OPTIMISATIONS FOR FHE SCHEMES • a uniform sampling of sampling of Rn+1 qgiving (a, b), where a∈Rn qis a vector of dimension nover Rqand b∈Rq • drawing a secret s←Rn quniformly and then drawing the (a, b)∈Rn+1 qby sampling a←Rn quniformly, e←χand defining b:=ha,si+e. The security assumption is that distinguishing these two distributions is not computationally feasible. From the fact that a b:=ha,si+ecannot be distinguished from a uniform draw, a message m∈Rtwould be encrypted as (a,˜ b):= (a,ha,si+t·e+m) in BGV for example, with the public key being (a,ha,si+t·e)and the private key s. Decryption is then performed by recovering e′:=t·e+m=˜ b− ha,si mod q, and from there m=e′mod q. This will be true as long as e, the noise term, is small enough that there is no wrap-around of e′modulo q. CKKS works similarly, with slight changes in the encryption (and decryption). The result of these changes are that in CKKS operations and decryption are approximate (hence the second ‘A’ in the original acronym HEAAN), as the noise slowly ‘creeps up’ the least significant bits. In contrast, in BGV decryption is exact. The changes made in CKKS make it more efficient for fixed-point operations, for which this progressive loss of precision is an acceptable trade-off. With both schemes, homomorphic addition, of two ciphertexts is performed by simply adding their ciphertext polynomials. Homomorphic multiplication involves multiplicating their ciphertexts and then performing some additional operations on the result. Polynomial (modular) multiplication is a very expensive operation and the ways to reduce the time to compute it motivate the rest of this report. 2.2 Theoretical optimisations for FHE schemes The previous section has touched on the basic workings of the FHE schemes that will be discussed in this report. This section will touch on mostly theoretical optimisations for some of them that will be found in most implementations of those schemes, both in software and in hardware. 2.2.1 Montgomery Reduction Current computers work with power-of-two modular arithmetic, most commonly 264 or 232, corresponding to 64 or 32-bit word sizes. Operating modulo a power-of-two smaller than the native one is relatively efficient, as a single 7 CHAPTER 2. BACKGROUND bitwise and operation suffices to return the result of any modular operation to the canonic representation. 3 Operating with arbitrary moduli, however, is significantly more costly. While addition or subtraction require at most one addition or subtraction to return its result to the canonic representation, multiplications require integer division, which is computationally expensive (compared to addition or bitwise and). Therefore, ways to more efficiently operate are desired if one is to perform a non-negligible number of multiplications. One of the ways to achieve better performance is the use of Montgomery reduction [16]. It works as follows: Given the modulo with one wants to work, N, choose a radix Rcoprime to Nwith R > N such that dividing Rand obtaining the residue of said division is “cheap”. Usually that means choosing Rto be a power of 2, as in processors division is a simple bit-shift and residue a bitwise and. 4 With the given Nand R, find the inverse of Rmodulo N, i.e., solve RR−1−NN′= 1, which is possible as Nand Rare coprime. With all of that, define the Montgomery form of a class as follows: given 0≤i<Nthe representative of the class, its Montgomery form will be iR mod N. Trivially one can observe that adding the Montgomery forms requires just an addition and at most one subtraction, and multiplication will give a result that has an extra Rfactor. Then, [16] introduces the following algorithm: Algorithm 1: Montgomery Reduction Function REDC(T) m←(Tmod R)N′mod R; t←(T+mN)/R; if t≥Nthen return t−Nelse return t; Which, once applied to the result of the multiplication of Montgomery forms returns the Montgomery form of the multiplication (details can be found in the original source). One will note that it does only involve divisions and modulo Rwhich as has been explained, will be efficient if Ris chosen properly. Therefore, the only expensive operation is getting the Montgomery form of a class. Getting the original class from its Montgomery form is just applying the above algorithm. 3The one that represents the classes with the smallest non-negative number they contain 4In custom ASIC or FPGA architectures, these operations with a fixed R do not even involve any gates, just wiring 8 2.2. THEORETICAL OPTIMISATIONS FOR FHE SCHEMES As long as conversion between the two forms is done infrequently, as is possible given that we can add and multiply in Montgomery form and only convert at the beggining and end, this will give major performance improvements. 2.2.2 Residue number system Operating on large numbers can be computationally costly. As one increases the word size (or uses multi-word numbers), the carry values make arithmetic slower, as one must propagate them across more bits (or words). Conversely, performing the same operations on many smaller numbers at the same time does not incur the same costs. Therefore, a way to map large numbers to a set of smaller numbers that still allow for arithmetic would be desired. Residue Number System (RNS) does exactly that, provided that some conditions are met. Given a non-prime modulo M=m1· · · mnwith mi pairwise coprime but not necessarily prime, one can represent any number A as the vector of its moduli by each mi: A→(a1, . . . , an)where ai:=Amod mi The Chinese remainder theorem states that this mapping will be a one- to-one function, and therefore this number system is well-formed and we can use the vectors instead of the long form. Addition and multiplication in RNS form are done position wise, that is, if C=A+Band D=A·B, their RNS forms as defined above are also given by ci=ai+biand di=ai·bi. Therefore, as was desired, one can perform those operations for each modulo in parallel and get the same results as if one was operating directly with the modulo Mforms. 2.2.3 Number-theoretic transform Modular polynomial multiplication requires performing a convolution on its coefficients. Even with all other optimisations, multiplications are still an expensive operation, and therefore a convolution is even more so. Reducing the number of multiplications one needs to perform for it would therefore be a good way to improve performance and reduce the hardware (or memory) needed for the algorithms that use it. In the conditions one finds in the described FHE schemes, the Number- Theoretic Transform (NTT) is the transform that achieves this goal. The NTT can be considered as a generalisation of the Discrete Fourier Transform (DFT), they share most properties and algorithms normally need only slight adjustments from their DFT versions. 9 CHAPTER 2. BACKGROUND The NTT takes as an input the vector of Nelements, X= (x0, . . . , xn−1) and returns a vector of also Nelements, ˜ Xits transform, with the following formula: ˜xi= n−1 ∑ j=0 xjωij Where ωis an n-th root of unity in the working ring. Its powers ({ωi}i∈[n]), are commonly called twiddles and, given that they are constant, are often precomputed. A more thorough explanation of the transform can be found, for example, in [17]. The performance gains when using the transform form of a polynomial come from the fact that a convolution of two polynomials in the original space is done in the transform space by a simple multiplying their two transform vectors element-wise. That is if we have vectors Xand Y, their convolution (modulo N) is Z(so zi=∑n−1 j=0 xjy(i−j)mod nmod N) and we define ˜ X=NT T (X),˜ Y=NT T (Y)and ˜ Z=NT T (Z)we have that ˜zi= ˜xi˜yi. When one takes into account that the NTT is linear, in other words, NT T (X+Y) = NT T (X) + NT T (Y), one can use the NTT to store the polynomial coefficients most of the time. Performing and inverting the transform is therefore done very occasionally, which makes using the transform form more efficient than performing the convolutions natively, even when taking into account the cost of converting from one form to the other. Performing the transform naively might still be expensive, taking O(n2) time if one simply evaluates the values as with the formula given above. One can use a Fast Fourier Transform (FFT) algorithm, such as Cooley-Tukey [18] to reduce the computational complexity. Cooley-Tukey works by recursively breaking an Nlength transform into 2 N/2 ones and combining them to get the full transform. On top of that, the FFT or NTT can be done in-place, that is, without needing extra space, with the trade-off that a fixed bit-reversal permutation must be done at the end of the process. Figure 2.2 shows how the in-place algorithm can be described as a circuit. One can observe that this algorithm can easily be staged in O(log n) stages and takes O(nlog n)multiplications (O(n)multiplications per stage). Finally, another algorithm that can be used to speed up one of those transforms is the so-called Four-step FFT [19] (NTT in our case). This algorithm also decomposes a full size transform into smaller ones, but it works by “placing” the coefficients in a matrix, performing row-wise transforms, multiplying all the elements by an adjustment factor (which depends only on the matrix position) and then performing transforms column-wise. Figure 2.3 illustrates this process. Alternatively, one can understand it as performing a 10 2.2. THEORETICAL OPTIMISATIONS FOR FHE SCHEMES n nttDIFMultiplyStep n/2 nttDIFMultiplyStep n/2 nttDIFMultiplyStep n/4 nttDIFMultiplyStep n/4 nttDIFMultiplyStep n/4 nttDIFMultiplyStep n/4 nttDIFMultiplyStep bitReversalPermutation ... Figure 2.2: A diagram of a fast NTT as a recursive decomposition of vector operations and a final permutation 11 CHAPTER 2. BACKGROUND Designs in SystemVerilog consist mainly of modules, wires and registers. A module represents a functional unit, which will have a set of input and output ports, most probably some registers inside it and possibly other modules. fig. 2.7 shows the code and schematics of one such module 1module full_adder( 2input logic[7:0] a_i, 3input logic[7:0] b_i, 4input logic c_i, 5output logic[7:0] r_o, 6output logic c_o 7); 8 9assign {c_o, r_o} =a_i +b_i +c_i; 10 endmodule full_adder a_i b_i c_i r_oc_o Figure 2.7: Full adder module code and diagram Logic in SystemVerilog is described in a way that resembles programming languages more than a logic diagram. Take for example the code and corresponding diagram in fig. 2.8: 1logic a, b, c, d; 2logic[1:0] s; 3logic r; 4always_comb begin 5unique case(s) 62'b00: r=a; 72'b01: r=b; 82'b10: r=c; 92'b11: r=d; 10 endcase 11 end 0 1 2 3 s Figure 2.8: Code and schematics for an implied multiplexer As can be seen, multiplexers, for example, are not explicitised and are instead usually described as case statements, similar to the switch statements of C-derived languages. Registers too are not explicit in the code.7Statements in SystemVerilog 7Some style guides call for naming conventions that make registers explicit and end the wire/register ambiguity 18 2.4. HARDWARE DESCRIPTION LANGUAGES are usually found in always blocks. The operations in them are performed whenever one of the signals in the sensitivity list of one such block changes. Most commonly the sensitivity list will be all the signals involved in the block for combinational logic or the clock and reset signals for the sequential logic. Registers are specified therefore as a signal that is assigned in one of these latter blocks, that is, in a block that is only updated at reset and at (usually positive) clock edges. 1logic r_d, r_q; 2always_ff @(posedge clk) begin 3r_q <= r_d; 4end Figure 2.9: A 1-bit register in SystemVerilog As one can see, SystemVerilog already represents a level of abstraction over the logic diagrams. One must be careful, for example, to not miss the assignement of a signal in one branch of a case statement and make the synthesiser 8infer a register where one was not desired. Still, SystemVerilog is considered to be a low-level language in the field of HDLs. Finally, among the many other features of SystemVerilog that could be explained here, it might be relevant to note that SV is weakly typed as a language. That means that there is no need for conversion when assigning vectors of different lengths to one another and that vectors of bits can be treated as integers without an explicit conversion. This can let many design errors go undetected and stands in contrast with the next language that will be discussed. 1logic a[3:0]; //vector of 4 bits 2logic b[1:0]; //vector of 2 bits 3 4assign b=a; 5// We are discarding the MSB of 'a' during this assignment, 6// and at most a Warning will be given Figure 2.10: Legal assignment of different length vectors in SystemVerilog 8the program that will convert the RTL code to an actual design 19 CHAPTER 2. BACKGROUND 2.4.2 Bluespec SystemVerilog Bluespec SystemVerilog (BSV) [21] is another HDL that despite its name is not directly related to SystemVerilog. In reality, the design language is “Bluespec”, and it has two possible frontends. BSV is the newer frontend and has a syntax similar to SystemVerliog. Bluespec Classic is the original frontend which has a Haskell-like syntax. Both are functionally equivalent, and the difference between them are in the syntax, not the functionality. Only BSV is relevant for this report, the existence of Bluespec Classic is noted here to explain that the “SystemVerilog” in BSV refers only to its syntax and not its actual semantics. Bluespec intends to be a higher-level HDL than SystemVerilog or VHDL 9. In that regard, one can draw a parallel with similar cases in the software space such as C and C++ or Java, for example, as will become, more obvious in the following paragraphs. Modules and methods As in SystemVerilog, the basic component in Bluespec is the module. However, unlike in SystemVerilog, Bluespec modules do not have a set of ports. Instead, they have an interface. More specifically, a module “implements” an interface, and there can be multiple modules that implement the same interface. This can be seen as a parallel between an abstract/virtual class in Object-Oriented Programming (OOP). Moreover, an interface in Bluespec does not consist of ports of signals but instead it contains either other interfaces or methods, which are called as methods in an OOP programming language would. fig. 2.11 shows a code example of both an interface and a module implementation for it. There exist three kinds of methods in Bluespec: Value methods, Action methods and ActionValue methods. Value methods are those that cause no change in state and return a value. Action methods change the state of the called module but do not provide any return value. ActionValue methods are those that both mutate the state of the module and return a value. Action and ActionValue methods can only be called in action blocks (which they temselves are), and have a different syntax for assignment (<- vs the normal =) so that the state change is explicit in the call. By separating methods in these three categories, and also having a different syntax for calling Action and ActionValue methods one greatly minimises the possibility of unforseen side-effects, which is in fact a problem a lot of 9Another HDL similar to SystemVerilog, but which has strong typing and a more verbose syntax. It is semantically very similar to SV, however. 20 2.4. HARDWARE DESCRIPTION LANGUAGES 1interface CustomMultiplier#(numeric type n); 2method Action put(UInt#(n) a, UInt#(n) b); 3method UInt#(TMul#(n,2)) get(); 4endinterface 5 6module mkCustomMultiplier#(CustomMultiplier#(n)); 7 8Reg#(UInt#(TMul#(n,2))) r <- mkRegU; 9 10 method Action put(UInt#(n) a, UInt#(n) b); 11 r<= unsignedMul(a, b); 12 endmethod 13 14 method UInt#(TMul#(n,2)) get() =r; 15 16 endmodule Figure 2.11: Example of an interface declaration and module implementation for a generic size multiplier in BSV OOP programming languages. Conditions As has been explained, methods are the means with which communication between modules happens in Bluespec. In a classical HDL such as SystemVerilog, that communication happens through ports, and that raises the issue of how to coordinate modules that cannot provide or receive data each cycle. One of the most extended solutions is using what is called a Ready-Valid protocol. Briefly, for each atomic exchange of information in the port there exist two boolean signals in opposite directions. Ready communicates that the module is ready to receive data and Valid that the other module is currently providing valid data. The exchange is mutually understood to have occurred when at a clock edge both signals are high (true). With Bluespec, those signals become implicit in the semantics. Calling a method corresponds to setting a Valid signal. When a method is actually called, the exchange is understood to have occurred, so methods need to only be able to be called when they are ready. Conditions ensure this. Conditions in Bluespec can be explicit, being written by the designer in the declaration of the module. They are also deduced implicitly from the 21 CHAPTER 2. BACKGROUND conditions of methods called in the block, so a method will have the union of its explicit conditions and the implicit ones that its operations require. Rules and scheduling Given that Bluespec is used to describe hardware, it is desirable to have a way to execute options even if a method is not called. Rules in Bluespec fill this void, similarly to how always_comb blocks did in Verilog. Rules have conditions as methods did, and the capacity for having explicit guards presents an easy way to program state machines, for example, as each state can be separated into its own rule. Communication between rules and methods happens through wires or registers, which are declared explicitly as opposed to SystemVerilog. Rules are run at most once per cycle. Finally, there is one more topic that is very important in Bluespec: scheduling. Some methods might need to be run before others, some rules might be mutually exclusive, etc. Rules and methods are atomic, and the Bluespec compiler (bsc) creates an schedule for them at compile time, which will condition the apparent order in which the rules are run (if they are, which the scheduling itself conditions as guards might change after previous rules). The designer can also manually specify priorities for different rules, as in the case where two rules or methods can be fired at a certain point, the compiler chooses one arbitrarily otherwise. Finally, though the execution of rules is scheduled to be sequential and atomic, the actual implementation is parallelized and multiple rules will most of the time be resolving concurrently, as long as that can be done without breaking sequential consistency. Provisos and recursion As alluded to previously, Bluespec is a strongly-typed language. Assigning a vector of bits to another of different lengths will not automatically truncate nor extend but always give an error (see fig. 2.12). 1Bit#(n) a; 2Bit#(m) b =a; 3//This will FAIL unless m = n and the compiler can prove it. Figure 2.12: Example of an illegal assignment due to mismatched sizes Operations like the shown truncate or zeroExtend make sense only when the size of the source and target variables are different. In some cases this is clear from context. However, when writing parametrized or generic code, be it 22 2.4. HARDWARE DESCRIPTION LANGUAGES functions or modules, those assertions cannot always be immediately deduced. The Bluespec compiler does not assume that those assertions will be met when resolving the specific instance of the function/module. Instead, every such assumption needed for the code to be correct needs to be explicitised if it cannot be proven true from context. The way this is done is trough what are called provisos. Some provisos assert arithmetic relations between parameters or define aliases for numeric types. fig. 2.13 gives an example of some of them. An Add#(k, _a, n) provisos asserts k < n (see footnote10) and would let the compiler compile a module/function containing the line in fig. 2.14. 1Add#(n, m, k) // Asserts n + m = k 2NumAlias#(j, TAdd#(n, m)) // This defines j as n + m Figure 2.13: Example of some provisos 1Bit#(n) a; 2Bit#(k) b =truncate(a); 3//The compiler must be able to assert that n > k 4//If it cannot deduce it from context, an explicit provisos 5//will be required Figure 2.14: Example of where a provisos might be needed In other cases, provisos assert other more abstract conditions. One very common is asserting that a generic type admits a Bit representation. Finally, another that will be used throughout is the assertion that a certain module can provide a concrete implementation for a certain combination of parameters. This, though at first might sound very abstract and confusing, is actually quite evident when one uses recursion. Bluespec, as many other modern OOP languages, treats all its types as ‘first-class citizens’. What is meant by that is that modules and functions can be assigned as can any other type. The definition of a module, for example, can contain conditional statements that can give different implementations for methods depending on the parameters, and can allow for toggling the definition of a rule for example. All of this is done natively in Bluespec, without needing to use the C-like preprocessor that its complier comes with. 10Type sizes are strictly positive, therefore an inequality is represented with a sum of a known variable and an unknown one, _a in this case. 23 CHAPTER 2. BACKGROUND With all of this, module recursion is possible in Bluespec. Recursion, as always, requires a base case and then general cases where some parameter approaches those of the base cases. There are many algorithms that benefit from being written in a recursive way, and Bluespec is no different in that regard. Given the strong type checks in Bluespec, however, one must add existence provisos to the non-base cases to assert that the recursively called module has an implementation. ‘Maybe’ type Bluespec has a generic class Maybe#(t) which is used to carry a value together with its validity. It essentially works as Haskell’s Maybe type or Rust’s std::option. Explicit conversion needs to happen between the underlying type ttype and a Maybe wrapper. This is done using the fromMaybe method, which needs a default value and returns either the value contained in the Maybe is it is valid or the default value otherwise. The default value is usually left as ?, which is the syntax for an unspecified value. If the Bluespec code is compiled with the -unspecified-to X option, this allows it to pass it to Verilog as an ‘X’ value, which would allow the synthesiser to avoid the multiplexer that would otherwise be inferred from said expression. Other details Bluespec differentiates between bit arrays (Bit#(n)) and integer numbers (Int#(n) and UInt#(n)). Though internally integers are represented by bits, conversion has to be explicitised to avoid errors. On top of that, Bluespec has an Integer type which represents compile/synthesis time integers that are used in elaboration (example: for loop variables) and does not have a hardware representation. 2.4.3 Minispec Minispec [22] is an HDL heavily inspired by BSV. Though it is not a strict subset of it, the incompatibilities that it introduced are few and they nearly all have a Bluespec equivalent. In general, it tries to be a simpler version of bsv. It removes the scheduling from Bluespec, making rules fire each turn. It also introduces inputs which work as Verilog input ports. Outputs are performed through methods. There are some small changes in the ways that Minispec handles parameters in modules and functions and recursion. It does not have provisos, among 24 2.5. FPGA TO HOST COMMUNICATION other changes. Minispec code can be transpiled to BSV. Parameters and recursion are resolved at the Minispec level, so the generated Bluespec code does not contain generic declarations but specific implementations instead. 2.5 FPGA to host communication When using FPGAs as accelerators, some portions of a program are offloaded from a host computer to the boards. This has to be done in an efficient and not overly complicated way. Therefore, in this section different software frameworks for this communication will be discussed. To be clear, there will not be any mention of the actual physical connection nor of the port protocols used, as those are fixed when the FPGA platform is chosen, which is usually whichever is available. 2.5.1 Connectal Connectal [23] is an open-source framework for interfacing software applications with FPGA hardware accelerators. On the hardware design side, it targets BSV. Interfaces are used as the top-level connection, connectal will automatically generate First-In First-Out (FIFO) queues in the resulting ports. 11 Connectal leverages the similarity between C++ and Bluespec and the interfaces consist of the methods that either the software On the software side, it targets C++, and works for the most part as an asynchronous library. Calls are made from C++ to the accelerator and responses are received as calls to the corresponding callback function. Connectal thus presents a very convenient workflow for accelerating existing C++ applications. On top of that, Connectal also manages the programming of the FPGA board to use. While all of these aspects make it seem a very attractive framework, connectal has limited hardware support and development for it seems to be mostly stopped. As of writing this section, March 2024, the last release published was in 2015 and there were a total of 10 commits in the previous year, of which only one referred to the inclusion of compatibility for two new boards. 11When transpiling Bluespec code to Verilog, which is done before feeding it into synthesisers, methods are converted into ports with valid and ready signals 25 CHAPTER 2. BACKGROUND 2.5.2 XRT XRT (which stands for Xilinx RunTime library) is a library that allows for simpler communication and programming of FPGA-based accelerators. Though it is mostly used with HLS and its most approachable interfaces target it, it also has utilities for RTL-based accelerators which are significantly better than manual interfacing. XRT has broad hardware support for Xilinx-made FPGA boards, and is used together with Vitis/Vivado, the Xilinx IDE/EDA toolset. XRT therefore can be used with both high-level code with HLS or RTL code in either SystemVerilog or VHDL. XRT works by having a ‘management platform’ programmed onto the target board which deals with management tasks and communicates with the host drivers. Through those, it is possible to flash (program) kernels (hardware designs) onto the board and communicate and manage them using C++ code. Whereas in Connectal all interfacing was done through implicitly instantiated FIFOs, XRT does not impose how the data transfer has to be done. Instead, it gives tools to allow the programmer to best use the resources available in the specific board however they consider best. 2.6 Other topics This section contains other topics which did not exactly fit into any of the previous sections but for which it is convenient to give a detailed explanation in this chapter either way. 2.6.1 Cyclic bitshifts and barrel shifters Given a fixed word size of Nbits, a cyclic bitshift is the operation which, given a word aand a shift value k, gives a result bwhere: •b[i] = a[(i−k)mod N]for a left shift and, •b[i] = a[(i+k)mod N]for a right shift (a[i]representing the i-th bit of afrom least to most significant, starting from 0) A trivial way to implement these operations in hardware would be to directly compute all k possibilities and have a final multiplexer choose between them. That would be an option with relatively shallow depth, but which would take significant area and cabling. 26 2.6. OTHER TOPICS n k <<1 k[0] 0 1 S0 <<2 k[1] 0 1 S0 <<4 k[2] 0 1 S0 Figure 2.15: Diagram of a barrel shifter as the composition of fixed shifts Alternatively, the bit representation of kcan be used, together with arithmetic properties, to compute it with less hardware. To do this, one divides the shifter into logk stages. Each stage has a shifter with a fixed k, which in hardware is just wiring. The exact value of kis 2ifor the i-th stage12. At the end of each stage, a multiplexer chooses whether to bypass the shifter or pass its output to the following stage. The shifter is used if the i-th13 bit of kis 1, otherwise it is bypassed. That is, constructing a kshift from the composition of 2log(k)−1, . . . , 20 shifts, leveraging the fact that the binary representation of kcorresponds with the selection bits for each stage. See fig. 2.15 for a diagram. This style of architecture, sequential chaining of units that can be enabled or bypassed depending on a value, is a general strategy that is used in many other contexts and which will feature prominently in this report. 12One can also use 2log(k)−iif properly adjusted. In fact, any order that goes through all first log(k)powers of 2 will work so long as the control signal for the final multiplexer is output consequently with the choice 13least significant, starts from 0 27 CHAPTER 3. RELATED WORK Finally, the permutation unit performs a cyclic bitshift permutation on the row. The actual permutation performed depends on the size of NTT that the unit is using. The variable value cyclic bitshift permutation can be decomposed into fixed shift-value permutations and use the same architecture as used in a barrel shifter, which is used in this case. In this way, the unit has O(log log w)latency but a low gate depth. Montgomery reduction and friendly primes As previously mentioned, the unit accepts only primes of the form p=m·2k+ 1, which [11] calls FHE-friendly. That is because, for primes with that form, the Montgomery reduction, which is what is used to compute the modular multiplications in both the small NTTs and before the transpose, can be optimised for a fast hardware implementation. Remember the Montgomery reduction algorithm from [16] and reproduced in this report as algorithm 1. The algorithm can be adapted for multiword arithmetic, that is, it can be adapted for the case where the integers are too big to fit in a single hardware word and have to be split amongst many. The multiprecision variation of the algorithm can also be found in [16]. For FHE-friendly primes, the algorithm is adapted. For a n-bit word size with a kit results in the following (adapted from [32]): Algorithm 2: Multiprecision Montgomery reduction for even word size n Function WRS(x, qh, s, w) xh←n−wMSB of x; xl←wLSB of x; t←2’s complement of xl; c←1if xl6= 0 else 0; m←qh ·t; return m·2s+xh+c Function REDCMP(x, qh) x1←WRS (x, qh, (k−n/2), n/2); x11 ←x1except its MSB bit; x2←WRS (x11, qh, (k−n/2), n/2); if x2≥qthen return x2−qelse return x2; Compared with the original algorithm, the required multiplications are much narrower. 34 3.4. F1 AND CRATERLAKE Quadrant-swap transpose Transposing a matrix is an operation that is very easy to describe but which, when actually performed, involves a lot of data movement. Therefore, it is not trivial to implement in hardware. As has already been explained, for the fully-pipelined Four-step NTT, a fully-pipelined transpose unit which receives a matrix row by row and outputs it in the same way is needed. In order to achieve this goal, it uses what it calls a quadrant-swap transpose unit. It works as follows: Observe that, for matrices with side a power-of-2 one can decompose a square matrix and transpose it as follows ([11]): (A B C D)t =(AtCt BtDt) From this expression a recursive algorithm can be deduced: Swap the Cand Bquadrants, then recursively transpose all four quadrants. The base case will be to transpose a single value, which is trivial (do nothing). With this algorithm, the problem of transposing a matrix has been reduced to swapping two of its quadrants. However, given that in the matrix is being received row-by-row, that problem is still not trivial. The solution (reproduced from [11]) is to use SRAM banks (left and right) to do as follows: 1. For the first n/2 cycles the input (Aand B) is saved to left and right respectively. 2. After that, for the following n/2 the left part of the input Cis output to the right. The output of left is output to the right of output. At the same time that Ais being read from left,Dis being written to it. 3. For the final n/2 cycles, Band Dare output from right and left respectively. Step 1. for the following matrix can be run at the same time Observe that the fact that step 3 can be run concurrently with 1 is what allows for fully-pipelined execution. A diagram of this process can be found in fig. 3.4. Table 3.1 shows the inputs and outputs of both an step and its two memory elements left and right. Finally, note that in this recursive algorithm, disabling the first kstages allows one to perform smaller transpositions in parallel, making the same hardware for a certain width easily reusable for multiple matrices of smaller widths. 35 CHAPTER 3. RELATED WORK right mem left mem 0 1 S0 Figure 3.4: Diagram for a step of the quadrant-swap transpose. Control signals for the multiplexer and swaps are omitted Adapted from [11] Input Output mem_in mem_out 1st swap 2nd swap bypass A B - - A B - - 0 (1) (0) C D A C D - A - 1 0 1 A’ B’ B D A’ B’ D B 0 1 0 Table 3.1: Table of input, outputs and control signals for the quadrant-swap transpose 36 3.4. F1 AND CRATERLAKE 3.4.4 Code and other details Since CraterLake is the starting point for this report, some additional details about its actual implementation and structure of its code will be useful to contextualise latter sections. CraterLake is designed at the RTL-level using Minispec. Many of the units are implemented using the recursion capabilities of Minispec. The codebase itself is quite parametrized. General constants like word-size and number of bits of the prime factors are defined in one file. Changing it requires little intervention. The functional units that compose it are parametrized Minispec modules. Most have at least a width parameter, and in the case of recursive ones the parameters that control it too. All of this allows for quick experimentation of different setups. Finally, validity of inputs and outputs is controlled trough Maybe values. 37 Chapter 4 Project methodology and planning This section discusses the milestones of this report, the methodology to achieve it and the planning that resulted. 4.1 Milestones As covered in the Introduction, the objective of this report is to study the feasibility of porting and/or using parts of CraterLake to an FPGA, specifically the NTT module. The concrete way to achieve this goal was to evaluate a port of the said module of the accelerator in an FPGA. Therefore, the objective was to port the NTT module. It was decided that Bluespec SV would be the language to use, given that the original was in Minispec, which can be seen as a reduced less powerful subset of it. With that, the project had three main milestones: port the accelerator from Minispec to Bluespec, get it running and synthesising on an FPGA and then optimizing it and modifying with FPGA in mind. 4.2 Methodology In order to reach the objectives, a bottom-up process was chosen for the first two milestones. With that, the first step is to get a proof of concept/feasibility working with the language/system that is to be used. That working model/code/etc. does not necessarily have to be related at all to the project. Its purpose is to both allow for checking that the final objective can be reached and to teach and serve as an example as to how. Then, once the proof of concept is working, the next step is to get the smallest part of the 38 4.3. PLANNING project working. Then, one iterates getting more complex parts under that new system/language until the objective is reached. The optimization milestone follows a different methodology. The model is already working and a proof of concept is not needed. The process here is one of continuous iteration and optimization as follows: 1. Run benchmarks 2. Identify bottlenecks from said benchmarks 3. Try a single optimization for that part 4. Run benchmarks again. Then (a) If the performance has not improved, remove the “optimization” and try from step 3 again with a different idea (b) If performance has improved but the part is still the bottleneck, go to step 3 (c) If the part is no longer the bottleneck, go to step 2 4.3 Planning Following the milestones and objectives given in the previous sections, the project was split into the following general tasks: 1. Learn about FHE (was done before the start of the stay) 2. Learn BSV 3. Translate the accelerator from Minispec into BSV 4. Get the infrastructure for FPGA ready, as well as a proof of concept model running on it 5. Get the accelerator working in the FPGA 6. Optimise the accelerator 7. Optionally, if schedule allows, try to get other modules running. Otherwise, use the time allocated to this task to remedy previous setbacks. 8. Write the report A planning for it was created, which can be found in the form of a Gantt diagram in fig. 4.1. 39 CHAPTER 4. PROJECT METHODOLOGY AND PLANNING 2023 2024 Aug Sep Oct Nov Dec Jan Feb Mar Apr Learn FHE Learn BSV Translate acc to BSV Proof of concept FPGA Accelerator in FPGA Optimise accelerator Other modules/extra time Document and write report Figure 4.1: Gantt chart for the initial planning of the project 40 Chapter 5 Proposed design This chapter explains the various optimisations which were proposed and studied for the FPGA version of the NTT module. They for the most part target an improvement of the achievable clock frequency. Given that the module is always fully-pipelined (for constant modulo), that is equivalent to target an improvement in bandwidth. This follows the rationale in the original accelerator and in [31] which consider data movement the main bottleneck for this kind of accelerators. Some of these optimisations result in a higher latency as a disadvantage. 5.1 Quadrant-swap transpose changes The original CraterLake targets ASIC. As has been explained, it performs the needed transpositions for the Four-step NTT using so-called Quadrantswap transpose unit. This unit needs to use two memory banks or register files. In the ASIC implementation, SRAM us used. In an FPGA there is less flexibility, and one cannot simply instantiate SRAM wherever it might be needed. To make up for this fact, FPGAs have different types of memory blocks inside the chip itself, as well as off-board memory. For Xilinx boards like the one used for this report, a memory can be implemented using a LookUp Table (LUT), or using Block RAM (BRAM) or UltraRAM memory blocks. Which type to use usually depends on the size of the memory. The memories in the quadrant-swap module therefore had to be migrated from being a hard-coded SRAM to FPGA-usable memories. Xilinx provides an XRAM block/interface which represents a generic memory from the three previous types. The decision of which exact technology to use can be taken by the designer or left to the synthesiser. Given that in the CraterLake source 41 CHAPTER 5. PROPOSED DESIGN the size of the module is configurable to different sizes, in this project the decision is left to the synthesiser, with the hope that it will choose the best technology for each size. Functionally, the module remained the same, but changes had to be made to the memory interface. The diagram of each quadrant-swap step can be found in fig. 5.1. The diagram for the general recursive module is in fig. A.1. Observe that there is no register between one step and the next, with only the memories themselves providing sequentiality. Adding registers was initially considered, but was not implemented as this module’s maximum achievable frequency was significantly higher than others and therefore there was no need to optimise it. 5.2 Input pipelining registers In some cases a very simple optimisation is simply breaking a long combinational path with pipelining registers. There are different places where this might need changes to the control structure or to the overall architecture of a module. In the case of CraterLake, however, its structure results in some places where a register can be added or removed without needing any other changes. One of those places is the input and output of different modules. The original version of CraterLake already has registers at the end (output) of most modules. It does not, as a rule, have registers at the input of most modules. Having a register at the output of a module and another at the input of the following one might seem redundant if one only considers gate depth as a contributor to path delay, but that is because routing delays are not being considered. In real designs with large amounts of logic, the time to propagate a signal trough a wire, even with no logic, can account for a significant proportion of the total delay. In the first tests after getting CraterLake in an FPGA it was observed that the Cooley-Tukey NTT submodule was at times quite limited by routing. Therefore, one of the proposed optimisations, is to add registers to the input of the recursive steps of it (nttDIFMultiplyStep in fig. 2.2). See ?? for a visual diagram. 42 5.2. INPUT PIPELINING REGISTERS left_ buffers right_ buffers vec extract_ subarrays 0 1 S0 0 1 S0 swap_quadrants_i isValid ctrl_logic 1'b1 0 1 S0 0 1 S0 0 1 S0 zip_subarrays Figure 5.1: Implementation of the quadrant swap 43 CHAPTER 5. PROPOSED DESIGN 5.5 Change list Given that most optimisations consist in altering the pipeline depth of the original design, names where given to those changes for latter evaluation. The following table summarises the proposed changes/places where pipelining can be added: Name num Description Module Fig IO1 1 A register in the input of nttStage nttStage A.3 IO2 2 A register at the output of montgomeryRestricted montgomery Restricted A.4 IO3 8 Add a register at the output of twid_mem transpose WithTwiddles 5.4 SEG1 4 A register between montgomeryRestricted steps montgomery Restricted A.4 SEG2 5 A (different) register between montgomeryRestricted steps montgomery Restricted A.4 SEG3 6 A register at the input of wordReduce wordReduce A.5 DSP1 7 Set the latency for the worReduce multiplication to 1 wordReduce A.5 DSP2 11 Set the latency for the mongomeryRestricted multiplier for max_freq montgomery Restricted A.4 DSP3 12 Set the latency for the wordReduces multipliers for max_freq wordReduce A.5 Table 5.1: Table of proposed optimisations num references the internal change number (see next chapter) and Fig references the diagram where the optimisation can be found The places where the different registers are added can be found in the linked diagrams (some in the appendices) as a double-line breaking the normal flow of data. The architectural change is not something that can be easily applied and removed and therefore has no number, it will be referred as ARCH troughout what remains of this report. All the changes in this table take as their baseline the version that already has had said change. IO changes refers to registers in input/output of modules, SEG to registers in 50 5.5. CHANGE LIST Montgomery Multiplier Quadrant Swap Transpose Transpose with Twiddles Ntt Four-step Ntt wordReduce nttDifMult SEG3,DSP1,DSP3 IO2,SEG1, SEG2,DSP2 IO1 IO3 Figure 5.6: A diagram of the dependencies between modules and the changes that affect them intermidiate stages and finally DSP refer to changes to change the latency of the DSP modules for the multiplications. Finally, the diagram in fig. 5.6 shows the dependencies between modules, and which proposed changes affect them. 51 Chapter 6 Experimental methodology This chapter will explain the experimental methodology and infrastructure and scripts developed for it. 6.1 Toggleable optimisations As has been briefly explained in the previous section, most changes in the design have been coded in such a way that they can be easily toggled. ARCH is not toggleable, but all of the proposed optimisations in table 5.1 are. Those optimisations all consist in either changing a wire for a register or changing the latency of multipliers. Bluespec’s interface system makes this quite easy: for components that need to change between Wire and register, first define their register interface but do not instantiate them. Then with a preprocessor conditional, one can then choose to instantiate them as either a register or as a BypassWire (which is a wire with the Reg# interface) or DefaultWire, which in practise act as 0-latency registers. See ?? for an example of this. 1Reg#(Maybe#(Bit#(TAdd#(TAdd#(n,w2),1)))) x_1; 2 3`ifdef OPT4 4x_1 <- mkReg(Invalid); 5`else 6x_1 <- mkBypassWire; 7`endif Figure 6.1: Code that toggles potential optimisation SEG1 (internally OPT4) 52 6.2. TESTING INFRASTRUCTURE 1module mkDspMultiplier(DspMultiplier#(n,k,d)); 2 3RtvReg#(d, Bit#(TAdd#(n,k))) result <- mkRetimingMaybeRegs; 4 5method Action put(Maybe#(Bit#(n)) a, Bit#(k) b); 6result <= isValid(a) ?tagged Valid pack(unsignedMul(unpack(fromMaybe(?,a)),unpack(b))) :Invalid; ,→ ,→ 7endmethod 8 9method Maybe#(Bit#(TAdd#(n,k))) get(); 10 return result; 11 endmethod 12 13 endmodule Figure 6.2: The “implementation” of the multi-cycle multiplier Observe how the latency of the module is one of the parameters of the module, RtvReg#(d, t) reprsents a d-cycle delay line for data of type t In the case of changing the latency of multipliers, this is done in a similar way: preprocessor conditionals are used to choose which of some hardcoded versions are instantiated. It must be said, however, that multipliers are not explicitised in the code but left for the synthesiser to infer as has been explained before. Changing the latency for the inferred DSP is achieved by placing a Delay Line immediately after the multiplication, as can be seen in fig. 6.2 6.2 Testing infrastructure The testing infrastructure of this project has three main parts, each of them with a specific purpose and different characteristics. Briefly, it consists of: 1. A Bluesim (bluespec simulation) layer that is used to verify the designs and get latency data for the modules 2. A Vivado-XRT layer that can be used to run the model on a real FPGA or simulation of it and allows for end-to-end tests 3. A Vivado Out Of Context (OOC) layer that allows for module-by- module benchmarking 53 CHAPTER 6. EXPERIMENTAL METHODOLOGY 6.2.1 Bluesim Bluesim is the name given to the simulation backend of bsc. While it would be possible to simulate the bsc output SV code using a tool like Verilator [34], for example, Bluesim provides a direct BSV way to perform simulation, generating an internal C++ code and later executable. Bluesim is used in this project as it avoids the need of an outer Verilog wrapper for the testbench as well as due to its performance. As has already been explained, the main purpose of this layer is to verify the functional correctness of the BSV RTL design. In order to achieve these two goals, a set of Python scripts were created which are able, for each tested module, to generate a random input for it and its expected output. These inputs and outputs are saved to files in disk. A generic wrapper for modules in Bluespec is used as the top-level file for each module, with slight variations for each. It uses register banks that are filled at execution time by reading the mentioned files as input, and it writes its output to a different file. This output is compared with the generated by the python code to either confirm the correctness of the module or find discrepancies in the expected and observed output. The tests also use two other files to compute latency and help with debugging: • One file saves all the cycle numbers where a valid input is fed to the tested module • Another file saves all the cycle numbers when the module is outputting a Valid value By using those two files, if the module is functionally correct, the latency of it can be computed. For all the modules in CraterLake, their latency is always constant, so a sanity check is performed. This architecture can be found in the diagram in fig. 6.3. The latency measurement function of this layer is critical for anything that wants to use the accelerator in its current form. Since different enabled optimisations result in different latencies for the module that performs the modular multiplication (montgomeryRestricted, fig. A.4), a source for the latency of the modules is needed. The latency of the multiplier depends only on preprocessor macros and could theoretically be computed before compilation. However, deriving the formulas for that, while not difficult, is prone to mistakes when any changes are made to the design that could change its latency. Once the testing infrastructure had been developed, it was significantly simpler to just use the test for the modular multiplication, which already had its 54 6.2. TESTING INFRASTRUCTURE DUT File 1 File 2 File 3 read_line write_line,we Invalid ctrl_logic cycl_start cycl_end out 0 1 S0 validity Figure 6.3: Diagram of the Bluesim testing top file DUT refers, as is usual, to Device Under Test. 55 CHAPTER 6. EXPERIMENTAL METHODOLOGY latency as an output, as the source for that information, which ensured that no mistakes could be made. The test itself takes mere seconds, which is negligible compared to the time needed to simulate or benchmark the complete four-step NTT design for the target size of 64 elements. Therefore, before any simulation, benchmarking or synthesis of any module that contains multipliers, the Bluesim test for the modular multiplier is run to get the latency value and set the MONT_MAT preprocessor variable which is used in the delay line in nttDIFMultiplyStep, for example. 6.2.2 XRT-FPGA infrastructure While the Bluesim layer is really useful to check that the modules are functionally correct as written in BSV, a correct simulation does not guarantee that the design can be used in a real FPGA. Among other things, a simulation provides no insight into achievable frequencies nor resource usage, which might make what seems like a good design in theory unfeasible in practise. Moreover, the read-file write-file approach to input and output used in our simulation is very different from what is used in reality. A system was therefore developed which allowed for running the accelerator in a real FPGA. Given that the available boards were manufactured by Xilinx, XRT was used for host-FPGA communication. Connectal was originally considered, but it had to be abandoned in favour of XRT as it did not have support for the U55C boards. XRT has two modes for RTL kernels, XRT-managed kernels and usermanaged kernels. XRT-managed kernels make great use of the XRT library and might be a good design for accelerators developed with XRT as its target from the beggining. In this project, a user-managed system was used, as it was considered easier to adapt the code to that model. XRT expects a SystemVerilog or VHDL top-level file. A SV wrapper was usedfor the bluespec module. The wrapper was modified so that the Bluespec module interface consisted only on a 512-bit line memory interface and control signals. In the verilog realm, two AXI [35] interfaces are used for communication. An AXI control interface allows the hosts XRT library to access a control register bank (also a module in verilog) with a single C++ method call. By writing and reading from the bank using this interface, the control signals that are used to start the module and check whether it has finished execution or not can be controlled. The second AXI interface is used for memory access and interfaces with the Bluespec module’s memory interface. By using a generic interface with only a memory interface and startfinished control signals, the logic for the test can be displaced to be manily 56 6.2. TESTING INFRASTRUCTURE finished Bluespec DUT AXI ↔ Mem interface logic start,reset Control registers master slave m_axi HBM memory Host slave master ctrl_axi DMA Figure 6.4: Diagram of the top-level XRT Verilog module and its connectivity in BSV, avoiding the need for changing the SV wrapper when testing different modules. The Bluespec module tries to mimic the bluesim model of testing. Instead of reading the input data from a file, it first loads the data from memory to XRAM-memories. Output is similarly first written to an XRAM before being copied to memory. This is done to greatly simplify the testing infrastructure, as otherwise a custom SV wrapper as well as host program would be needed for each different module. Moreover, since a single AXI interface can retrieve at maximum 512 bits per cycle, the inputs would need to be split into different memory banks or different clocks speeds would need to be used as the modules expect significantly more than 512bits of input per cycle1The HBM memory of the U55C board 2is used for the data transfers, as a staging are from which either host or accelerator copy or read the data that the other will then tranfer to their own memory (host RAM or accelerator XRAM). 1For a 64-element 28-bit word NTT, which is the main target here, the input vector alone takes 1792 bits 2DRAM memory would work as well for a board without HBM 57 CHAPTER 6. EXPERIMENTAL METHODOLOGY With that infrastructure, it is possible to run the test sets that were used in the Bluesim simulation in either a real FPGA or a hardware-level simulation as opposed to the behaviour level simulation that Bluesim had provided. The resource usages can also be obtained after synthesis. The target clock frequency needs to be set before synthesis, as various optimisations, among them retiming, will only attempt to improve the design up to said frequency. Setting a high clock period and looking at the maximum slack time3is not a reliable way to find the best possible, for this reason. A process of trial and error was deemed to costly, as each synthesis needed around 1 hour if testing only a multiplier and around 4 hours for the complete module. 6.2.3 OOC synthesis and benchmarking Given the observed synthesis times for the whole XRT simulation, using it to measure the achievable frequency for a number of design variations did not seem feasible. Another method was used for that purpose. Out Of Context (OOC) synthesis is a synthesis mode that is used to only synthesise a part of a larger design, without resulting in a whole bitstream that can be uploaded to an FPGA. The result of an OOC synthesis can be used to speed up the generation of the full bitstream, that is, it can be seen as the equivalent of incremental compilation in hardware. OOC is significantly faster than a full bitstream generation pipeline, and experiments with it showed that the time it needed for a single synthesis of the adapted CraterLake module was between one and two orders of magnitude shorter than actual XRT image generation. It therefore opened the door to trial-and-error methods. An automated system was designed to perform a dicothomic search on the frequencies for which the OOC synthesis succeeded or failed. The time for a full dicothomic search set to a precision of 20Mhz or 5% of the observed maximum working frequency, whichever smaller, took approximately the same time as a single synthesis in XRT. By using this system, it has been possible to quickly iterate on different design ideas and get a good approximation of the maximum achievable frequency. One of the downsides of OOC synthesis is that given that its result is not a full image, it cannot be simulated nor run, and therefore it cannot verify the correctness of the module, as opposed to the previous two modes. On top of that, the resulting achievable frequencies need to be taken as only orientative for the real design, as it is possible that the added verilog wrapping and connections could decrease them. The fact that they are all 3The time between the target period and the critical path signal delay 58 6.2. TESTING INFRASTRUCTURE comparable, however, makes them a good indicator to find better and worse designs and optimisations, one just needs to take into account that the final result might be skewed. 59 CHAPTER 7. EVALUATION AND RESULTS ORIG REARCH SDSP SDSP+ ALL LOWLAT 0 0.5 1 Time (us) (a) Time plot Version Time (us) ORIG 1.316 REARCH 0.996 SDSP 1.023 SDSP+ 1.105 ALL 1.218 LOWLAT 0.612 (b) Time table Figure 7.5: Time for a single transform between transforms of different moduli can be relevant to find and the time to perform a single transform can help identify the version more suitable depending on the number of transforms between moduli change. Figure 7.5 shows the time to run a single transform using the best compiler options for each version, once the twiddles have been set up. It must be remarked that these times are not to be mistaken with the time between transforms when one is pipelining them, those go as low as 0.202ns for ALL. Instead, this reflects the latency and the additional 64 cycles of input/out for a single tranform, and would be the relevant data point for a use case where transforms are issued to the accelerator occasionally, but with the same modulo. Note that here LOWLAT is the best-performing version3, as for lowest execution time, a combination of low latency and high frequency is needed. Next, fig. 7.6 shows the time needed for performing ntransforms with each of these versions, this time taking into account the time needed to set the modulo-dependent parameters (65 extra cycles). Since the values of four of the six series are too close to discern in it, fig. 7.7 presents the difference in execution time between LOWLAT and the other 3 versions that have similar 3And is in fact the best-performing version tested overall, hence why it is considered notable (see appendix B) 66 7.5. SIZE EXPLORATION 123456 0 2 4 6 Number of transforms Time (us) ORIG REARCH SDSP SDSP+ ALL LOWLAT Figure 7.6: Execution time vs number of transforms for the selected versions performance. From that plot one can see that up to (and including) 11 transforms in a row with the same modulo, LOWLAT is the most efficient version. ALL is the most efficient version from then on. The other versions are not the most efficient for any number of consecutive transforms. Therefore, in a possible implementation, the choice to be made would be between LOWLAT and ALL. 7.5 Size exploration Having identified the ‘best’ version for a single width, an analysis of its performance for different vector widths was performed to study both their resource utilisation and achievable frequencies to find which sizes could be more efficient. Therefore, version ALL was The results, with selected resource usages, can be found in table 7.2 From the table, it can be seen that doubling size decreases frequency by less than half each time. Since 2n-width unit can also be used to process 2 n-width NTTs in parallel, 4 n/2-width, etc. The best option for throughput seems to be the 128-element wide one. A larger version is not expected to fit in a U55C board, as its DSP usage is significantly over half (6144/9024) the board’s available units and as can be seen usage seems to more than double when doubling size. Conversely, the best option for latency will always be the smallest possible for the desired size, as latency increases (and actual time even more so when considering the frequency decrease) when making 67 CHAPTER 7. EVALUATION AND RESULTS 0 2 4 6 8 10 12 14 16 −0.2 0 0.2 0.4 Number of transforms Time (us) SDSP SDSP+ ALL LOWLAT Figure 7.7: Difference in time between LOWLAT and other versions Width Freq (MHz) DSPs CLB % 4 783.4 72 0.72 8 458.6 192 1.67 16 423.4 480 4.12 32 362.2 1152 9.93 64 316.2 2688 21.52 128 186.1 6144 52.67 Table 7.2: Performance and usage of diffrent versions 68 7.6. XRT TESTING the transform size larger. Performing the benchmarking on the 128-wide version took over 24h, so it is not recommended as a development version for that reason. The choice of the 64-wide version for performance study seems a good compromise in light of this fact. 7.6 XRT testing In the hopes to get end-to-end performance data comparable to Ulvetanna’s accelerator, an attempt was made to use the XRT testbench for benchmarking. Though single multipliers were able to run and verify correctly on the U55C board, as of writing this report the four-step NTT unit does not output data when running on the real U55C. It, however, works as expected in Vivado’s hardware emulation mode. Given all these facts, it is suspected that the communication between the Bluespec test module and the board’s HBM memory is at issue. Finding errors present in real-life execution but not testing is usually a specially time-consuming process. It has not been possible to fix it in the limited time between when it was found and the deadline for this report. In any case, the goal of the XRT test was to prove that the accelerator could theoretically be run on an FPGA. Since simulation worked and synthesis was possible (even if the generated bitstream had communication issues), it has served its purpose of being an assurance that the module can in fact be used in real-life hardware. 69 Chapter 8 Sustainability analysis This chapter will consider the various sustainability considerations of this project, using a sustainability matrix method. The possible ethical implications of this project will also be discussed in a following section. 8.1 Sustainability matrix The sustainability considerations are split into three categories: environmental, economic and social. In each category, at least three main points are addressed: impact during development, impact of execution and risks and limitations. For those purposes, in all the following sections, the development will be understood to be all the work done during this thesis. The execution and risk and limitations sections will discuss the possible implications of deploying the optimised and evaluated accelerator in an FPGA. This project is a feasibility analysis and technical exploration, and therefore its main goal has not been to develop a finalised product ready for actual deployment. Therefore, these latter two sections can only contain speculation for how a future implementation might be used if that is even possible. A potential final product would probably use the studied accelerator only as one of its components, which makes many of the otherwise usual questions sometimes impossible to even estimate roughly. In order to obtain some cost and pollution estimates, the following assumptions will be used when itemizing my use of different computation resources: • Total of 28 effective weeks • Estimated use of the FPGA-enabled machines, 8h per week, for 22 of 70 8.1. SUSTAINABILITY MATRIX Item Power Hours Energy consumed Personal computer 100W 1120h 112kWh Workstations 500W 960h 480kWh FPGA Workstation 650W 176h 114kWh TOTAL 706kWh Table 8.1: Energy consumption the 28 weeks • Estimated 40h of weekly server use1for 24 of the 28 weeks • Estimated 40h of personal computer use per week Those estimates are a best-attempt guess at the actual usage. Given that the actual power consumption of none those machines can only be guessed from reasonable hypotheses (none have the actual hardware to measure it and some are shared), there seems to be no justification for obtaining a detailed usage log, as the end result will be a best-effort estimate either way. 8.1.1 Environmental impact Development Development of the project has been performed by myself with the occasional assistance of my supervisors and some of their current PhD students. The two resources used for the project have been computers/servers and FPGA boards. The main recurring environmental impacts therefore will have been the ones associated with the use of these computing resources. A consumption of 500W for the workstations has been estimated. The maximum power draw of a U55C FPGA is 150W [36]. From this, we can calculate the CO2 generated as a result of this power consumtption. Using an estimate of 0.39Kg/kWh (0.89lb/kWh, from [37] for general US consumption), the total is approximately 275Kg of CO2. As a comparison, this is approximately what is emitted by driving 3000Km in a combustion car (using KgCO2/Km from [38]) or a round-trip from Barcelona to Berlin (found using [39]). 1I estimate that the tasks I could perform locally without using it are offset by the benchmarks I scheduled to run after-hours 71 CHAPTER 8. SUSTAINABILITY ANALYSIS Execution The actual environmental impact of execution would depend on many factors which are not available for this report. Amongst them are the portion of computation that would be done with FHE instead of non-homomorphic encryption, the overhead of the system used, the amount of data, etc. An estimation cannot be provided as we have no information as to how an actual deployment might look like. Risks and limitations The use of FHE is more computationally expensive than regular encryption. A deployment of systems like the one developed would decrease the environmental footprint compared to using FHE without accelerators, but even with that it would have a significantly greater impact than using classically encrypted data. Using FHE for all data processing is not a good idea. However, the privacy benefits from using it will probably outweigh its expense in very sensitive use cases like medical data. 8.1.2 Economic impact Development The development of the project required access to two workstations which featured a “AMD Ryzen 9 5900X” processor. A quick search returned that the typical cost for a system with said processor is around €2500. A cost of €3000 will be assumed to have some margin for better components. A U55C board, of which 1 was used, costs approximately €4500 (depends on the exact USD/EUR exchange). Finally, a computer is needed to connect to the workstations and work locally. A €500 cost is estimated for it. The breakdown of the hardware cost for deveoping this project can be found in table 8.2. These costs are for a situation where the hardware needs to be purchased specifically for this project and no reuse is possible. This has not actually been the case at all. The workstations used were from Barcelona Supercomputing Center (BSC) and shared with multiple other researchers. The personal computer used was my own. No hardware was purchased specifically for this project, but the breakdown is included to illustrate the needed infrastructure. In addition to the hardware costs, the development of this project also had two other variable costs in the form of power consumption and manpower. The previously used power consumption estimate is again used here. 72 8.1. SUSTAINABILITY MATRIX Component Cost per unit Units Total Workstations €3000 2 €6000 U55C FPGA €4500 1 €4500 Personal computer €500 1 €500 TOTAL €11000 Table 8.2: Hardware cost Component Cost per unit Units Total Power consumption 0.18€/kWh 706kWh €127 Student developer 20€/h 1120h €22400 TOTAL €22527 Table 8.3: Variable costs Again, these estimations are reflective of a hypothetical case which has not been what has really happened during this project. The power consumption has been shared with other users of the workstations at BSC on top of being a high estimate. I also have not received any salary, my stay has been funded by scholarships and grants in the form of a lump sum in addition to family funds. Execution The cost of a U55C as has been stated is approximately €4500. The maximum total power of a U55C is 150W. The cost of running a U55C at full power is therefore less than 3 cents per hour. As in the previous section, further estimations are not possible as a possible deployement is not the objective nor studied in this report. Risks and limitations The use of FPGAs in environments that do not use them currently will probably require training the people in charge of the IT systems that might use them. Again, the increased power and hardware usage of FHE are drawbacks of using it, but they are probably outweighed in certain scenarios. 73 CHAPTER 8. SUSTAINABILITY ANALYSIS 8.1.3 Social impact Development Development of the project is not thought to have significant social impact. Execution Use of FHE can increase privacy and avoid potential misuse of personal data. It is not expected to impact different population groups differently neither in form nor in measure. An exception might be cases where lack of privacy disproportionally effects one group, in that case it might have a more positive effect on said group. Risks and limitations Using FHE to increase privacy can difficult finding biases in processes, as encryption would prevent or greatly difficult studies that try to evaluate them. 74 Chapter 9 Conclusions The work in this report has shown that the NTT unit in CraterLake can effectively and quite efficiently be used on an FPGA. Segmenting the unit seems to be beneficial in general, with the best-performing version also being the most segmented one. However, when using a language like BSV, care must be taken with the compilation options, as large performance differences have been observed when not using the optimal ones, going so far as to change which version was the best-performing one. Efficiently using an FPGA’s DSP unit, which in this project has mostly consisted in ensuring that all its internal pipelining registers were being used, has also been shown to a critical point in optimisation, with the performance changes due to it usually surpassing segmentation in other parts of the accelerator. Routing has shown to probably be the main limiting factor in reaching higher achievable frequencies for the accelerator, and changes that have reduced the amount of needed data movement with nearly no latency increase have shown to be quite effective. Usage of on-chip memory has proved to be significantly more suitable than in ASICs, due to both its lower cost in terms of computational resources and due to this last fact. The four-step FFT/NTT algorithms has shown to be a good choice for FPGA accelerators, as its nature allows for relatively easy segmentation, both of its logic and implementation itself as splitting the inputs and outputs amongst successive cycles. This contributes to both reduce resource usage and amount of connections (routing) needed, which as has been explained Finally, while routing is thought to have been the limiting factor in terms of maximum achievable frequency, DSP usage has shown to be the main limiting factor in terms of scaling the accelerator to larger widths. Increasing the width of the accelerator’s transform has shown to reduce its maximum frequency less than the increased throughput gained by its larger size, and therefore for production use a larger width is recommended. 75 BIBLIOGRAPHY 82 List of Figures 2.1 Diagram of the encryption . . . . . . . . . . . . . . . . . . . . 5 2.2 A diagram of a fast NTT as a recursive decomposition of vector operations and a final permutation . . . . . . . . . . . . . 11 2.3 Diagram of the dataflow of a 4-step NTT . . . . . . . . . . . . 12 2.4 Example of a full-adder circuit . . . . . . . . . . . . . . . . . . 15 2.5 Example of a partially segnented full-adder circuit . . . . . . . 15 2.6 Example of a fully-segmented full-adder circuit . . . . . . . . 15 2.7 Full adder module code and diagram . . . . . . . . . . . . . . 18 2.8 Code and schematics for an implied multiplexer . . . . . . . . 18 2.9 A 1-bit register in SystemVerilog . . . . . . . . . . . . . . . . 19 2.10 Legal assignment of different length vectors in SystemVerilog . 19 2.11 Example of an interface declaration and module implementation for a generic size multiplier in BSV . . . . . . . . . . . . 21 2.12 Example of an illegal assignment due to mismatched sizes . . 22 2.13 Example of some provisos . . . . . . . . . . . . . . . . . . . . 23 2.14 Example of where a provisos might be needed . . . . . . . . . 23 2.15 Diagram of a barrel shifter as the composition of fixed shifts . 27 3.1 Diagram of OpenFHE abstraction layers . . . . . . . . . . . . 29 3.2 Diagram of Ulvetanna’s design for a 64 x 64 NTT . . . . . . . 30 3.3 Diagram of CraterLake’s Four-step NTT unit . . . . . . . . . 33 3.4 Diagram for a step of the quadrant-swap transpose. Control signals for the multiplexer and swaps are omitted . . . . . . . 36 4.1 Gantt chart for the initial planning of the project . . . . . . . 40 5.1 Implementation of the quadrant swap . . . . . . . . . . . . . . 43 5.2 The internal architecture of a DPS48E2 . . . . . . . . . . . . . 45 5.3 Diagram of the nttDIFMultiplyStep module, with the delay linesalreadyadded........................ 46 83 LIST OF FIGURES 5.4 A side by side comparison of the old transpose with twiddles module (left) versus the new one (right) . . . . . . . . . . . . 47 5.5 Diagram of the new Four-step NTT unit . . . . . . . . . . . . 49 5.6 A diagram of the dependencies between modules and the changes thataffectthem.......................... 51 6.1 Code that toggles potential optimisation SEG1 (internally OPT4)............................... 52 6.2 The “implementation” of the multi-cycle multiplier . . . . . . 53 6.3 Diagram of the Bluesim testing top file . . . . . . . . . . . . . 55 6.4 Diagram of the top-level XRT Verilog module and its connectivity................................ 57 7.1 Additional latency cycles for each optimisation . . . . . . . . . 63 7.2 Total latency for the selected versions . . . . . . . . . . . . . . 63 7.3 Achievable frequency for individiual optimisations . . . . . . . 64 7.4 Achievable frequency for selected versions . . . . . . . . . . . 65 7.5 Time for a single transform . . . . . . . . . . . . . . . . . . . 66 7.6 Execution time vs number of transforms for the selected versions 67 7.7 Difference in time between LOWLAT and other versions . . . 68 A.1 Quadrant-swap transpose recursive module . . . . . . . . . . . 89 A.2 Top-level Cooley-Tukey NTT module . . . . . . . . . . . . . . 90 A.3 The non-recursive logic for one stage of the Cooley-Tukey NTT 91 A.4 Diagram of the whole modular (montgomery) multiplier module 92 A.5 Logic for the word reduction (algorithm 2) . . . . . . . . . . . 93 84 List of Tables 2.1 Comparison of the different targets for an algorithm . . . . . . 13 3.1 Table of input, outputs and control signals for the quadrantswaptranspose .......................... 36 5.1 Table of proposed optimisations . . . . . . . . . . . . . . . . . 50 7.1 Summary of notable combinations of optimisations . . . . . . 61 7.2 Performance and usage of diffrent versions . . . . . . . . . . . 68 8.1 Energy consumption . . . . . . . . . . . . . . . . . . . . . . . 71 8.2 Hardwarecost........................... 73 8.3 Variablecosts........................... 73 B.1 Rawdata ............................. 95 85 LIST OF TABLES 86 Appendices 87 Appendix A Diagrams Some diagrams have been included in the body of the document. Those that have not been deemed relevant enough for that but might still be useful are included here. 88 quadrant_swap_transpose_tail first_stage (QuadrantSwapStage) following_stages (quad_..._tail) fifo vec numer_of_input_vectors ctn < x Figure A.1: Quadrant-swap transpose recursive module 89 APPENDIX A. DIAGRAMS ntt use_... vec use_stages_bitmask q ntt_pipeline (NttPipelineTail) bitReversal Permutation result input_type Figure A.2: Top-level Cooley-Tukey NTT module 90 nttPipelineStage vec 0 1 S0 Mux root_of_unity_powers q use_stage regi nttDIFMultiplyStep IO1 Figure A.3: The non-recursive logic for one stage of the Cooley-Tukey NTT 91