FAMOUS: Flexible Accelerator for the Attention Mechanism of Transformer on UltraScale+ FPGAs

Transformer neural networks have demonstrated significant advancements in natural language processing (NLP) [1, 2], machine translation [3], computer vision [4], and other domains in recent years. Numerous transformer-based models have surfaced, including full transformers containing an encoder and decoder [2], BERT [5, 6], Transformer-XL [7], ALBERT [8], T5 [9], Routing Transformers [10], structBERT [11], and more. These models contain a remarkable feature named multi-headed attention (MHA) mechanism which is different from the traditional convolutional neural network (CNN), recurrent neural network (RNN), and long short term memory (LSTM) model. It is even replacing RNNs and LSTMs for NLP tasks, as well as convolutional layers in CV tasks, because it enables a high level of computational parallelism for both training and inference phase. This makes it well-suited for acceleration on hardware such as GPUs and FPGAs.

Nevertheless, the attention mechanism incurs high computational costs due to intensive matrix computations and intricate data flows [12]. It consumes a significant amount of runtime in many existing TNNs, ranging from about 38% to 64% when the sequence length (number of tokens in the input sequence) varies from 64 to 256[13]. Unfortunately, general-purpose platforms such as GPUs and CPUs are inefficient for processing TNNs due to low computational efficiency, underutilized memory bandwidth, and significant compilation overheads[14]. In contrast, FPGAs have gained widespread use for accelerating DNNs due to their high level of parallelism and low latency [15, 16]. Many works focus on parallelizing computations to accelerate CNN, LSTM, Graph Convolutional Network (GCN) [17, 18, 19, 20] on FPGAs. Recently, some works have successfully built FPGA or application-specific integrated circuit (ASIC) hardware accelerators for transformers [21, 22, 23]. Most of these works compress the model by using different weight pruning strategies to accelerate attention, and they reduce latency by incorporating sparse matrices. Thus, they have specialized sparse architecture for a specific application. However, different applications require different sparsity patterns, necessitating the redesign of hardware architectures for optimal results, which is a time-consuming and challenging task. ASICs are designed for a specific model and configuration, so, they perform poorly on different models or even the same model with varying configurations[24]. Custom FPGA accelerators also lack the flexibility to be reconfigured for a different model during runtime.

Thus, a versatile accelerator is needed that can efficiently handle dense matrix computations across various TNN applications. The study in [21] utilizes logic resources to implement a systolic array (SA) for parallelism, leading to a waste of digital signal processing (DSP) resources that are capable of high-speed computation at higher frequencies. DSP consumption also depends on the implementation method. For example, most accelerators [23, 25, 26, 27] used high-level synthesis (HLS) tools, while some used hardware description language (HDL) [28, 29, 30] for design. While HLS takes less implementation time compared to HDL, it is challenging to write efficient HLS code that can effectively manage certain FPGA resources like DSPs on an FPGA for optimal performance[18]. Analysis done in [31, 22, 32, 33, 34] showed that MHA occupies most of the storage and has the highest number of operations. Since the block RAM (BRAM) size of FPGAs typically falls below 36MB, input matrices must be partitioned into tiles. However, formulating an ideal partition scheme that aligns well with the architecture poses a considerable challenge.

In this paper, we present FAMOUS, a flexible accelerator designed to adapt to a wide range of TNN applications. Our HLS-based code is optimized to utilize more DSPs and BRAMs in parallel. FAMOUS integrates efficient tiling along with enhanced parallel computation and communication to accelerate the attention mechanism as much as possible.

The contributions of this paper are:

• $\bullet$

  A novel architecture that ensures high utilization of BRAM and DSP, enhancing parallel processing of the attention mechanism of the transformer and achieving low latency.

• $\bullet$

  An efficient tiling of weight matrices to accommodate large models in on-chip memory.

• $\bullet$

  A parameterized HLS code that enables users to modify some parameters at design time from HLS tool.

• $\bullet$

  A runtime programmable feature that enables users to modify some parameters at runtime from software.

• $\bullet$

  A theoretical model to validate both predicted and experimental latency.

There are several building blocks in transformers as shown in Fig. 1. An input sequence of tokens is converted into embeddings. The positional encoder enables the model to consider the order of tokens in a sequence by adding positional information to the embeddings. It generates vectors that give context according to the word’s position in a sentence. Then the vectors are linearly transformed into three tensors: Q (queries), K (keys), and V (values) by multiplying the embedding matrix with three weight matrices. The encoder block handles these tensors, transforming them into a higher-level representation that encapsulates crucial information. This process ensures the proper capture of features and contextual relationships within the input sequence. The encoder architecture comprises two main sub-layers: (1) the self-attention mechanism, and (2) the position-wise feed-forward network. The self-attention mechanism enables the model to assess different segments of an input sequence simultaneously. It captures long-range relationships by measuring attention scores and utilizing multi-head projections for various input representations. Thus, it can learn complex patterns, dependencies, and relationships effectively. The position-wise feed-forward network (FFN), which is equivalent to a multilayer perceptron (MLP), applies linear transformations to every position independently in the input sequence. In this network, two linear transformations are executed. They mainly contain matrix-vector multiplication. The first linear transformation has activation functions such as the Rectified Linear Unit (ReLU) or Gaussian Error Linear Unit (GeLU) but the second one does not have these. Furthermore, each sub-layer includes a residual connection combined with layer normalization (LN). This solves the vanishing gradient problem during training. Residual addition and LN layers are inserted after each MHA and FFN. It mainly includes the addition of matrix elements and nonlinear functions.

The decoder block illustrated in Fig. 1 is responsible for generating the output sequence based on the encoded representations supplied by the encoder. Like the encoder, the decoder also consists of a stack of N identical layers. Each layer within the decoder contains three sub-layers. They are: (1) the Masked Attention Mechanism, resembling the encoder’s self-attention, and it includes a masking feature that restricts the output’s dependency on known preceding outputs; and (2) an attention layer that directs its focus to the encoder’s output, enabling the decoder to emphasize relevant sections of the input sequence for each output element. and (3) a position-wise feed-forward network.

As illustrated in Fig 2, the scaled dot product attention in each head is a crucial part of the multihead attention layer. The attention weights are computed by performing the dot product of the Q and K matrices and subsequently scaling them down by the square root of the 2^nd dimension of the K matrix. This scaling is essential to prevent the dot products from becoming excessively large, contributing to the stabilization of gradients during the training process. Subsequently, the scaled dot products undergo the softmax function, resulting in the computation of attention weights. These weights are then utilized to perform a weighted sum of the value vectors. The ultimate output is the projection of the concatenated sequences from all heads.

The output of MHA can be represented as Equation 1 & 2. The input sequence X is linearly mapped into $Q_{i},K_{i},V_{i}$ matrices using weights and biases. The parameter $d_{k}=d_{model}/h$ is the 2^nd dimension of $Q_{i}$ and $K_{i}$. $d_{model}$ is a hyperparameter called embedding dimension and h is number of heads. ‘i’ is the index for attention heads.

Several FPGA and ASIC accelerators exist for accelerating attention mechanisms. The ASIC design in [22] exploited parallelism and datapath specialization to significantly improve performance and energy efficiency. Another ASIC called ELSA [13] used specialized approximation algorithms to reduce computation. SpAtten [33] ASIC utilized sparsity and quantization to reduce computations and memory access. A hardware-software co-design framework called Sanger [12] enabled dynamic sparsity by a reconfigurable architecture on ASIC. The FPGA accelerator proposed by Lu et al. [21] is the first hardware architecture to accelerate both the multi-head attention (MHA) layer and the feedforward network (FFN) of the transformer. However, their implementation was done using HDL for a single attention head. Ye et al.[35] proposed an FPGA accelerator for MHA with reconfigurable architecture, efficient systolic arrays, and hardware-friendly radix-2 softmax, but they did not consider maximization of BRAM and DSP usage to maximize parallelism. Fujimaki et al. [36] also proposed a systolic array-based accelerator for attention mechanism within CNN where MHA consumed 63% of the computation time, but they used MHA within CNN, not TNN. A shared computing architecture is implemented in [37], where a parallel computing array is shared between MHA and FFNs for a CNN application. A novel structural pruning method was proposed by [38] and the associated accelerator on FPGA was designed to reduce memory footprint. All of the existing hardware architectures are designed for a specific TNN and a specific sparsity pattern. They lack the flexibility to reconfigure the computing structure for different applications during runtime. Furthermore, they have not explored which tile size and what utilization of BRAMs and DSPs could achieve optimum parallelism.

The core of the accelerator was designed in C language on Vitis high level synthesis (HLS) 2022.2.1 tool. Functional verification was performed through its C simulation and C/RTL co-simulation features. This section describes the HLS design technique that generates an optimized architecture utilizing most of the BRAMs and DSPs in the processing elements, ensuring high parallelism.

Fig. 5 shows the complete system design for running the multi-head attention layer on different FPGA platforms such as U200 (UltraScale+XCU200-FSGD2104-2-E) and U55C (UltraScale+XCU55C-FSVH2892-2L-E) for our experiments. Each design parameter can be programmed during runtime up to a maximum value by MicroBlaze ($\mu$B) softcore processor.

The overall system was designed on Vivado 2022.1.2 design suite. It contains a custom IP block for the MHA accelerator, which is exported from HLS. The inputs and weights are fetched from off-chip high-bandwidth memory (HBM) using AXI4 master interfaces [39] when the load instruction from the accelerator controller is received according to demand. The accelerator receives control signals from the processor through an AXI-lite slave interface. $\mu$B can access the HBMs which is connected to the MHA accelerator. It is used to transfer data to the BRAMs from HBMs. It also sends control signals to the accelerator. The boards are connected to a host PC with USB-JTAG interface and PCIe 3.0$\times$4 interface. This host can communicate with other IPs except $\mu$B using the DMA/Bridge Subsystem for PCI Express IP [40] in the system, but PCI communication was not needed in this work. $\mu$B uses AXI-TIMER[41] to measure the latency, which includes the time between the start and stop signal from the custom IP module. The host connected to JTAG cable[42] displays the results on the terminal using the UARTlite interface[43].

Table I illustrates the runtime programmable capability, resource utilization, and performance of FAMOUS. Synthesis was performed once for a constant tile size. The design parameters such as embedding dimension ($d_{model}$), number of heads (h), and sequence length (SL) of the accelerator were configured before synthesis with the fixed values of 768, 8, and 64, respectively, according to a variant of BERT[6] and the available FPGA resources. Then they were dynamically adjusted during runtime using $\mu$B. Hence, FAMOUS can be synthesized for a fixed number of resources, but it will remain flexible enough to accommodate smaller architectures as needed. The tile size can be adjusted only before synthesis. The data was quantized into 8-bit fixed-point numbers. Quantization for various applications may lead to accuracy loss, although it wasn’t our primary focus. If a larger bit width is necessary, the design can be easily adjusted by modifying certain parameters in HLS code during design time, which will affect resource utilization and latency. Tests no. 1, 2 & 3 show how the number of heads can be varied within the same accelerator dynamically affecting the latency and throughput where throughput is defined as number of giga operations per second (GOPS). On Alveo U55C, the lowest latency of 0.94 ms and the highest GOPS of 328 were achieved for 8 parallel heads. Tests no. 4 & 5 show the effect of varying embedding dimensions on performance where latency increased and GOPS decreased for a larger dimension. Sequence length was dynamically varied for tests no. 6, 7 & 8 and performance deteriorated as the length increased. It can be observed that resource utilization remained unchanged from tests 1 to 8 because the accelerator was synthesized only once when tile size was constant, while other parameters could be reconfigured at runtime from the software.

Tests no. 9 & 10 had different tile sizes, necessitating resynthesis of the accelerator, which resulted in different resource utilization. Resource utilization decreased with a reduction in tile size, leading to increased latency and decreased GOPS. This is because a smaller tile size requires more frequent loading of each tile from external memory to on-chip memory. Tests no. 11 and 12 demonstrated the performance and resource utilization of FAMOUS on Alveo U200, highlighting its portability. We ensured high resource utilization levels, with 46% DSPs, 78% BRAMs, and 98% LUTs. Further DSP utilization was not feasible, as it would have exceeded the capacity of LUTs. The optimal number of attention heads operating in parallel was determined to be 8 and 6 when the tile size is 64 on Alveo U55C and U200, respectively. Otherwise, the LUT becomes overutilized by the ${QKV}_{PM}$ module. Reducing the tile size helped to decrease resource consumption, although at the expense of speed. Six parallel attention heads were feasible on U200, and this decrease in parallelism led to an increase in latency.

Table II shows a comparison of FAMOUS with some GPUs and CPUs running approximately at 1.5GHz frequency. Topologies include sequence length, embedding dimension, and number of heads. Assuming that attention heads operate in parallel, their number should not impact the latency. Therefore, we did not alter the number of attention heads, even though other works used different numbers. However, we varied the embedding dimensions in line with other studies to ensure a fair comparison. We achieved 3.28$\times$, 2.6$\times$, 1.17$\times$ speed up and increase in throughput compared to Intel Xeon Gold 5220R CPU, NVIDIA V100 GPU, and Intel E5 2698 v4 CPU respectively because of higher parallelism.

Table III compares our FPGA-based accelerator and several ASIC-based accelerators tailored for attention mechanisms. The ASICs utilize sparsity to mitigate resource consumption and computation time for specific applications, operating at a frequency of 1 GHz. Consequently, some ASICs in the table exhibit higher throughput compared to ours. Conversely, our accelerator employs dense matrices, ensuring no loss of accuracy for any transformer-based application. Furthermore, it provides flexibility to run many models without requiring redesign or resynthesis. Table IV provides a comparison of the latency of our accelerator with other FPGA-based accelerators. The works in [21], [35], and [44] reported latency for single-head attention calculation. Their embedding dimensions are also smaller in this table. The number of operations (GOP) reported for the transformer base model in [44] is equivalent to the operations of a single self-attention head. It compared latency with [21], which reported latency for single-head computations based on the given resource usage and algorithm. Ye et al. [35] compared its results with [21], so it was assumed that it also measured latency and resources for single-head computation. Since our results were for 8 self-attention heads, we multiplied the results of other works by 8 for a fair comparison. It also compared with Peng et al. [25] though Peng et al. implemented a complete transformer model. However, it provided latency details for each layer, allowing us to extract the latency specifically for the attention layer.

To ensure a fair comparison, we presented the latency specifically for the computation of the attention mechanism, excluding the latency associated with load and store operations for the accelerator, in this table. Our latency is lower and GOPS is higher than all other works except for Calabash[34] because it excluded computation time for Q, K, and V calculations. Calabash claims to outperform the Intel E5 CPU with a $2.5-6.7\times$ speedup. Therefore, its latency and GOPS could be calculated using the Intel E5 CPU’s data from Table II. In summary, we were able to utilize more DSPs and BRAMs in parallel, even with HLS implementation, achieving the lowest latency for a larger embedding dimension.

The parameters that affect the resource utilization and performance of FAMOUS are the tile size or number of tiles in the attention module, the number of attention heads, the sequence length, and the embedding dimension when the bit width is fixed. An analytical model was developed to establish the relationship between these parameters and latency. This model aids in estimating both latency and the value of the parameters before synthesis.

The design is modular, and each module is implemented as a function with loops. Thus, the latency of the modules depends on the loop iteration latency, which in turn depends on the loop pipeline and unrolling pragmas. For the nested loops in the modules, the second loop from the last is pipelined resulting in a complete unroll of the innermost loop. The outermost loop had no pragmas to avoid complicated pipeline depth and resource requirements. Pipelined loop latency (PLL) can be calculated by equation 3. If it is enclosed by another loop, then the total latency (TL) will be given by equation 4. Here, Trip_count (TC) is the number of iterations of a loop, and the initiation interval (II) is the latency between the initiation of two consecutive iterations. Pipeline_Depth is the latency to finish one iteration. It depends on the sequential and parallel operations executed in one iteration. Different modules of FAMOUS can have different Pipeline_Depth (PD). The latency is measured in clock cycles (cc).

Equation 3 & 4 are generalized equations, the variables of which differ for different modules of FAMOUS as shown in the following equations.

where, PD_L includes the time required to establish communication with HBM using AXI master interface (7 cc), read address location (1 cc), load (1 cc), and store (1 cc) data from and to that address, and convert floating point data to fixed point (3 cc) for tasks such as loading all inputs (LI) and all biases (LB), as well as loading inputs (LIA) and weights (LWA) for each attention head. PD_MHA equals ($\frac{d_{model}}{TS}$) plus the time required to load (1 cc), multiply (2 cc), add (1 cc), and store (1 cc) for computing self-attention (SA) in $QKV_{PM}$ module. PD_BA includes latency associated with loading, adding, and storing operations in bias addition (BA) tasks. PD_S equals ($\frac{d_{model}}{h}$), the time required to compute the score (S) in $QK_{PM}$ module. PD_SV equals SL in the computation of SV within the $SV_{PM}$ module. Experimental results showed that

Equation 13 represents the total latency ($LAT_{total}$) in clock cycles (cc), which was calculated by summing equations 5 through 12. Equation 14 converts clock cycles into milliseconds (ms).

For instance, the analytical model predicts a latency of 0.98 ms at 400 MHz for the configuration of test 1 in Table I, closely matching the experimental result of 0.94 ms. Likewise, for test 6, the analytical model estimates a latency of 1.9 ms, which is very close to the 2 ms observed experimentally. Other data from the same table will also comply with the analytical model.

In this research, a flexible FPGA-based accelerator was designed for the multi-head attention (MHA) layer of a transformer neural network (TNN) using a high-level synthesis (HLS) tool. The accelerator architecture leverages the parallelism of the FPGA and the inherent parallelism of the MHA layer. Resources including BRAMs, DSPs, and LUTs were utilized in an optimized way on Alveo U55C and U200 FPGA platforms to maximize parallelism and minimize the latency. The accelerator is runtime programmable to support different topologies without going through synthesis steps. An efficient tiling and loading of weight arrays were implemented to accommodate large models in on-chip memory without exceeding the capacity of computation units. Experimental results demonstrate that our design achieves a maximum throughput of 328 GOPS, surpassing some CPUs and GPUs. It achieves comparable throughput with state-of-the-art ASIC accelerators, which operate at higher frequencies and leverage sparsity to reduce computation and resources. Moreover, it achieved a latency that is $1.3\times$ lower than the fastest state-of-the-art FPGA-based accelerator. In this paper, the architecture supports only the attention module, but it will be expanded to support the full encoder and eventually both the encoder and decoder of the transformer in future work using the same architectural concept.