Energy-efficient architectures for recurrent neural networks

Energy-efficient architectures for recurrent neural networks Franyell Silfa ADVERTIMENT La consulta d’aquesta tesi queda condicionada a l’acceptació de les següents condicions d'ús: La difusió d’aquesta tesi per mitjà del repositori institucional UPCommons (http://upcommons.upc.edu/tesis) i el repositori cooperatiu TDX ( h t t p : / / w w w . t d x . c a t / ) ha estat autoritzada pels titulars dels drets de propietat intel·lectual únicament per a usos privats emmarcats en activitats d’investigació i docència. No s’autoritza la seva reproducció amb finalitats de lucre ni la seva difusió i posada a disposició des d’un lloc aliè al servei UPCommons o TDX. No s’autoritza la presentació del seu contingut en una finestra o marc aliè a UPCommons (framing). Aquesta reserva de drets afecta tant al resum de presentació de la tesi com als seus continguts. En la utilització o cita de parts de la tesi és obligat indicar el nom de la persona autora. ADVERTENCIA La consulta de esta tesis queda condicionada a la aceptación de las siguientes condiciones de uso: La difusión de esta tesis por medio del repositorio institucional UPCommons (http://upcommons.upc.edu/tesis) y el repositorio cooperativo TDR (http://www.tdx.cat/?localeattribute=es) ha sido autorizada por los titulares de los derechos de propiedad intelectual únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro ni su difusión y puesta a disposición desde un sitio ajeno al servicio UPCommons No se autoriza la presentación de su contenido en una ventana o marco ajeno a UPCommons (framing). Esta reserva de derechos afecta tanto al resumen de presentación de la tesis como a sus contenidos. En la utilización o cita de partes de la tesis es obligado indicar el nombre de la persona autora. WARNING On having consulted this thesis you’re accepting the following use conditions: Spreading this thesis by the institutional repository UPCommons (http://upcommons.upc.edu/tesis) and the cooperative repository TDX (http://www.tdx.cat/?localeattribute=en) has been authorized by the titular of the intellectual property rights only for private uses placed in investigation and teaching activities. Reproduction with lucrative aims is not authorized neither its spreading nor availability from a site foreign to the UPCommons service. Introducing its content in a window or frame foreign to the UPCommons service is not authorized (framing). These rights affect to the presentation summary of the thesis as well as to its contents. In the using or citation of parts of the thesis it’s obliged to indicate the name of the author. Energy-Efficient Architectures for Recurrent Neural Networks Franyell Silfa Doctor of Philosophy Department of Computer Architecture Universitat Polit`ecnica de Catalunya Advisors: Jos´e-Maria Arnau, Antonio Gonz´alez October, 2020 Barcelona, Spain 2 Abstract In recent years, Deep Learning algorithms have been remarkably successful in applications such as Automatic Speech Recognition, Sentiment Analysis and Machine Translation. As a result, this kind of applications are ubiquitous in our lives and are found in a plethora of devices extending from small IoT systems to cloud servers. However, even for edge devices, the evaluation of Deep Learning algorithms is typically offloaded to the cloud. The main reason is that these algorithms are composed of Deep Neural Networks (DNNs), such as Convolutional Neural Networks (CNNs) and Recurrent Neural Networks (RNNs), which have a large number of parameters and require a large amount of computations. Therefore, deploying DNNs on devices with a constrained energy and memory budget is a challenge since the memory and power requirements of DNNs are extremely large. RNNs are usually employed to solve sequence to sequence problems such as Speech Recognition and Machine Translation. In addition to having extremely large memory and power requirements, they also contain data dependencies among the executions of time-steps, and thus the amount of parallelism is severely limited. Therefore, the challenge to evaluate them in an energy-efficient manner is higher than the evaluation of other DNN algorithms, such as CNNs. This thesis aims to study applications using RNNs to improve their energy efficiency on specialized architectures. More specifically, we propose novel energy-saving techniques and highly efficient customized architectures tailored to the evaluation of deep RNN models. There are several RNN topologies, but the most successful are the Long Short Term memory (LSTM) and the Gated Recurrent Unit( GRU). Consequently, they are the main focus of this work. To carry out our objective, as an initial step, we characterize a set of state-of-the-art RNN workloads running on a modern SoC. We identify that accessing the memory to fetch the network parameters is the major source of energy consumption accounting for up to 80%. Moreover, we observe that real-time evaluation requires a high power budget. Hence, we propose a novel energyefficient processing unit to perform RNN inference, which we call E-PUR. By employing a cycle-level simulator, we show that E-PUR achieves 6.8x speedup and a reduction on energy consumption of 58x when compared to a modern SoC. We further improve E-PUR’s energy efficiency by developing a novel technique that maximizes the temporal locality of fetching the network parameters, which we call Maximizing Weight Locality (MWL). The final proposal reduces energy consumption by 88x on average, while the power dissipation is 10x lower. Although E-PUR’s energy efficiency is extremely high, we observe that fetching the parameters continues to be the primary source of energy consumption. Hence, we strive to reduce memory accesses and propose a novel technique that reuses previously cached computations. Our key observation is that when evaluating the large input sequences (audio frames, words, etc.) of an RNN model, the output of a given neuron tends to change lightly between consecutive evaluations. Therefore, we exploit this observation to develop a hardware scheme that caches the neurons’ outputs and reuses them whenever it detects that the change between the current and previously computed output value for a given neuron is small. Consequently, we do not fetch the weights or perform the computations for that neuron. One of the main challenges is implementing a low-cost hardware solution to predict when a neuron’s output for the current evaluation and the previously 3 cached result will be similar. We address this issue by employing a Binary Neural Network (BNN) as a predictor of reusability. The low-cost BNN can be employed in this context since we show that its output is highly correlated to the output of RNNs. In other words, when the output of the BNN changes lightly between consecutive evaluations, it is very likely that the same happens for the output of the RNN. We show that our proposal avoids more than 24.2% of computations. As a result, on average, energy consumption is reduced by 18.5% while achieving a speedup of 1.35x. The memory footprint for RNN models ranges from a few megabytes to hundreds of megabytes, and usually, their size is reduced by using low precision for its evaluation and storage. In this regard, the minimum precision used is identified offline by an static profiling of the model. Also, it is set such that the model maintains its original accuracy. We observe that this method utilizes the same precision to compute all time-steps. However, our experiments show that some time-steps can be evaluated using a lower precision while preserving the original accuracy. Therefore, we propose a novel technique that dynamically selects the precision employed to compute each time-step. A significant challenge of our proposal is deciding when to choose a lower bit-width. We address this issue by recognizing that information from a previous evaluation can be employed to determine the precision required in the current time-step. Specifically, we use the cell state and the cell output for LSTM and GRU models, respectively. By selecting the precision based on previous time-step information, our scheme evaluates 57% of the computations on a bit-width that is lower than the fixed precision employed by methods using the same bit-width during all the time-steps. We implement our proposal on E-PUR and evaluate it for a set of modern RNN networks. We show that it provides 1.46x speedup and 19.2% energy savings on average without any accuracy loss. Our previous proposals are tailored to systems that execute one input sequence at a time. However, systems such as cloud services batch several input sequences together and compute them simultaneously. Hence, as a final optimization, we focus on batching for RNNs. RNN batching is employed to increase throughput. However, it requires using a large amount of padding due to the variability in length (i.e., number of time-steps) of the batched sequences. Hence, some schemes use a fine granularity (i.e., a small number of time-steps) when batching aiming to reduce the amount of padding. However, they perform a large number of parameters swap. The reason is that each time an RNN layer is processed, a new set of weights is loaded into on-chip memory. Henceforth, weight reuse is severely affected in previous RNN batching proposals. As a result, their energy efficiency is extremely low. We propose E-BATCH to address these issues. E-BATCH is a low-latency and energy-efficient batching scheme tailored to RNN accelerators. It requires a runtime system and simple hardware support in the RNN accelerator. The runtime is in charge of concatenating the input sequences so that batches with a large number of time-steps are created. Therefore, weight reuse is increased. On the other hand, we extend the hardware accelerator so that it tracks the state of the requests while they are evaluated. Also, it notifies the runtime once a request is completed, hence it allows a new input sequence to join the ongoing evaluation of a batch, effectively decreasing the amount of padding required. Finally, we evaluate E-BATCH on top of two state-of-the-art RNN accelerators, E-PUR and the Tensor Processing Unit (TPU). We show that, compared to the state-of-the-art RNN batching techniques, E-BATCH improves throughput by 1.8x and energy-efficiency by 3.6x in E-PUR, and by 2.1x and 1.6x, respectively, in the TPU. 4 Keywords Deep Learning, Deep Neural Networks, Recurrent Neural Networks, Convolutional Neural Networks, Hardware Accelerator. 5 Acknowledgements First of all, I want to express my sincerest gratitude to my advisors, Jose-Maria Arnau and Antonio Gonz´alez, for their continuous support during my Ph.D. study and related research, for their patience, motivation, and tremendous knowledge. I sincerely believe that I could not have better advisors. I am very grateful to Prof. Antonio Gonz´alez for giving me the opportunity to join the ARCO group and learn from him. I appreciate your invaluable guidance, your timely feedback, and your always wise advice. Thanks for pushing me to be the best and teaching me the importance of doing high-quality research. I will always be in debt with Dr. Jose-Maria Arnau for all your support and faith in me. I appreciate everything that you taught me and all the discussions that we have throughout these years. Thanks for your invaluable guidance and fruitful ideas. I will never forget your encouragement and constructive comments. Your patience and persistence made completing this Ph.D. possible. I owe a tremendous debt to La Fundaci´on Carolina and PUCMM for providing me financial support during these years. I am also very grateful to Roberto Abreu, Victor Gonz´alez, Julio Ferreira, and Jes´us Ram´ırez, which have always been pending about my welfare and success during the Ph.D. I want to make a special mention to Gem Dot, who helped me a lot at the beginning of the Ph.D. Thanks for your wise advice, support, and inspiring discussions about computer architecture and life. I want to thank all the members of ARCO that I met over these years. I was fortunate to be part of a well-known and enriching research group. Special thanks to Enrique, Hammid, Reza, Marti, Marc, Albert, Azue, Josue, Dennis, Diya, Raul, Pedro, Jorge and Mehdi for the stimulating discussions, the coffee breaks, and for all the great moments that we had at UPC. Also, thanks for your support and encouragement after those endless paper rejections. I feel blessed to have amazing friends in my life. Especially, I would like to express my appreciation to Reyna, Luis (kp), Billy, Leandro, Andres, Manuel, Junior, Engerst, and Aby. Thanks for your friendship, motivation, and moral support. It made this journey more comfortable, and I am very thankful for that. Also, I would like to thank my second family in Barcelona. Mara, Carolina, Fifi, and Aby, thank you for worrying about my well-being and opening your doors and hearts. Finally, I owe my deepest gratitude to my family for their unconditional love and support. Thanks to my brothers and sisters, Fabiannys, Josefina, Fabiolys, Heydi, and Jos´e for their continuous encouragement, and spiritual support. Particularly, I would like to thank my brother Fabio Antonio and his wife, Maria Luisa, for their unconditional support and caring. Also, I am grateful to my cousins, aunts, and uncles. I will always be in debt with my parents Fabio and Mercedes, for their genuine love, patience, and support. Especially, I will like to thank my mother for being a role model, her hard work, and always caring and supporting my brothers and me. I have the most profound appreciation for her prayers and unconditional love. 6 This thesis is dedicated to my grandmother Josefa who always encouraged me to study, be myself, and taught me the importance of being a good person. 7 LIST OF FIGURES 6.3 Relationship among neurons in the gates and elements in the LSTM cell state . . . . 87 6.4 State machine employed to dynamically select the precision for an element ck. . . . 88 6.5 Positive and negative peak region definition for the cell state of a given neuron . . . 88 6.6 LSTM cell state’s evolution for a given neuron on multiple time-steps . . . . . . . . 89 6.7 Compute Unit (CU) with Multi-precision multipliers or SIP units . . . . . . . . . . . 91 6.8 Overlapping of computations in the accelerator. . . . . . . . . . . . . . . . . . . . . 92 6.9 Structure of the Peak Detector Unit (PDU). . . . . . . . . . . . . . . . . . . . . . . 92 6.10 Linear Quantization of floating-point values for 8 and 4 bits . . . . . . . . . . . . . . 94 6.11 Comparison between our scheme (“Peaks”) and randomly selecting the precision . . 96 6.12 Speedups achieved by changing the precision dynamically . . . . . . . . . . . . . . . 96 6.13 Energy savings achieved by dynamically changing the precision . . . . . . . . . . . . 97 7.1 SequencePadding .....................................103 7.2 SequenceBucketing ....................................104 7.3 CellularBatching. .....................................105 7.4 Time-steps distribution for Deepspeech and NMT . . . . . . . . . . . . . . . . . . . . 105 7.5 Percentage of hardware utilization for useful and wasteful computations . . . . . . . 106 7.6 Architecture of a Compute Unit (CU) in E-PUR when batching . . . . . . . . . . . . 108 7.7 E-Batchexecutionflow...................................110 7.8 Evaluation of an RNN with two LSTM layers using E-Batch . . . . . . . . . . . . . . 111 7.9 Overview of E-Batch System Architecture. . . . . . . . . . . . . . . . . . . . . . . . . 111 7.10 Average Latency vs throughput for Machine Translation . . . . . . . . . . . . . . . . 115 7.11 Average Latency vs throughput for Speech Recognition . . . . . . . . . . . . . . . . 115 7.12 Average number of Requests per Joule vs Throughput for Machine Translation . . . 116 7.13 Average number of Requests per Joule vs Throughput for Speech Recognition . . . . 116 7.14 Average Latency vs Throughput for Machine Translation . . . . . . . . . . . . . . . 117 7.15 Average number of Requests per Joule vs Throughput for Machine Translation . . . 117 15 List of Tables 3.1 Hardware parameters for E-PUR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2 Configuration of TPU-like accelerator. . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.3 TegraX1parameters. ................................... 49 3.4 RNN Networks used for the experiments. . . . . . . . . . . . . . . . . . . . . . . . . 52 4.1 Steps of the Multifunctional Units for a single data element . . . . . . . . . . . . . . 59 4.2 Hardware parameters for E-PUR and E-PUR with MWL. . . . . . . . . . . . . . . . 62 5.1 Configuration Parameters for E-PUR+BM. . . . . . . . . . . . . . . . . . . . . . . . 79 6.1 HardwareConfiguration................................... 95 7.1 Hardware configuration for E-PUR and TPU. . . . . . . . . . . . . . . . . . . . . . . 113 17 1 Introduction This chapter presents the motivation behind this work and explains the challenges of performing RNN inference in hardware accelerators in an energy-efficient manner. It then provides a summary of the related work and an overview of the main contributions of this thesis. Also, we highlight the key differences between our solutions and the state-of-the-art approaches. 1.1 Motivation Deep learning algorithms have become ubiquitous in many computer science domains. They are employed on a plethora of commercial and academic applications such as image classification [60, 50], speech recognition [7,69], machine translation [110,58], video classification [113,91] and sentiment analysis [23,13]. Moreover, they are applied in less mainstream applications such as the smart toilet [76] or to play video games [103]. Not surprisingly, evaluating deep learning algorithms on cloud servers and low power devices, in an energy-efficient manner, has become a relevant and very active research area. Evaluating deep learning applications in cloud servers is very important since many companies provide online services powered by machine learning algorithms. Services such as conversational agents (chatbots) [4,27] and grammatical analysis [39] are generally evaluated in the cloud. Moreover, applications such as semantic search [67], which is employed by banks to navigate through customer documents, and sentiment analysis [96] for brand management, are better suited to the cloud computing domain since their main target is the enterprise sector. Deep learning applications are also very relevant on low power mobile devices such as Smartphones, Smartwatches and IoT devices. On Smartphones, they can be used to create more natural human-machine interfaces that are controlled by voice [10,36]. Additionally, real-time speech trans19 CHAPTER 1. INTRODUCTION lation allows conversations between people speaking different languages. On Smartwatches, they are used to identify activities such as eating or drinking habits [108]. Finally, deep learning enables IoT devices to react and intelligently process information [100]. Deep Neural Networks (DNNs) are the main reason for the tremendous results obtained by deep learning algorithms. DNNs are composed of millions of neurons and the connections among them (i.e. synaptic weights) [65]. These weights determine the importance of the information that is being processed. Moreover, they are computed and adapted to the application domain using a training algorithm. The number of applications of deep learning algorithms on cloud servers and low power mobile devices are countless. Hence, evaluating them in an energy-efficient manner is essential to decrease inference services’ prices on the cloud. Moreover, high energy-efficiency is required to perform inference in low power mobile devices. In this regard, the evaluation of deep learning applications requires a humongous amount of memory and power, which hinder their implementation on mobile devices. For this reason, DNNs are usually evaluated in the cloud using specialized hardware architectures (i.e., accelerators) such as (TPU [51], Brainwave [29]), GPUs, or FPGAs. Nevertheless, this approach has some drawbacks. First, it requires a permanent internet connection. Therefore, it is impossible to use them if an internet connection is not available. Second, the transmission to the cloud increases the latency, which may result in unacceptable delays that violate real-time constraints. Moreover, due to the high power dissipation, performing inference on the cloud server is very costly. Finally, offloading the processing to a cloud server might result in larger energy consumption. The reason is that the communication energy per byte can be thousands to millions of times bigger than the energy per instruction [85]. There are many topologies of DNNs. However, the most common are Convolutional Neural Networks (CNNs) and Recurrent Neural Networks (RNNs). CNNs are employed on problems such as image classification [60] and human pose recognition [101]. On the other hand, RNNs have achieved tremendous success for a wide variety of sequence-to-sequence application domains [110, 113,23,7,69,54]. Recent data presented in [51] shows that RNNs account for 30% of machine learning workloads in Google’s data centers, whereas CNNs only represent 5% of the applications. The major reason for the success of RNNs is that they have loops that allow them to use information from previously processed inputs. Also, they can handle problems with variable input and output length.In this work, we focus on RNNs. More specifically, the main objective is to improve the energy-efficiency of RNN inference in hardware accelerators, while also improving their performance. The memory footprint and power requirements of RNNs are extremely large. Figure 1.1 shows the memory footprint for several state-of-the-art applications employing RNNs. As it can be seen, their sizes range from a few hundreds to several megabytes, making its deployment in small IoT devices a challenge since their memory footprint is usually in the order of kilobytes or a few megabytes. Furthermore, due to its recurrent nature, RNN inference exhibits a significant amount of sequential processing and limited parallelism. As a result, it cannot be efficiently executed on multicore CPUs, GPUs or state-of-the-art high performance accelerators for DNNs. We evaluate several RNNs applications in a modern SoC (i.e., Tegra X1) [72] and an accelerator for RNNs. Figure 1.2 shows the power consumption for several RNN applications running on these devices. For the Tegra X1 the power consumption is 4.3 watts on average. This power dissipation is 20 1.1. MOTIVATION 0 10 20 30 40 50 Video Captioning Speech Recognition Time Series Clasification Machine Translation Memory Footprint (MiB) 1 272 40 42 Figure 1.1: Memory Footprint for several RNN applications. not amenable for low power devices that are operated from a battery source. On the contrary, the power consumption of the accelerator is 330 milli-watts on average, and thus the power is reduced by 10x on average. Some applications, such as speech recognition, in addition to high accuracy also require realtime evaluation to maintain user satisfaction. However, real-time inference comes at a high energy cost. For instance, for the speech recognition network shown in Figure 1.2, the power dissipation of the SoC is extremely high, our measurements show that it does not achieve real-time performance. More specifically, the SoC takes 2.72 seconds to decode one second of speech while its power dissipation is 5.6 watts. On the contrary, it takes 0.03 seconds to decode the same audio in the accelerator and the power dissipation is 0.3 watts. Energy-efficient evaluation of RNNs in cloud servers is also challenging. In this regard, stateof-the-art accelerators such as TPU [51] and Brainwave [29], and high-end GPUs are employed to evaluate large RNN models while providing high-performance. These accelerators are generally composed of a systolic array consisting of a large number of processing elements (i.e., mac units). Due to the recurrent nature of RNNs, many computations must be serialized during their evaluation. As a result, the amount of parallelism available is limited, and processing elements are underutilized. For instance, the resource utilization for RNNs is: 18% and 3.5% for TPU and Brainwave, respectively. Also, resource utilization is moderate for GPUs. For instance, a high-end GPU (Titan V) has resource utilization ranging from 4% to 28% [112]. Besides the low resource utilization, these accelerators have a power dissipation in the order of hundreds of Watts, which increases the price of evaluating inference services on them. For instance, TPU V2 [37] and Brainwave’s power dissipation is 200W and 125W, respectively, whereas it is in order of hundreds of watts for high-end GPUs. As mentioned earlier, performing RNN inference on either cloud servers or edge devices is very challenging. For edge devices, this difficulty is due to their hardware limitations. On the contrary, offloading RNN inference to cloud servers has a high cost in performance and energy. Besides, for the high-performance accelerators commonly found in the cloud, resource utilization is very low while power dissipation is high. As shown earlier, a hardware accelerator for RNN can reduce the 21 CHAPTER 1. INTRODUCTION 0 0.1 0.2 0.3 0.4 0.5 0.6 Video Captioning Speech Recognition Time Series Clasification Machine Translation GEOMEAN Power (W) Mobile SoC Accelerator 3.2 5.6 2.9 5.1 4.3 Figure 1.2: Power dissipation for several RNN applications on a modern SoC and an accelerator. power consumption during RNN inference to milli-watts, which is amenable for cloud severs and low power devices. Therefore, we claim that hardware acceleration and energy-saving techniques are crucial in implementing RNN inference in an energy-efficient manner. Consequently, we propose a novel, highly-efficient custom architecture tailored to RNN inference. Moreover, we design several novel energy-saving techniques that further enhance the energy efficiency of our proposal. 1.2 Problem Statement, Objectives and Contributions RNNs are usually employed to solve sequence to sequence problems. In this context, an input sequence is passed to an RNN, and then it outputs the most likely sequence according to a previously learned probability distribution. Typically, an RNN is composed of millions of weights which are used during inference to compute its final output. Therefore, as outlined before, its memory footprint and power requirements are significant. Furthermore, its output is fed back to the input allowing past information to persist from one execution to the next. Hence, the evaluation of an input sequence in an RNN is strictly sequential due to the data dependencies. For this reason, an RNN cannot be efficiently executed on state-of-the-art accelerators, modern multicore CPUs or GPUs. We present detailed background information for RNNs in Chapter 2. Due to the importance of evaluating large and small RNN models in hardware accelerators, either in edge devices or in the cloud, the challenges that it carries, and the significant benefits of using an architecture tailored to RNN inference, we concentrate this thesis on hardware accelerators for RNN inference. The main objective of this thesis is to perform RNN inference on hardware accelerators in an energy-efficient manner while also improving performance. We address the problems that hinder the evaluation of RNNs efficiently by proposing novel techniques and custom architectures tailored to improve their performance and energy efficiency. First, we tackled the issue of efficiently evaluating large RNN models by offloading their execution to a custom architecture, which does not need the entire RNN model on local memory during its evaluation. Second, we overcome the problems of low 22 1.2. PROBLEM STATEMENT, OBJECTIVES AND CONTRIBUTIONS performance and high power dissipation during RNN inference by employing a highly optimized pipeline tailored to RNN computations and by improving the temporal and spatial locality of the RNN’s parameters. Third, we further enhance the performance and energy efficiency of the custom architecture by proposing two novel techniques that employ memoization and reduced precision to avoid computations and increase weight reuse. Finally, we approach the problem of low energy efficiency during the evaluation of several input sequences concurrently (i.e., RNN batching) by proposing a novel batching system that trades latency for increased weight reuse. The following sections outline the problems we are trying to solve, describe the approach we take to solve them, and highlight the novel contributions of this thesis. 1.2.1 RNN Inference on an Energy-Efficient Processing Unit Figure 1.1 shows the memory requirements of some important RNN applications. As it can be seen, the memory requirements for some models are significant, and the models cannot be deployed entirely on small IoT devices, which generally only have a few megabytes of memory storage. Note that state-of-the-art architectures for RNN inference [41,62,61] usually include local on-chip memories to improve energy efficiency, and they keep the entire RNN model locally. While this approach is very efficient energy-wise, it is only applicable to small RNN models. Consequently, an important class of RNN applications such as machine translation and speech recognition cannot be evaluated on these architectures. Other state-of-the-art proposals [17,31,43] mitigate the issue of high storage requirement by compressing the model employing reduced precision and/or pruning [43]. While these proposals support large RNN models, their approach degrades the model’s accuracy (i.e., the ability to predict correctly decreases). To address the problem mentioned above, we observe that only one RNN layer1needs to be kept on local on-chip memory at any given time since values (i.e., weights) are not reused among RNN layers. Consequently, we alleviate this problem by proposing to keep only one RNN layer on local on-chip memory during inference. This approach effectively reduces the required on-chip memory to the storage requirement of one RNN layer, which is typically not more than a few megabytes. Furthermore, the current trend is to create RNNs with several layers to increase their accuracy [26]. Therefore, the proposed solution also scales-up with the current trend. Figure 1.2 shows the power dissipation for several RNN applications running on a modern SoC. As can be seen, the power dissipation is 4.3 watts on average, which is not amenable to low power devices. Moreover, state-of-the-art proposals for RNN inference that can evaluate large RNN models have a power dissipation ranging from 10 to hundreds of watts [41,62,43,37,29]. To illustrate this problem from a user’s perspective, consider a Smartphone [9] whose battery has a capacity of 11.91 Wh. Also, assuming that it employs the RNN application for speech recognition, shown in Figure 1.2, to create a better human-to-machine interface. In this case, the power dissipation is 5.6 watts, and as a result, the operating time will decrease to 2.7 hours. Besides, the SoC has a poor performance when evaluating this model: it takes 2.72 seconds to decode one second of speech. Hence, it does not achieve real-time performance which is a requirement to ensure user satisfaction. Note that since the SoC is tailored to a broader range of applications, its performance is impacted 1In this context, an RNN layer can be viewed as an array of weights. 23 CHAPTER 1. INTRODUCTION 0 10 20 30 40 50 60 70 80 90 100 Video Captioning Speech Recognition Time Series Clasification Machine Translation AVERAGE Energy Breakdown(%) Operations Memory Accesses Figure 1.3: Energy breakdown for several RNN applications in a state-of-the-art accelerator. by the overhead due to related tasks (e.g., GPU synchronization, CPU work, etc.). Moreover, due to the RNN data dependencies, the hardware resources on the SoC are not fully utilized. To overcome the problem of high power dissipation in state-of-the-art solutions for RNN inference, we observe that most of the energy consumption is due to memory accesses to fetch the model parameters (i.e., weights). As shown in Figure 1.3, the energy consumption due to memory accesses is close to 80% on average. We solve this problem by offloading RNN inference to a hardware accelerator, that we call E-PUR, and applying several architectural optimizations to it. RNN inference involves performing several matrix-vector multiplications. Consequently, EPUR is composed of an extremely optimized pipeline to compute matrix-vector multiplications and activation functions (i.e., hyperbolic tangent). Also, it includes several on-chip memories to store one RNN layer during inference. Hence, E-PUR solves the issue of evaluating large RNN models. Moreover, it includes several on-chip memories so that when values are reused, the high energy cost of accessing the main memory is mitigated by accessing the local on-chip memories. As a result, energy consumption is reduced. In E-PUR, we approach the problem of poor performance presented in the mobile SoC by hiding memory latency (i.e., loading/storing is overlapped with computations) and reducing memory traffic. Moreover, due to the custom pipeline tailored to RNN computations, several computations that do not have data dependencies are evaluated in parallel. Our evaluations show that E-PUR reduces execution time by 6.9x, on average, compared to a mobile SoC [72]. Moreover, energy consumption is reduced by 58x on average, while the power dissipation is 500 mW. Although these results significantly improve the performance and energy consumption of RNN inference, we observe that the design can be further improved. More specifically, we observe that the RNN computations can be divided into calculations due to the input sequence and calculations due to the previous output. The computations due to the input sequence can performed in parallel, while computations that include the previous output must be evaluated sequentially. Hence, we first perform the computations involving the input sequence in parallel, and then we evaluate the computations for the previous output sequentially. We call this 24 1.4. THESIS ORGANIZATION domains. Moreover, we focus on improving energy efficiency by increasing weight reuse and reducing computations at run-time, whereas pruning is performed offline. Finally, our solutions are orthogonal to the techniques presented in [43]. MASR is another ASIC based RNN accelerator which employs pruning to improve energyefficiency [42]. This accelerator is designed to exploit the sparsity in the weights and activations. Furthermore, it avoids storing and computing null values. Moreover, it presents a co-designed technique to encode the sparse weights and activations. The principal focus of this accelerator is sparse models, whereas this thesis targets dense models. Wang et al. [107] proposes an FPGA accelerator that employs block-circulant matrices to compress the weights. By applying this technique, compression ratios of 16x can be obtained. However, the accuracy of the model is degraded. On the contrary, in this thesis we strive to propose solutions that do not degrade the original accuracy of the models. 1.4 Thesis Organization The organization for the rest of this thesis is as follows. Chapter 2 provides detailed information about RNNs. Moreover, we explain the principal RNN topologies: Long Short Term Memory and Gated Recurrent Unit. Chapter 3 presents the evaluation methodology. First, we describe the infrastructure employed to estimate energy consumption, performance, power, and area of our proposals. Second, we present the software tools used to implement and test our techniques. Finally, we describe the set of RNN workloads used in our proposals. Chapter 4 describes E-PUR, our proposal for low power RNN inference. First, we evaluate and benchmark several RNN applications to identify the main bottlenecks and sources of energy consumption. Second, we propose a highly optimized accelerator tailored to RNN inference. Finally, we describe our technique to maximize the temporal locality of the weights and improve their reuse. Chapter 5 presents our technique for computation reuse. We first analyze several RNN application to find the potential for reuse. Then, we present a novel predictor for reusability and the principal motivation behind its choice. Finally, we describe Neuron Level Fuzzy Memoization for RNNs, a technique that improves energy efficiency by reusing previous computations. Chapter 6 proposes a technique for selecting and employing lower precision dynamically. In this proposal, we analyze the impact of the precision used on the RNN state and the RNN’s accuracy. Then, we use the RNN state to identify which computations will be done using a lower precision. Finally, we describe our scheme which employs a simple, yet effective hardware solution. Chapter 7 presents a novel energy-efficient batching scheme for RNNs. Firstly, we identify the major inefficiencies in the state-of-the-art batching solutions for RNNs. Secondly, we describe our proposal to address the major issues of performing RNN batching efficiently. Finally, we show results for our schemes on top of E-PUR and TPU. 31 CHAPTER 1. INTRODUCTION Chapter 8 outlines some of the future steps and open research areas. Finally, we summarize the main conclusions of this thesis. 32 2 Background on Recurrent Neural Networks In this chapter, we provide background information on Recurrent Neural Networks. First, we present a brief overview of Artificial Neural Networks and their building blocks. Second, we briefly describe the feed-forward neural networks. Then, we offer detailed information on RNNs and their different topologies. Finally, we discuss several topics and techniques that are employed throughout this work. 2.1 Artificial Neural Networks Artificial Neural Networks (ANNs) are networks of simple processing units (i.e., neurons) whose initial design was motivated by the fact that the brain processes information in an utterly different manner than conventional digital computers [46]. However, nowadays, their design is far from their initial bio-inspired design [98]. Contrary to digital computers, the brain can learn and adapt [88]. Also, the brain can perform specific tasks such as pattern recognition and perception faster and more efficiently (i.e., energy-wise) than digital computers [46]. In theory, an artificial neural network can perform any arbitrary mapping from one vector space to another [68]. For the sake of simplicity, we refer to artificial neural networks as neural networks. Figure 2.1c shows a high-level view of a neural network; its working principle is as follows. First, the input information is received and processed by the neurons. Then, the neurons send out the processed data to the network output and/or other neurons. The relevance of the information received by a neuron is determined by its connections (i.e., synaptic weights) with the network input and/or with other neurons. Neural networks are trained for a specific task by adjusting the weights until a well-defined objective function is fulfilled, and usually, a learning algorithm such as back-propagation [47] is employed. Accordingly, the learned knowledge is stored in the connections 33 CHAPTER 2. BACKGROUND ON RECURRENT NEURAL NETWORKS          Inputs SynapticWeights Bias ActivationFunction . . . . . . (a) Artifical Neuron. (b) Sigmoid Function. (c) Artificial Neural Network. Figure 2.1: Artificial Neural Networks. Its main component is the neuron (a). A sigmoid function is commonly used as an activation function (b). An artificial neural network (c) is created combining several neurons, and thus it can be trained to identify complex patterns. of each neuron. A formal definition of an artificial neural network is provided in [46]: “An Artificial Neural Network is a massively parallel distributed processor made up of simple processing units that has a natural propensity for storing experiential knowledge and making it available for use”. 2.1.1 Artificial Neurons ANeuron is the basic computation unit of neural networks, shown in Figure 2.1a. As mentioned before, neurons are connected to external inputs or the outputs of other neurons via the synaptic weights. Then, the information received by the neurons is filtered out by the synaptic weights, as can be seen in Figure 2.1a. A neuron produces an output by summing all the filtered data acquired through its connections, and then applying an activation function (i.e., a sigmoid function, shown in Figure 2.1b ). For the rest of the thesis, we refer to the synaptic weights as weights for the sake of simplicity. Formally, the computations carried out by a neuron are shown in Equation 2.1. First, a linear combination of the neuron’s input (~x) and the weights (~w) is performed. Also, the bias (b) is added. Then, the output of the neuron (y) is computed using a nonlinear function (σ). More specifically, the primary computation performed by a neuron is an inner product (i.e., dot product) between ~x and ~w. Note that the bias term can be considered as an input with a weight whose value is one. Therefore, for the sake of simplicity, we omit the bias for the rest of the thesis. y=σ(X~w~x +b) (2.1) 2.1.2 Feed-forward Neural Networks Neural Networks can be classified into two categories: Feed-forward Multi-Layer Perceptrons (MLPs) and Recurrent Neural Networks (RNNs). MLPs do not have feedback from their output towards their inputs. On the contrary, RNNs include feedback loops. Although in this work we 34 2.1. ARTIFICIAL NEURAL NETWORKS (a) Single-layer Feed-forward Neural Network. (b) Multi-layer Perceptron (MLP). Figure 2.2: MLPs are composed of millions of neurons arranged by layers. The layers between the input layer and the output layer are called hidden layers. All the layers in both figures are fully-connected. focus on RNNs, feed-forward neural networks are presented in this section since they are an essential building block of RNNs. A feed-forward MLP is composed of many neurons organized in different layers [68]. Figure 2.2a shows a feed-forward neural network with only one layer, a.k.a. perceptron, whereas an MLP is shown in Figure 2.2b. The layers between the input and the output layer are called hidden layers. Note that the input layer does not perform any computation, and thus it is not included when counting the number of layers in a neural network. For instance, the number of layers of the neural network shown in Figure 2.2b is three: the output layer (Softmax) and two hidden layers (Dense #1 and Dense #2). The current trend in MLPs is to create very deep networks with many layers to increase recognition accuracy. The reason is that neural networks with a large number of neurons (i.e., a wide network) and networks with a small number of hidden layers (i.e., a shallow network) are excellent at memorization. Consequently, they cannot generalize, whereas deep neural networks can capture richer structures [26]. Generally, the layers of a neural network where every neuron in the layer is connected to the output of every neuron in the previous layer is called a fully-connected layer. Moreover, neural networks where all the layers are fully-connected are called fully-connected networks [88]. Otherwise, they are called partiallyconnected networks. Formally, the computations carried out by a fully-connected layer are shown in Equation 2.2. They are defined as a matrix-vector multiplication between Wand ~x. The rows of the weight matrix Wcontain the connections for each neuron in the layer, whereas ~x is the output vector of the previous layer (i.e., one element per neuron of the previous layer). Note that Wfor fully-connected layers is a dense matrix, whereas it is a sparse matrix for partially-connected layers. As with neurons, for the sake of simplicity, we omit the bias 35 CHAPTER 2. BACKGROUND ON RECURRENT NEURAL NETWORKS a) One to one b) One to many c) Many to one d) Many to many e) Many to many Figure 2.3: Modeling sequence to sequence problems with RNNs. In each sub-figure, blue rectangles correspond to inputs, violet rectangles to outputs, and green boxes to the RNN cell. (a) This is the typical case solved by standard feed-forward networks. (b) Sentiment analysis and video classification are tasks in which a sequence is mapped to one output vector. (c) Applied to problems such as image captioning and text generation where the input is a vector. (d) This configuration has been used for machine translation tasks in which the input and output sequences may have varying and different lengths. e) This architecture has been used for predicting at each step the following character in a sentence. vector for the rest of the thesis. ~y =σ(W~x +~ b) (2.2) MLPs are trained by adjusting the weight matrix of each layer. Typically, a variation of the back-propagation algorithm, such as ADAM [57] or RMSprop [84], is employed during training. In this work, we focus on inference; thus, we do not detail the training process of neural networks. 2.2 Recurrent Neural Networks RNNs provide a start-of-the-art solution for sequence to sequence problems. Unlike feedforward neural networks, RNNs include loops, which allows them to use a vast amount of context information during inference. In this section, we provide background information on RNN and the motivation behind its different topologies. First, we present a brief description of sequence to sequence problems. Second, the vanilla RNN and deep RNNs are described. Then, we detail the Long Short Term Memory (LSTM) and Gated Recurrent Unit (GRU) architectures. Finally, we review Bi-directional RNNs. 36 2.2. RECURRENT NEURAL NETWORKS 2.2.1 Sequence to Sequence Problems Sequence to Sequence problems involve mapping an input sequence (e.g., audio frames, a sentence) of one or more elements to another sequence, which can also have one or more elements [66, 97]. RNNs are suitable for this kind of problem because they do not require an input or output sequence with fixed length [66]. Also, due to the recurrent connections, they can learn short and long temporal and spatial dependencies on the input data [97]. Figure 2.3 shows several sequence to sequence models. Sentiment analysis and video classification can be modeled with Figure 2.3b, whereas Image captioning could be represented as in Figure 2.3c. Moreover, problems where the input and output sequence have a variable length are modeled as in Figure 2.3d. On the contrary, problems such as language modeling (i.e., the input and output sequence have the same length) are modeled as in Figure 2.3e. Note that Figure 2.3a is the traditional application where feed-forward neural networks are used. 2.2.2 Vanilla RNN Cell and Deep RNNs Vanilla RNN Cell Figure 2.4a shows the most basic architecture of an RNN, commonly referred as Vanilla RNN cell [109,97]. The input (i.e., X) to a vanilla RNN cell is a sequence of real value vectors, i.e., [~x1, ~x2, ...~xN] where Nis the number of elements in the input sequence. Similarly, the output (i.e., Y) is also a sequence of real value vectors, i.e. [~y1, ~y2, ...~yM] where Mis its length. Note that Nis not necessarily equal to M. Conventionally, an element of the input sequence (i.e., ~xt) is called a time-step [66]. As Figure 2.4a shows, a vanilla RNN cell (RNN cell for simplicity) includes forward connections and recurrent connections (also called feedback connections). The forward connections operate on ~xt(i.e., the current time-step of the input sequence). On the other hand, the recurrent connections work on ~yt−1(i.e., the output of the RNN cell on the previous time-step). Figure 2.4b shows an unrolled RNN cell which is evaluated sequentially for each time-step of the input sequence, i.e., (x1) to (xN). In the unrolled view of the network, recurrent connections are shown as horizontal connections. Note that these horizontal connections correspond in fact to connections from the output of one cell to the input of the same cell. Conceptually, the forward and recurrent connections can be defined as two independent fullyconnected layers (without the activation function) whose weight matrices are Wand U, respectively. Also, note that Wand Ualways have an identical number of rows and columns. Formally, the output of an RNN cell is computed according to Equation 2.3. As seen in Equation 2.3, to compute the output of an RNN cell for a time-step ~xt, two matrix-vector multiplications are done: one between the forward connections Wand the current time-step ~xt, and the other between the recurrent connections Uand the previous output ~yt−1. Then, the results of these two multiplications are added together. Finally, to compute the output ~yt, the result of this summation (~ ht) is fed to an activation function which is usually a hyperbolic tangent (φin Equation 2.3) for Vanilla RNN cells. 37 CHAPTER 2. BACKGROUND ON RECURRENT NEURAL NETWORKS U W  ℎ  W  ℎ  W  ℎ  W  ℎ  UU U … Unroll U a) Vanilla RNN Cell b) Unrolled RNN Cell Figure 2.4: Vanilla RNN cell. Its output is a function of the current time-step xtand the previous output yt−1. The figure in the right shows the cell unrolled for an input sequence X= [x1, x2, .., xN]. ~ ht=W~xt+U~yt−1+~ b ~yt=φ(~ ht)(2.3) Regarding neurons, note that the activation function is applied to ~ ht. Hence, conceptually, an element (nk) of the vector ~ytcan be viewed as the output of a neuron since it follows to the definition of neuron given in 2.1.1. Therefore, for RNNs, the output of neuron nkis computed by adding the result of the inner product between row ~wk(i.e., forward connections) and the current time-step ~xt, to the result of the inner product between row ~uk(i.e., recurrent connections) and the previous output ~yt−1. Also, consider that when stating the number of neurons in an RNN, it refers to the dimensionality of ~yt. Thus, it is equal to the number of rows in the matrix containing the recurrent or forward connections. Finally, some works used the term units instead of neurons. However, throughout this thesis we use the term neuron unless it is explicitly stated otherwise. Finally, since RNN computations are mostly done using vectors and matrices, we refer to a given vector (~x) just as (x) for the sake of readability. Regarding the input sequences, since RNN cells are employed in a plethora of applications from different domains, the elements of an input sequence must be encoded as a real-value vector (e.g., a hot vector). Moreover, for some applications such as sentiment analysis [23], the input sequences do not have an explicit temporal component (i.e., words in a sentence); nonetheless, the convention is to call every single element on an input sequence a time-step. We follow this convention in this thesis. Deep RNN Deep RNNs are created by stacking together several RNN cells in a layered manner. In the context of deep RNNs a layer consists of one or more RNN cells. Similar to deep feed-forward 38 2.2. RECURRENT NEURAL NETWORKS Encoding RNN Cell 1 Softmax     Encoding Encoding Encoding RNN Cell 1 RNN Cell 1 RNN Cell 1 RNN Cell 2 RNN Cell 2 RNN Cell 2 RNN Cell 2 Softmax Softmax Softmax     Figure 2.5: Deep RNN employed to translate an English sentence to German. First, words are encoded into a real value vector. Then, they are processed sequentially for each RNN cell. neural networks, deep RNNs include an input layer, one or more hidden layers, and an output layer. Figure 2.5 shows an unrolled Deep RNN with two hidden layers. In this logical view of the network, recurrent and forward connections are shown as horizontal and vertical links, respectively. Therefore, the output of a given RNN cell is used as input to the next RNN cell in the same time-step (forward link), but also as input to the same RNN cell in the next time-step (recurrent link). As an example, Figure 2.5 shows the process of translating an input sentence from English to German using a deep RNN. As it can be seen, each word in the input sentence is first encoded as a vector (e.g., ~xt, a one-hot vector). Then, each of the encoded-words (i.e., a time-step) is passed to the first RNN layer, which evaluates them sequentially from x1to x4. Note that the output of evaluating a time-step is fed to the upper layer and also used when processing the next input word. Once the first layer is evaluated for all the time-steps, the same process is followed for the rest of the hidden layers. Finally, the output of the last RNN cell is given to a Softmax function that generates a probability distribution of the most likely words. Finally, output word for each time-step is selected using either a greedy approach or a beam search [110]. As mentioned in 2.1.2, the primary motivation for deep neural networks is that they are better at generalizing than shallow networks [26]. For instance, consider the machine translation model [110], which translate sentences from English to German. When the model is configured with four RNN cells and 1024 neurons, its accuracy is 19 Bleu [74]1. However, increasing the number of RNN cells to 8 raises the model accuracy to 26 Bleu. On the contrary, doubling the number of neurons does not increase the model accuracy. Vanilla RNNs can capture and exploit short term dependencies in the input sequence. However, capturing long term dependencies is challenging since useful information tends to dilute over time [15,48]. To exploit long term dependencies, Long Short Term Memory (LSTM) [48] and Gated Recurrent Units (GRU) [20] networks were proposed. These types of RNNs represent the 1It is a metric for evaluating a generated sentence to a reference sentence. It works by counting matching n-grams in the candidate translation to n-grams in the reference text. The larger the Bleu, the better. 39 CHAPTER 2. BACKGROUND ON RECURRENT NEURAL NETWORKS xt ht-1 gt it xtht-1 Σ ft xtht-1 Cell State Ct-1 ot xtht-1 Ø Ct ht Figure 2.6: Structure of an LSTM cell. denotes an element-wise multiplication of two vectors. φ denotes the hyperbolic tangent. most successful and widely used RNN architectures. In the next subsections, we describe their architecture and formal model. 2.2.3 Long Short Term Memory Cell Figure 2.6 shows the structure of an LSTM cell. Contrary to a Vanilla RNN cell, an LSTM cell has a memory storage. Moreover, the flow of information going in or out of an LSTM cell is modulated. The critical component of an LSTM cell is the cell state, i.e. ct, a vector that is stored in the cell memory. Moreover, an LSTM cell has four gates that are used to build the cell state and to control the output of the cell. In this context, a gate is a multiplicative node which is composed of two independent fully-connected layers operating on the forward and recurrent connections, respectively. The gates in an LSTM cell control how the information is added or removed from the cell state. More specifically, for an input sequence (X), the cell state is updated by three of the gates in the following manner. First, the updater gate (gt, whose computations are shown in Equation 2.4c) modulates the amount of input information that is considered a candidate to update the cell state. Then, the input gate, (it, Equation 2.4a) decides how much of the candidate information will be added to the cell state. On the other hand, the forget gate (ft, Equation 2.4b) determines the amount of information to be erased from the previous cell state (ct−1). Once these three gates are evaluated, the cell state is updated according to Equation 2.4d. Similarly, the output gate (ot, Equation 2.4e) decides the amount of information that will be emitted from the cell to create the output (ht). it=σ(Wixt+Uiht−1) (2.4a) ft=σ(Wfxt+Ufht−1) (2.4b) 40 3 Experimental Methodology In this chapter, we detail the methodology that is followed during this work. First, we present the simulator and tools that we employ to simulate and implement our proposals. Then, we describe our benchmarks and the methodology that we follow to evaluate the impact of our proposals in terms of accuracy. 3.1 Hardware Simulation Infrastructure The standard methodology employed to model hardware architectures tailored to RNN acceleration involves using cycle-level simulators to estimate timing and activity factors. Moreover, pipeline components are implemented in Verilog and synthesized for a given technology to estimate their energy consumption, timing and area. Finally, the total execution time, energy consumption and power of the accelerator are estimated by combining the results from the cycle-level simulator and the synthesis process. In this work, we model two RNN accelerators: E-PUR and TPU. 3.1.1 E-PUR To model E-PUR, we implemented a cycle-level simulator in Python. This simulator estimates the execution time of an RNN model running on top of it by accurately modeling each of the hardware components of E-PUR’s pipeline. At each execution cycle, the dynamic activity of each pipeline component is calculated and recorded. Note that the behavior and memory access pattern of RNNs is very predictable, and thus many pipeline components are simulated using an analytical model. After a simulation is completed, the simulator provides the total execution time and overall energy consumption (dynamic and static) of the accelerator. Furthermore, it provides the power 47 CHAPTER 3. EXPERIMENTAL METHODOLOGY Table 3.1: Hardware parameters for E-PUR. Parameter E-PUR Technology 32 nm Frequency 500 MHz Intermediate Memory 1.5 MB Weights Memory 2 MB per CU Inputs Memory 8 KB per CU DPU Width 16 operations MU Operations cycles: 2 (ADD), 4 (MUL), 5 (EXP) MU Communication 2 cycles Peak Bandwidth 30 GB/s dissipation and the dynamic activity of each pipeline component. Note that the simulator only estimates the execution cycles and the activity factors. To determine timing and energy consumption, it combines the energy and timing estimations obtained using the following tools. Regarding the latency, area and power dissipation of each of the individual pipeline components, we implement them in hardware by creating their RTL description in Verilog. Then, we use Synopsys Design Compiler [99] to synthesize each pipeline component employing a 32 nm technology library. The compiler reports the power dissipation (static and dynamic ) and the critical-path delay. We use a typical process corner with a voltage of 0.78V, and an average switching activity is used to estimate dynamic power. Moreover, to estimate the energy consumption and delay of the memory components (i.e., buffers and scratch-pad memories) of E-PUR, we use CACTI selecting energy-delay as the optimization function. Finally, to estimate the timing and energy consumption of the main memory we employ MICRON’s power model [70]. We model 4 GB of LPDDR4 DRAM. Regarding the clock frequency, we use the delays reported by Synopsys Design Compiler and CACTI [71] to set the frequency such that most hardware structures operate on a single clock cycle. We also evaluate alternative frequency values to minimize energy consumption. Table 3.1 shows the standard hardware configuration of E-PUR. However, note that in some of our proposals, we use a slightly different configuration as a baseline. For each of our proposals, we detail the modifications done to the baseline in the corresponding chapter. 3.1.2 TPU-like architecture To model a TPU-like architecture, we use the SCALE-Sim [87,86] simulator with the configuration parameters shown in Table 3.2. We employed an output stationary dataflow [87,19]. The number of filters is set to the number of neurons in the model. Also, the input features are set to the number of weights per neuron. On the other hand, the width and height of the filters are set to one, whereas the width of the input features is set to the batch size. Pipeline components are modeled using the methodology that was described for E-PUR. Also, the energy consumption and timing is estimated in a similar manner. 48 3.2. GPU EVALUATION Table 3.2: Configuration of TPU-like accelerator. Parameter Value Frequency 700 MHz SRAM Buffer 24 MiB Systolic Array PEs 128x128 Dataflow Output Stationary Table 3.3: Tegra X1 parameters. Parameter Value CPU 4-core ARM A-57 GPU 256-core Maxwell GPU Streaming Multiprocessors 2 (2048 threads/proc) Technology 20 nm Frequency 1.0 GHz CPU L2 Cache 2 MB GPU L2 Cache 256 KB Peak Bandwidth 25.6 GB/s 3.2 GPU Evaluation For comparison purposes, we use an NVIDIA Tegra X1 SoC [72] whose parameters are shown in Table 3.3. Its energy consumption is measured by reading the registers of the Texas Instruments INA3221 power monitor included in the Jetson TX1 development board [72], as outlined in [30]. Furthermore, we only use the energy consumption of the GPU. Regarding the software implementation of the networks, we implemented them using high-level APIs (as explained in the next section). Then, to perform inference on the Jetson TX1, we rely on cuDNN [11], a GPU-accelerated and highly optimized library of primitives for DNNs. 3.3 Functional Evaluation and Benchmarks The machine learning community offers a variety of software frameworks tailored to the implementation of deep learning models. Some software frameworks such as Keras [21] and PyTorch [79] have a very user-friendly API, whereas frameworks such as TensorFlow [2] work at a lower level of abstraction. All of them use the Python programming language to implement the models and a highly optimized back-end library, such as cuDNN [11] or cuBLAS [1], to perform computations. We use several of these frameworks in this work since our benchmark models are based on open source projects from different companies and research groups. Our benchmarks include RNN models from different application domains. They have a different number of RNN layers and neurons. Moreover, they have either LSTM or GRU cells, and some of them include bidirectional layers. On the other hand, the length of the input sequence is also different for each RNN, and it ranges from 20 to a few thousand time-steps. Finally, we used the 49 CHAPTER 3. EXPERIMENTAL METHODOLOGY test and train sets provided with each network during our experiments. Regarding the functional evaluation of a model’s performance, we employ the term accuracy to refer to how good or bad an RNN model is at predicting correctly the outputs. However, several metrics are used in the machine learning community to measure the performance of a model. Also, we use the term accuracy loss to refer to the fact that the accuracy of a model is worse than its baseline accuracy. To evaluate the impact that our proposals may have on the accuracy of a given model, we implemented them on top of the original model. More specifically, for a given RNN model, we develop our techniques using its framework and compare the new accuracy against the baseline accuracy to measure potential accuracy loss. In the next subsections we present a brief overview of each of our benchmark models and the metrics employ to determine their accuracy. Moreover, we show their characteristics in Table 3.4. 3.3.1 Accuracy Metrics of the Benchmarks A variety of metrics are employed in the Machine Learning community to measure the accuracy of a DNN model: how good or bad a DNN model it is when performing a given task. In the next subsections, we describe the accuracy metrics used by the benchmarks evaluated in this thesis. Top-N Accuracy Top-N is an accuracy metric commonly employed in classification problems to measure the ratio of correct predictions over the total number of instances evaluated. Note that in classification problems, the predicted class is selected based on a probability distribution outputted by a Softmax function. In this case, the correct class could correspond to one of the top N predictions (i.e., the N classes with highest probabilities). Hence, for Top-N accuracy, a prediction is considered correct if it corresponds to one of the top N classes of the Softmax distribution. For instance, top-5 means that the right class corresponds to one of the five classes with highest probabilities outputted by the Softmax function. Bilingual Evaluation Understudy (Bleu) The Bleu [74] score is an accuracy metric typically used in problems that generate an output sentence such as machine translation and video captioning. Bleu compares a generated sentence to one or more reference sentences. The comparison is made by counting matching n-grams (usually up to 4-grams) in the generated sentence to n-grams in the reference sentences. Then, a weighted averaged of the matching n-grams is computed. The Bleu score is a value between 0 and 1, but it is generally multiplied by one hundred. A value of one indicates that the generated sentence matches precisely one of the reference sentences. In contrast, a score of zero shows no matching between the generated and the reference sentences. Therefore, a higher Bleu score is considered better. 50 3.3. FUNCTIONAL EVALUATION AND BENCHMARKS Word error rate (WER) Word error rate (WER) is a standard metric of the performance of a speech recognition system. It works by counting the number of insertions plus deletions plus substitutions required to convert the recognized word sequence into the reference word sequence, divided by the total number of words of the reference word sequence. Lower WER is considered better. 3.3.2 Benchmark RNN Models IMDB Model The IMDB Model [23] is employed to predict the user sentiment about a movie based on an input review. The final output of the model tells whether the user gave a positive or negative review. As dataset, it uses movie reviews from the IMDB movie database. Regarding its parameters, it has 1 LSTM layer and 128 neurons. On the other hand, the input sequences have a fixed length of 80 time-steps. For this model, the accuracy metric used is top-1 accuracy. Its baseline accuracy is 86.5%. Finally, it is implemented in Python using the Keras library. DeepSpeech2 DeepSpeech2 [7] is a speech recognition system for different languages. In our evaluations, we employ the Librispeech [73] dataset, which contains more than 900 hours of speech from audiobooks. Speech models for Librispeech are trained with a large vocabulary of 200K words. Since the input sequences to this model are usually composed of audio frames of 10ms, they tend to have a large length, which ranges from 100 to 2000 time-steps. The DeepSpeech2 implementation used in our evaluations contains 5 GRU cells, and each one of them has 800 neurons. For this model, the baseline accuracy is 10.24 WER (Word Error Rate). Regarding the software implementation, we implemented it on Python and used the trained model (weights) from the original paper. EESEN EESEN [69] is another speech recognition system for the English language. It uses the Tedlium [83] dataset, that is collected from TED talks and consists of spontaneous speech in a noisy environment. It is trained with a vocabulary of 150K words. Similar to DeepSpeech2, the input sequences range from a few hundred to 2000 time-steps. The EESEN model is composed of 5 BiLSTM layers, each one containing 320 neurons. In this model, the baseline accuracy is 23.8 WER. For the software implementation, we used the open-source model from the original paper, which is written in C++. 51 CHAPTER 3. EXPERIMENTAL METHODOLOGY Table 3.4: RNN Networks used for the experiments. Network App Domain Cell Type Layers Neurons Accuracy Dataset IMDB Sentiment [23] Sentiment Classification LSTM 1 128 86.5% (Top-1) IMDB dataset DeepSpeech2 [7] Speech Recognition GRU 5 800 10.24 WER LibriSpeech EESEN [69] Speech Recognition BiLSTM 10 320 23.8 WER Tedlium V1 GNMT [110] Machine Translation LSTM 8 1024 29.8 Bleu WMT’15 En→Ge SHOW TELL [104] Image Description LSTM 3 512 32.2 Bleu MSCOCO Google Machine Translation (GNMT) GNMT [110] is an RNN model for machine translation proposed by Google. It is based on seq2seq [97] architecture, which is composed of an encoder and a decoder. Both the decoder and decoder consist of BiLSTM and LSTM layers. In total, this model has 10 LSTM layers and 1024 neurons per layer. Our evaluations are based on the English to German dataset (WMT’15 En→Ge) [16]. For this model, the input sequences are sentences, and their number of time-steps ranges from 20 to 100. Moreover, this model is implemented in TensorFlow. Finally, it has a baseline accuracy of 29.8 Bleu. Showtell Showtell [104] is an RNN model for image description, i.e. it generates a textual description of the action in an image. It is composed of 3 LSTM layers, each one containing 512 neurons. It is implemented in TensorFlow and employs the MSCOCO [64] dataset, which includes thousands of images. The input sequences in these models range from 20 to 100 time-steps. Finally, it has an accuracy of 32.2 Bleu. 52 4 Energy-Efficient Processing Unit In this chapter, we describe E-PUR, an energy-efficient processing unit tailored to RNN inference. E-PUR is our proposal to overcome the problem of supporting large RNN models while providing real-time performance with an energy consumption amenable for low power devices. First, we describe our approach to evaluate RNNs on a custom architecture. Second, we detail the overall architecture of E-PUR and its pipeline. Third, we describe our technique to maximize weight locality. Finally, we present the experimental results and conclusions. 4.1 RNN inference on E-PUR State-of-the-art hardware implementations [41,43,62,61] for RNNs rely on storing the synaptic weights on-chip in order to avoid expensive off-chip memory accesses. Commonly, there are two possible approaches to compute the output of an RNN given an input sequence (X= [x1, x2, .., xN]): vertical or horizontal computations. Vertical computations refer to the case where the final output of the RNN for time-step (xt) is computed before proceeding with the next time-steps. More specifically, time-step (xt) is evaluated for all the RNN layers, and then the evaluation proceeds to time-step (xt+1). One drawback of this approach is that, unless the entire RNN model is kept locally in on-chip memory, the temporal locality of the weights is severely affected since the entire weight matrices for the forward and recurrent connections of each RNN layer must be fetched from main memory for each time-step of the input sequence. Therefore, this approach is inefficient energy-wise. Another drawback is that it only works for unidirectional RNN layers, since for a bi-directional RNN layer its input is a composition of the output from the previous layer evaluated for the forward and backward pass. For example, to evaluate time-step (x1) in the second layer of a deep RNN model, we need the output from layer 1 evaluated for x1in the forward pass and the output for xNin the backward pass. 53 CHAPTER 4. ENERGY-EFFICIENT PROCESSING UNIT 0 5 10 15 20 0 40 80 120 BYSDNE RLDRADSPR EESEN LDLRNN GMAT Decrease in Footprint (x) Memory Footprint (MB) Memory footprint for all weights on-chip Decrease in memory footprint (1 cell on-chip) 272 1.03 Figure 4.1: Amount of memory required to store the synaptic weights on-chip for several LSTM networks. Right y-axis shows the reduction in storage requirements obtained by keeping a single cell on-chip. Regarding horizontal computations, they are done by first evaluating a whole layer for all the time-steps of the input sequence before proceeding with the evaluation of the next layer. Note that if the weights of a given layer are kept locally in on-chip memory, they can be reused to evaluate each time-step of the input sequence without the need to access the main memory multiple times. Hence, this approach is effective energy-wise, and we employ it on E-PUR. A drawback of this approach is that several intermediate results are generated since the output of a given layer for each time-step must be stored, as it will be used to compute the next RNN layer. We describe in section 4.2 the solution employed to mitigate this problem. As described above, storing the entire RNN model on-chip is unfeasible for many RNN applications due to their large memory requirements to achieve high accuracy. For instance, the GMAT [110] RNN model for machine translation requires more than 256 megabytes of memory, as we can see in Figure 4.1. To alleviate this problem, we propose a cost-effective trade-off between main memory accesses and on-chip memory storage. It is based on the observation that the input sequences of RNN networks tend to contain a large number of elements and that to evaluate a given RNN layer horizontally, only the weights for that particular layer are used when computing the whole input sequence. We exploit this characteristic of RNNs to design the memory system of E-PUR, providing on-chip memory capacity to store only the weights of a single RNN layer. Note that, as seen in Figure 4.1, the storage requirements are reduced by 7x on average, although this comes at the expense of higher off-chip memory traffic. Nonetheless, this trade-off is necessary to support larger and deeper models since keeping them on-chip is unfeasible due to their large memory footprint. Also, to further reduce memory footprint weights and input sequences are converted to a lower precision (i.e., 8-bits) using linear quantization. 54 4.2. E-PUR PROCESSING UNIT CU: Forget Gate CU: Cell Updater Gate CU: Input Gate OM: Intermediate Results CU: Output Gate           Figure 4.2: Overview of E-PUR architecture, which consists of four computation units (CU) and an on-chip memory (OM) for intermediate results. Each CU is mapped to one of the gates in an LSTM cell. However, a similar mapping is done when evaluating GRU cells. 4.2 E-PUR Processing Unit 4.2.1 Overview Figure 4.2 shows the main components of E-PUR. It is composed of four computation units (CUs), which have several communication links among them. Each of these four hardware units is tailored to the computation of one of the four LSTM gates (i.e., forget gate, input gate, cell updater gate, and output gate), as shown in Figure 4.2. The reason for this one-to-one gate-to-CU mapping is that exchanging information between LSTM gates is not needed for most of the cell state computation. Regarding the mapping of the gates on a GRU cell, it is done in the following manner. The update gate is mapped to the CU tailored to the LSTM’s input gate. On the other hand, the reset gate is assigned to the CU for the LSTM’s forget gate. Finally, the GRU cell’s new hidden state is computed on the CU, which is tailored to the LSTM’s update gate. Note that the CU employed to evaluate the LSTM’s output gate is not used when evaluating GRU cells, but it can be power gated so it does not drain any power. E-PUR is designed to deliver the highest efficiency for LSTM networks, as they represent by far the most popular RNN architecture, but it is flexible enough to support GRU networks. The computations on a gate of an RNN cell are mainly dominated by the calculation of the matrix-vector multiplications detailed in Sections 2.2.3 and 2.2.4. Note that each gate performs exactly two matrix-vector multiplications (i.e., two dot products for each neuron) per time-step of the input sequence and, therefore, the total computation is well balanced among the gates. However, a minimal amount of information is shared among CUs at the end of the cell state calculation to gather the necessary data for its update. As shown in Figure 4.2, for an LSTM cell both input and forget gates send their result to the cell updater gate, whereas the output gate consumes the result 55 CHAPTER 4. ENERGY-EFFICIENT PROCESSING UNIT 0 20 40 60 80 100 0 1 2 3 BYSDNE RLDRADSPR EESEN LDLRNN GMAT Reduction in accesses to Main Memory (%) Normalized Energy Intermediate results in on-chip memory Intermediate results in main memory Reduction in accesses to main memory Figure 4.3: Total energy consumption by storing intermediate results in on-chip memory versus main memory. Right y-axis shows the reduction in accesses to main memory. produced in the cell updater gate. Moreover, after the cell updater gate updates the cell state, the new cell state value is sent to the input and forget gates. Note that the hidden state of a GRU cell is computed in a similar manner. For the rest of this chapter, we describe the operations performed by E-PUR on an RNN cell employing an LSTM cell as an example. However, note that the same principles apply to GRU cells since their computations are very similar to the LSTM’s calculations. In E-PUR, an RNN model is evaluated horizontally (i.e., one layer after the other) for a given input sequence. Thus, the intermediate results produced by one layer for an entire input sequence must be saved in memory because of the data dependencies. There are two main alternatives to store this information: a dedicated on-chip memory (OM) or main memory. In Figure 4.3, we show the normalized energy consumption and the reduction in accesses to the main memory for some LSTM applications using both approaches. As we can observe, using a dedicated onchip memory consumes, on average, 2.4x less energy than storing/loading the intermediate results continuously to/from main memory since, on average, 77% of the accesses to main memory are avoided. Therefore, this is the adopted solution in E-PUR. This dedicated on-chip memory is divided into two parts of equal size. One part is used to store the output results produced in the current layer, and the other one is used to keep the results produced in the previous layer. 4.2.2 Computation Unit The Computation Unit is the hardware structure that implements the formal model of an RNN cell, described in Equations 2.4 and 2.5. It is composed of two main components: the Dot Product Unit (DPU) and the Multifunctional Unit (MU). The DPU, shown at the top of Figure 4.4, performs the necessary dot product operations in a gate, which is the most time-consuming part. Note that our design employs dot products over matrix-matrix multiplications to simplify the hardware. Also, since the weights and input sequences are quantized, dot products are computed using integer operations. The MU, shown at the bottom of Figure 4.4, performs the rest of operations, such as activation functions and linear quantization. These operations are evaluated using floating point arithmetic. In addition to these components, two memory buffers are used to store the input sequence and the synaptic weights for each gate in the RNN cell. Note that the same weights are reused for each recurrent execution of an RNN cell. 56 4.4. EXPERIMENTAL RESULTS 0 10 20 30 40 50 60 BYSDNE RLDRADSPR EESEN LDLRNN GMAT GEOMEAN Energy Reduction (x) EPUR EPUR+MWL 144 211 157 223 88 Figure 4.7: Energy reduction of E-PUR with respect to the Tegra X1. 0 20 40 60 80 100 EPUR EPUR+MWL EPUR EPUR+MWL EPUR EPUR+MWL EPUR EPUR+MWL EPUR EPUR+MWL EPUR EPUR+MWL BYSDNE RLDRADSPR EESEN LDLRNN GMAT AVERAGE Energy Breakdown (%) Leakage operations Leakage scratchpad memories Dynamic energy operations Dynamic energy scratchpad memories Dynamic energy Main Memory Figure 4.8: Energy breakdown for E-PUR and E-PUR+MWL. for E-PUR+MWL. Note that the energy consumption due to scratchpad memories is not reduced by 50% since there is an increase in memory accesses to the on-chip memory for intermediate results. In the case of the leakage due to on-chip memories, after applying MWL, it is reduced by 44% on average. This saving comes from the reduction in storage requirements to store the weights for the forward connections. Regarding the energy consumption due to the operations, it ranges between 1% and 3% of the total energy for both configurations. Henceforth, after applying MWL the energy consumption is reduced by 33.4% on average. Figure 4.9 shows the speedups for different LSTM networks. On average, the speedup achieved by E-PUR over Tegra X1 is 6.8x. E-PUR performance improvements come from hiding memory latency (i.e, loading/storing is overlapped with computations), reducing off-chip memory accesses, and featuring a custom pipeline tailored to LSTM computation. Regarding E-PUR+MWL, there is no performance improvement against the baseline since the order in which MWL evaluates the neurons does not change the final execution time. Note that in MWL the number of operations to evaluate a given neuron is equal to the number of operations for the conventional order. However, because the evaluation of the recurrent connections for a given neuron is postponed until all forward connections are evaluated, the latency to evaluate a single neuron increases but the latency to produce the final output sequence does not change. Finally, for speech recognition applications, E-PUR achieves real-time performance by a large margin, running 30x and 5x faster than real-time for EESEN and RLDRADSPR respectively. 63 CHAPTER 4. ENERGY-EFFICIENT PROCESSING UNIT 0 2 4 6 8 10 12 14 BYSDNE RLDRADSPR EESEN LDLRNN GMAT GEOMEAN Speedup (X) EPUR +MWL Figure 4.9: Speedups achieved by E-PUR over Tegra X1. 0 0.2 0.4 0.6 0.8 1 BYSDNE RLDRADSPR EESEN LDLRNN GMAT GEOMEAN Power(W) Tegra X1 EPUR EPUR+MWL 3.2 5.5 5.6 2.9 5.1 4.3 Figure 4.10: Power dissipation for E-PUR, E-PUR+MWL, and Tegra X1. 0 25 50 75 100 EPUR EPUR+MWL Area Breakdown (%) On-Chip Memory for Intermediate results On-Chip Memory for Weights Operations Figure 4.11: Normalized Area breakdown for E-PUR and E-PUR+MWL. On the other hand, power dissipation is shown in Figure 4.10, which includes the total power for Tegra X1 and the two configurations of E-PUR. As it can be seen, E-PUR+MWL dissipates about 10x lower power than Tegra X1 on average. Regarding area, E-PUR requires a total area of 31.3 mm2, whereas the total area of EPUR+MWL is 22 mm2. As depicted in Figure 4.11, the component with larger contribution to the total area is the on-chip memory for the synaptic weights, which is reduced by 48.6% when MWL is applied. Note that with MWL the memory requirements to store intermediate results increase. Hence, the overall saving in area due to MWL is 30%. Finally, Figure 4.12 shows the speedup and energy reduction of the Tegra X1+MWL, i.e. MWL implemented in software, with respect to the baseline. On average, it provides 7.8% speedup, 64 4.5. RELATED WORK 0 0.5 1 1.5 2 2.5 BYSDNE RLDRADSPR EESEN LDLRNN GMAT GEOMEAN Normalized Values (x) Energy Reduction Speedup Figure 4.12: Speedup and normalized energy achieved by Tegra X1+MWL over Tegra X1. increasing energy consumption by 25%. Overall, Tegra X1+MWL achieves better performance than the baseline but since the on-chip memories of Tegra X1 are fairly smaller than the ones included in E-PUR, the effectiveness of Tegra X1+MWL for RNNs is constrained due to the increase in off-chip memory traffic. As a result, the baseline implementation consumes less energy than Tegra+MWL. 4.5 Related Work Proposals for LSTM networks acceleration have been presented in [43,41,62]. Although these accelerators achieve higher performance per watt than CPUs and GPUs, they are not designed for low-power mobile devices since their power dissipation ranges from 19 W to 41 W. However, E-PUR dissipates a peak power of 330 mW, which is amenable for low-power mobile devices. Chang et al. [17] present a low-power accelerator targeting the mobile segment. It implements a small LSTM network (2 layers, 128 neurons) and dissipates 1.9 W. In this work arithmetic operations are done using fixed-point Q8.8 data format, thus an accuracy loss of 7.1% is aggregated. On the contrary, E-PUR uses 8-bit linear quantization to store the weights, matrix multiplications are perform using integer operations, and it does not aggregate accuracy loss. In addition, E-PUR supports larger network models for a wide variety of application domains. Note that scaling up the aforementioned accelerator presented in [17] to support larger LSTM networks would require a significant increase in local storage capacity or in main memory traffic, and both alternatives would come at a high overhead in energy consumption. Another low-power LSTM accelerator is presented in [61], this system consumes 9 W and supports larger models by using aggressive weight quantization. External DRAM traffic is completely avoided by storing the quantized weights in a local on-chip memory of 2 Mbytes. However, this quantization comes at the expense of non-negligible accuracy loss. For speech recognition, Word Error Rate increases from 13.5%, using 32-bit floating point, to 15.1% and 20.2% when using 6bit and 4-bit quantization respectively. Furthermore, larger and more accurate models cannot be stored in its local memory even with the 4-bit quantization. For example, EESEN requires more than 5 Mbytes when using 4 bits per weight. E-PUR uses 8-bit quantization to reduce memory footprint with not impact on accuracy. TPU is another state-of-the-art accelerator for neural networks [51]. It includes a systolic array of processing elements (PEs) and on-chip memory for weights and activations. TPU is mainly 65 CHAPTER 4. ENERGY-EFFICIENT PROCESSING UNIT tailored to CNNs, and thus it has low hardware resource utilization (i.e., 18%) when evaluating RNNs. On the contrary, E-PUR has nearly 100% hardware resource utilization. Furthermore, TPU’s power dissipation is 200 watts [37], whereas E-PUR has a peak power dissipation of 330mW. Recently, Edge TPU [38], a low power version of TPU, has been proposed. It is tailored to CNNs and fully-connected networks, whereas this work focuses on RNNs. Edge TPU dissipates 0.5 watts for each TOPS. BrainWave [29] is a highly optimized accelerator targeting DNNs. In this accelerator, matrixmatrix multiplications are performed using a vast array of matrix-vector multipliers. Similar to E-PUR, BrainWave includes multi-functional units to compute activation functions. However, as TPU, BrainWave’s resource utilization is only 3.5% when evaluating RNNs. On the contrary, EPUR achieves nearly 100% utilization. Finally, its peak power computation is 125W, which is not amenable to low power devices. Regarding pruned RNNs, MASR [42] is an RNN accelerator tailored to sparse models. It employs pruning to improve energy-efficiency. Also, it does not store or compute null values. ESE [43] and EIE [44] are another RNN accelerators for sparse models. ESE targets speech recognition applications, whereas EIE targets image captioning. Also, EIE is tailored to CNNs. Both of these proposals employed aggressive pruning to reduce the model size. On the contrary, E-PUR focuses on dense models and maximizes weight locality to improve energy efficiency. Moreover, E-PUR is designed to support applications from several domains. Regarding the work in [19], E-PUR without MWL is similar to a weight stationary architecture applied to LSTMs since it loads all weights for given layer in on-chip memory, holding them until all associated computations are performed. However, MWL is different since it aims at further reducing the reuse distances. Unlike traditional weight stationary architectures, MWL splits synaptic weights in two types: forward and recurrent. Based on the observation that forward connections can be processed in any order, whereas recurrent connections impose sequential processing due to data dependencies. Therefore, MWL evaluates forward connections in the order that maximizes temporal locality, requiring extra small on-chip storage for this stage, whereas it processes all recurrent connections on a second stage as shown in Figure 4.6. MWL greatly reduces the energy consumption of the baseline accelerator. Finally, cuDNN [11] has been recently extended to efficiently support RNN training. E-PUR design is significantly different in multiple ways. First, cuDNN focuses on RNN training with large batch sizes, whereas E-PUR focuses on RNN inference with batch size of one, i.e. one input sequence at a time. We measured cuDNN performance for RNN inference with batch size of one and found that E-PUR achieves 6.8x speedup. cuDNN effectiveness is reduced due to the small batch size commonly used for RNN inference. Furthermore, cuDNN’s optimizations to execute multiple layers in parallel cannot be applied to bidirectional LSTMs due to data dependencies. 4.6 Conclusions In this chapter, we present E-PUR, a processing unit for RNNs that supports large RNN networks while dissipating low-power, motivated by the increasingly important role of RNN networks 66 4.6. CONCLUSIONS in applications such as speech recognition, machine translation and video classification. Unlike previous proposals that attempt to accommodate the entire RNN on-chip, E-PUR only provides storage for one RNN layer, whose weights are fetched once from main memory and reused for multiple recurrent executions. To further improve the memory efficiency of E-PUR, we introduce Maximizing Weight Locality (MWL), a novel technique that improves the temporal locality of the synaptic weights. Moreover, we implement MWL in software to analyze the benefits of a softwareonly implementation The proposed design supports large LSTM and GRU networks of hundreds of Megabytes, while using small on-chip storage and low memory bandwidth. Our results show that E-PUR reduces energy consumption by 88x on average with respect to a modern mobile GPU, while providing 6.8x speedup. 67 5 Neuron-Level Fuzzy Memoization In chapter 4, we presented E-PUR, an accelerator for RNN inference which provides high performance and energy efficiency. Although the energy savings and performance improvements of E-PUR are significant, we observe that the primary source of energy consumption is still the access to the local on-chip memories of E-PUR, which account for up to 80%. In this case, most of the memory accesses are done to fetch the weights when computing the output of a given neuron. In this chapter, we explore computation reuse techniques with the aim of avoiding accesses to the on-chip memories. More specifically, we leverage a memoization scheme where the output of a neuron is cached and reused in future evaluations, skipping the corresponding memory accesses and computations. Memoization is a well-known optimization technique used to improve performance and energy consumption that has been used both in software [3] and hardware [35]. In some applications, a given function can be executed repeatedly but the inputs to those executions are not always distinct. Memoization exploits this fact to avoid these redundant computations by reusing the result of a previous evaluation. In general, the first time an input is evaluated, the result is cached in a memoization table. Subsequent evaluations probe the memoization table and reuse previously cached results if the current input matches a previous execution. In a classical memoization scheme, a memoized value is only reused when it is known to be equal to the real output of the computation. However, for some resilient applications such as multimedia [6], graphics [12], and neural networks [116], this scheme can be extended to tolerate a small loss in accuracy with negligible impact in the quality of the results, and is normally referred to as fuzzy memoization. In this work, we leverage fuzzy memoization to avoid neuron evaluations selectively and, hence, to avoid their corresponding memory accesses and computations. For fuzzy memoization to be effective, applications must be tolerant of small errors, and its hardware implementation must be 69 CHAPTER 5. NEURON-LEVEL FUZZY MEMOIZATION simple. In the next sections, we show that RNNs are resilient to minor errors in the outputs of the neurons. Also, we provide an efficient implementation of a fuzzy memoization scheme that requires simple hardware support. First, to assess the feasibility of memoizing the previous output of a given neuron, we analyze the output of millions of neurons in several RNN models to determine how much the output of a neuron changes between the evaluation of consecutive time-steps. Note that for each application run, an RNN layer is executed many times to process an input sequence, which normally contains a large number of time-steps (i.e., words, images, audio frames). From this analysis, we observe that after evaluating a neuron for consecutive time-steps, its output exhibits small changes, 23% on average. Motivated by the previous observation, we perform a second analysis to establish the potential for reusing previous computations, and thus to avoid them so that energy efficiency is improved. The results of this analysis show that the potential for reuse is between 20% and 50% with a negligible impact on the model accuracy. Therefore, we exploit this observation to build a fuzzy memoization scheme, which dynamically caches each neuron’s output and reuses it whenever it is predicted that the current output will be similar to a previously computed result, avoiding the computations and the memory access for some neurons. In the rest of this chapter, we describe our analyses and present our fuzzy memoization scheme. The organization is as follows. First, we detail a study of the neurons’ output in several RNN models and show that reuse is between 20% and 50%. Second, we describe our motivations for fuzzy memoization in RNNs. Then, we present our memoization scheme. Finally, we detail the experimental results and conclusions. 5.1 Analysis of Potential for Computation Reuse As mentioned in Chapter 2, neurons in an RNN are recurrently executed for each of the timesteps in the input sequence X. Moreover, for a time-step (xt) the output of neuron nkis computed by adding the result of the inner product between the forward connections and xt, to the result of the inner product between the recurrent connections and the previous output of the neuron yt−1. In this regard, the relative difference (δ) between the output of nkbetween consecutive time-steps xtand xt−1is defined as follows. δ= yt−yt−1 yt(5.1) In this chapter, we aim to reuse computations by caching the previous output of a neuron (ym) and reusing it when we determine that it is similar to the current one (yt). The similarity between ymand ytis defined as their relative difference (δ) which is computed using Equation 5.1. In the next subsection, we experimentally show that there is a high degree of similarity between the current and previous output of some neurons and that for some evaluations, a previously computed output could be reused with a negligible impact in the model accuracy. 70 5.1. ANALYSIS OF POTENTIAL FOR COMPUTATION REUSE 0 10 20 30 40 50 60 70 80 90 100 Cummulative % of neurons (%) 0 10 20 30 40 50 60 70 80 90 100 Relative Ouput Difference (%) EESEN Deepspeech Machine Translation IMDB Sentiment Figure 5.1: Relative change in neuron output between consecutive time-steps. 5.1.1 RNNs Redundancy and Reuse Potential Memoization schemes rely on a high degree of redundancy in the computations. For RNNs, a key observation is that the output of a given neuron tends to change lightly between consecutive time-steps. Note that RNNs are used in sequence processing problems such as speech recognition or video processing, where RNN inputs in consecutive time-steps tend to be extremely similar. Prior work in [82] reports high similarity across consecutive frames of audio or video. Not surprisingly, our own numbers for our set of RNNs also support this claim. Figure 5.1 shows the relative difference between consecutive outputs of a neuron in our set of RNNs. As it can be seen, a neuron’s output exhibits small changes (less than 10%) for 25% of consecutive input time-steps. On average, consecutive outputs change by 23%. Furthermore, RNNs can tolerate small errors in the neuron output [116]. This observation is supported by data shown in Figure 5.2, where the accuracy curve shows the accuracy loss when the output of a neuron is reused using fuzzy memoization, for different thresholds (x-axis) that control the aggressiveness of the memoization scheme. For the study shown in Figure 5.2, we implemented the memoization scheme described in Equations 5.2, 5.3, and 5.4 . For this scheme, the relative error (δ) between a predicted neuron output (yp t) and a previously cached neuron output (ym) is used as the discriminating factor to decide whether the previous output is reused, as shown in Equation 5.2. For this memoization scheme, the predicted value is provided by an Oracle predictor, which is 100% accurate (i.e., its prediction is always equal to the neuron output (yp t=yt)). We employ this approach to evaluate the potential benefits of memoization in RNNs. As shown in Figure 5.2, neurons can tolerate a relative output error between 0.3 and 0.5 without significantly affecting the overall network accuracy (i.e., accuracy loss smaller than 1%). On the other hand, the reuse curve shows the percentage of neuron computations that could be avoided through this memoization with an Oracle predictor. Note that by allowing neurons to have an output error between 0.3 to 0.5, at least 30% of the total network computations could be avoided. 71 CHAPTER 5. NEURON-LEVEL FUZZY MEMOIZATION 0 0.1 0.2 0.3 0.4 0.5 0.6 Threshold 0 2 5 10 15 20 WER Loss (%) 0 10 20 30 40 50 60 70 80 Computation Reuse (%) DeepSpeech WER Loss Computation Reuse 0 0.1 0.2 0.3 0.4 0.5 0.6 Threshold 0 2 5 10 15 20 WER Loss (%) 0 10 20 30 40 50 60 70 80 Computation Reuse (%) EESEN WER Loss Computation Reuse 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Threshold 0 5 10 15 20 25 Accuracy Loss (%) 0 10 20 30 40 50 60 70 Computation Reuse (%) IMDB Sentiment Accuracy Loss Computation Reuse 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Threshold 0 2 5 10 15 Bleu Loss (%) 0 10 20 30 40 50 60 Computation Reuse (%) Machine Translation Bleu Loss Computation Reuse Figure 5.2: Accuracy loss of different RNNs versus the relative output error threshold using an oracle predictor. If the difference between the previous and current output predicted is smaller than the threshold, the memoized output is employed instead of calculating the new one. δ= yo t−ym yo t(5.2) yt=(ymif δ <=θ yo totherwise, (5.3) ym=(yo tif δ > θ not updated otherwise, (5.4) Figure 5.3: Neuron Level memoization with Oracle Predictor. ytis the neuron output. ymcorresponds to the memoized evaluation and yo tis the output of the Oracle predictor. δ,θare the relative error and the maximum allowed output error respectively. Finally, to achieve significant savings, a memoization scheme must add a small overhead to the system. In our case, the critical challenge is approximating the behavior of the Oracle predictor with simple hardware that decides when memoization can be safely applied with a minor impact on overall RNN accuracy. We describe an effective solution in the next section. 72 5.4. EXPERIMENTAL RESULTS Table 5.1: Configuration Parameters for E-PUR+BM. E-PUR Parameter Value Technology 28 nm Frequency 500 MHz Intermediate Memory 6 MiB Weight Buffer 2 MiB per CU Input Buffer 8 KiB per CU DPU Width 16 operations Memoization Unit BDPU Width 2048 bits Latency 5 cycles Integer Width 2 bytes Memoization Buffer 8 KiB The proposed fuzzy memoization technique for RNNs is implemented on top of E-PUR and we refer to it as E-PUR+BM. First, we detail the percentage of computation reuse and the accuracy achieved. Second, we show the performance and energy improvements, followed by an analysis of our technique’s area overheads. Figure 5.11 shows the percentage of computation reuse achieved by the BNN and the Oracle predictors. The percentage of computation reuse indicates the percentage of neuron evaluations avoided due to fuzzy memoization. For accuracy losses smaller than 2%, the BNN obtains a percentage of computation reuse extremely similar to the Oracle. The networks EESEN and IMDB are highly tolerant to errors in neuron’s outputs, thus, for these networks, our memoization scheme achieves reuse percentages of up to 40% while having an accuracy loss smaller than 3%. Note that, for classification problems, BNNs achieve an accuracy close to the state-of-the-art [80] and, hence, it is not surprising that the BNN predictor is highly accurate for approximating the neuron output. For DeepSpeech (speech recognition) the reuse percentage is up to 20% for accuracy losses smaller than 2%. In this network, the input sequence tends to be large (i.e, 900 elements on average). As the reuse is increased, the error introduced to the output sequence of a neuron persists for a larger number of elements. Therefore, the introduced error will have a larger impact both in the evaluation of the current layer, due to the recurrent connections, and the following layers. As a result, the overall accuracy of the network decreases faster. For MNMT (machine translation) the BNN predictor and the oracle achieve similar reuse versus accuracy trade-off for up to 23% of computation reuse. Note that, for this network, the linear correlation between the BNN and the full precision neuron output is typically lower than for the other networks in the benchmark set. Figure 5.12 shows the energy savings and computation reuse achieved by our scheme, for different thresholds of accuracy loss. For a conservative loss of 2%, the average energy saving is 25.5%, whereas the reuse percentage is 31%. In this case, the networks DeepSpeech and MNMT show similar energy savings, whereas the networks IMDB and EESEN exhibit the largest savings since they are more tolerant to errors in the neuron output. For an extremely conservative 1% of accuracy loss, the computation reuse and energy saving are 24.2% and 18.5% on average respectively. EESEN and DeepSpeech achieve 25.32% and 12.23% energy savings respectively for a 1% accuracy 79 CHAPTER 5. NEURON-LEVEL FUZZY MEMOIZATION 0 10 20 30 40 50 60 70 Computation Reuse (%) 0 2 5 10 15 20 25 WER Loss (%) Oracle predictor Binary Network predictor 0 10 20 30 40 50 60 70 Computation Reuse (%) 0 2 5 10 15 20 25 WER Loss (%) EESEN Oracle predictor Binary Network predictor 0 10 20 30 40 50 60 70 80 Computation Reuse (%) 0 2 5 10 15 20 Accuracy Loss (%) IMDB Sentiment Oracle predictor Binary Network predictor 0 10 20 30 40 50 60 Computation Reuse (%) 0 2 5 10 15 20 Bleu Loss (%) Machine Translation Oracle predictor Binary Network predictor Figure 5.11: Percentage of computations that could be reused versus accuracy loss using Fuzzy Neuron Level Memoization with an Oracle and a Binary Network as predictors for several RNNs. 10 15 20 25 30 35 40 IMDB EESEN DEEPSPEECH MNMT AVERAGE IMDB EESEN DEEPSPEECH MNMT AVERAGE IMDB EESEN DEEPSPEECH MNMT AVERAGE 1% Accuracy Loss 2% Accuracy Loss 3% Accuracy Loss Percentage (%) Energy Savings Computation Reuse 45 49 Figure 5.12: Energy savings and computation reuse of E-PUR+BM over the baseline (E-PUR). loss. Regarding the machine translation network (MNMT), the energy savings for 1% and 2% accuracy loss are 15.17% and 23.46% respectively. Regarding the sources of energy savings, Figure 5.13 reports the energy breakdown, including static and dynamic energy, for the baseline accelerator and E-PUR+BM, for an accuracy loss of 1%. The sources of energy consumption are grouped into on-chip memories (”scratch-pad” memories), pipeline components (”operations”, i.e. multipliers), main memory (LPDDR4) and the energy consumed by our FMU component. Note that most of the energy consumption is due to the scratch-pad memories and the pipeline components and, as it can been seen, both are reduced when 80 5.5. RELATED WORK 0 10 20 30 40 50 60 70 80 90 100 EPUR EPUR+BM EPUR EPUR+BM EPUR EPUR+BM EPUR EPUR+BM IMDB EESEN DEEPSPEECH MNMT Energy Breakdown (%) Operations On-Chip Memories Main Memory FMU Energy Figure 5.13: Energy breakdown for E-PUR and EPUR+BM. using our memoization scheme. In E-PUR+BM, each time a value from the memoization buffer is reused, we avoid accessing all the neuron’s weights and the input buffers, achieving significant energy savings. In addition, since the extra buffers used by E-PUR+BM are fairly small (i.e. 8 KB), the energy overhead due to the memoization scheme is less than 3% on average. The energy consumption due to the operations is also reduced, as the memoization scheme avoids neuron’s computations. Furthermore, the leakage of scratch-pad and operations are also reduced due to the speedups achieved by the memoization scheme. Finally, the energy consumption due to accessing main memory is not affected by our technique since both, E-PUR and E-PUR+BM, must access main memory to load all the weights once for each input sequence. Figure 5.14 shows the performance improvements for the different RNNs. On average, an speedup of 1.35x is obtained for a 1% accuracy loss, whereas accuracy losses of 2% and 3% achieve improvements of 1.5x and 1.67x respectively. The performance improvement comes from avoiding the dot product computations for the memoized neurons. Therefore, the larger the degree of computation reuse the bigger the performance improvement. Note that the memoization scheme introduces an overhead of 5 cycles per neuron (see Table 5.1), mainly due to the evaluation of the binarized neuron. In case the full precision neuron evaluation can be avoided, our scheme saves between 16 and 80 cycles depending on the RNN. Therefore, configurations with low degree of computation reuse, like Deepspeech at 1% accuracy loss, exhibit smaller speedups due to the overhead of the memoization scheme. On the other hand, RNNs that exhibit higher computation reuse, such as EESEN at 2% accuracy loss, achieve an speedup of 1.55x. E-PUR has an area of 64.6 mm2, whereas E-PUR+BM requires 66.8 mm2(4% area overhead). The largest overhead contribution (3%) is due to the extra scratch-pad memory required by the memoization unit. 5.5 Related Work Increasing energy-efficiency and performance of RNN networks has attracted the attention of the architectural community in recent years [43,62,41,61]. Most of these works employ pruning and compression techniques to improve performance and reduce energy consumption. Furthermore, 81 CHAPTER 5. NEURON-LEVEL FUZZY MEMOIZATION 1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 IMDB EESEN DEEPSPEECH MNMT AVERAGE IMDB EESEN DEEPSPEECH MNMT AVERAGE IMDB EESEN DEEPSPEECH MNMT AVERAGE 1% Accuracy Loss 2% Accuracy Loss 3% Accuracy Loss Speedup 2.25 1.9 Figure 5.14: Speedup of E-PUR+BM over the baseline (E-PUR). linear quantization is employed to decrease the memory footprint. On the contrary, our technique improves energy-efficiency by relying solely on computation reuse at the neuron level. To the best of our knowledge, this is the first work using a BNN as a predictor for a fuzzy memoization scheme. BNNs have been used previously [22,80,56] as standalone networks, whereas we employs BNNs in conjunction with the RNN to evaluate neurons on demand. Fuzzy memoization has been extensively researched in the past and has been implemented both in hardware and software. Hardware schemes to reuse instructions have been proposed in [95, 5,35,12]. Alvarez et al. [6] presented a fuzzy memoization scheme to improve performance of floating point operations in multimedia applications. In their scheme floating point operations are memoized using a hash of the source operands, whereas in our technique a whole function (neuron inference) is memoized based on the values predicted by a BNN. Finally, software schemes to memoize entire functions have been presented in the past [111,3]. These schemes are tailored to general purpose programs whereas our scheme is solely focused in RNN , since it exploits the intrinsic error tolerance of RNNs. 5.6 Conclusions In this chapter, we have shown that about 25% of neurons in an RNN change their output value by less than 10%. This motivated us to propose a fuzzy memoization scheme to save energy and time. A major challenge to perform neuron level fuzzy memoization is to predict, in a simple and accurate manner, whether the output of a given neuron will be similar to a previously computed and cached value. To this end, we propose to use a Binarized Neural Network (BNN) as a predictor, based on the observation that the fully precision output of a neuron is highly correlated with the output of the corresponding BNN. We show that a BNN predictor achieves 24.2% computation reuse on average, which is very similar to the results obtained with an Oracle predictor. The experimental results show that our memoization scheme achieves significant time and energy savings with minimal impact in the accuracy of the RNNs. When compared with the E-PUR accelerator, our scheme achieves 18.5% energy savings on average, while providing 1.35x speedup at the expense of a minor accuracy loss. 82 6 Dynamic Precision Selection In previous chapters, the performance and energy efficiency of RNN inference is improved either by changing the order of computations or avoiding them. In this chapter, we follow a different approach by focusing on the precision (bit-width) used to perform the calculations. More specifically, we explore the use of dynamic precision selection during RNN inference. As mentioned earlier, RNN models tend to require a large amount of memory for storage. In this regard, linear quantization is one of the most popular and effective optimizations employed to reduce the storage requirements of RNN models. Linear quantization maps floating-point values to the product of an integer index and a quantization step, as detailed in Section 2.3.1. Therefore, the parameters and inputs are commonly stored as integer values, and the computations are performed using integer arithmetic [51,19,43]. For this reason, energy efficiency and performance are also significantly improved since it reduces the amount of energy required for computations and memory accesses. Traditionally, when linear quantization is employed, the bit-width is set to the minimum precision that can retain the original model’s accuracy based on an offline profiling, and it is kept constant during RNN inference. For instance, RNN accelerators such as E-PUR and TPU [51] use 8-bit weights and inputs for RNN inference. Other proposals, such as Stripes [52] and Bit Fusion [92], support variable precision to further improve performance and energy efficiency for RNN layers that can be computed with less than 8 bits. Despite the additional flexibility of these accelerators, the bit-width for each RNN layer is determined offline, and it is fixed during inference. In other words, different RNN layers can be evaluated at different precision, but a given layer is always computed at the same bit-width for all the inputs. In this chapter, we propose a mechanism to dynamically select the precision used during the evaluation of a neuron aiming to boost performance without any accuracy loss. 83 CHAPTER 6. DYNAMIC PRECISION SELECTION A major challenge to select the precision dynamically is deciding when to change precision. We observe that for RNNs, the cell state can be useful as it stores information from previous inputs that will be used for future predictions. Therefore, we investigate a practical scheme to set the bit-width online based on the cell state. In the rest of this chapter, we go over the motivations for employing dynamic precision. Then, we present an analysis of the importance of the cell state when deciding the precision to be used. In the later sections, we describe our proposal for dynamic precision selection. Finally, we detail our experimental results and conclusions. 6.1 Benefits of Dynamic Precision Selection RNN cells are composed of four gates, each one of them with two matrices containing the weights for the forward and the recurrent connections, respectively. Since these weight matrices tend to be quite large, most of the energy consumed by state-of-the-art hardware accelerators for RNN inference is due to the static and dynamic energy consumed by the memories employed to store the weights and intermediate results. An effective way to decrease memory footprint and thus static and dynamic energy without affecting accuracy is using Linear Quantization (see Chapter 2). Typically, a static profiling of the network is done to determine the minimum precision that can be used to quantize an RNN model without losing accuracy. A common approach is to set a fix bit-width (i.e., 8 bits) for the whole network. However, while this solution covers the worst case, it ignores cases where a lower precision could be employed for a subset of computations without losing accuracy. Figure 6.1 shows the accuracy loss of an RNN model for speech recognition [69] when using 8 bits, 4 bits, and a mix of both. In the case of the mixed-precision, for each neuron (e.g., inputs and weights), we dynamically set the precision to 8 or 4 bits as described later in Section 6.3.1. As shown in Figure 6.1, using a precision of 8 bits (i.e., assuming worst-case bit-width for the whole network) results in no accuracy loss. On the contrary, using a precision of 4 bits incurs in 2% of accuracy loss (which is an important loss for speech recognition). However, it can be observed that more than 50% of the computations can be evaluated using 4 bits while the rest are computed using 8 bits without losing accuracy. Previous works have reported and exploited variability in the precision requirements for DNN computations [52,53]. However, they exploited precision variability across layers, whereas in this work, we focus on precision variability among neurons and time-steps of execution, which is a much finer-grain variability. In other words, prior proposals support different precision for different DNNs, but the precision for each DNN and layer is determined offline and kept constant during inference. Our proposal is different as we dynamically select the precision for each neuron and time-step. Regarding the benefits of dynamic precision selection, they are shown in Figure 6.1. Employing 4-bits precision to evaluate all time-steps reduces the execution time to 50% of the 8-bit version. However, it would introduce a significant degradation to the model accuracy. Our scheme, illus84 6.2. IMPORTANCE OF THE CELL STATE 0 0.5 1 1.5 2 0 0.5 1 1.5 2 8 Bits 4 Bits 8/4 Dynamic Accuracy Loss (%) Speedup Ideal Speedup Accuracy Loss Figure 6.1: Speedup and accuracy loss for a speech recognition LSTM network [69] using different schemes to set the precision. 8 Bits and 4 Bits are configurations that fix the precision to 8 and 4 bits respectively for all the time-steps. 8/4 Dynamic is our scheme for dynamically selecting the precision at run-time, which employs 4 bits for stable regions of the cell state and 8 bits for peak regions. As it can be seen, our dynamic scheme outperforms the 8 bits version without any accuracy loss. trated in the second bar, restricts the use of 4-bit quantization to certain regions of the cell state, representing around 66% of the time. In contrast, the remaining regions are computed using 8 bits. By doing so, we leverage 4-bit quantization for a large percentage of the execution, while avoiding any accuracy loss. A primary challenge to dynamically change the precision is deciding when to use a high or low precision. In this work, we propose to use the state of the cell state as an indicator of the required precision. We describe the rationality behind this decision in the next section. 6.2 Importance of the Cell State The cell state is a critical component of an RNN cell as it stores the cell information. As described in Section 2.2.3, it consists of an array of N elements, where several neurons from different gates are employed to compute each element, i.e. the gates behave as fully-connected layers. Furthermore, we use the term cell state to refer to the hidden state (ht) of GRU cells and the cell state (ct) of LSTM cells. Figure 6.2b shows the evolution of one element in the cell state in a speech recognition network [69], at three different levels of precision (32-bit floating-point, 8-bit integer, and 4-bit integer). As it can be seen, 8-bit quantization closely tracks the behavior of the 32-bit full-precision version, resulting in the same accuracy. However, 4-bit quantization introduces significant errors in some time-steps, resulting in noticeable accuracy loss. Previous schemes would conclude that this LSTM network layer cannot be evaluated using 4 bits. However, a more detailed look at Figure 6.2 reveals that the 4-bit version can mimic the behavior of the 32-bit version for a large percentage of timesteps. More specifically, for phases where the cell state is stable the 4-bit version is quite accurate, whereas for phases where the cell state changes rapidly, i.e., peaks/valleys, it tends to exhibit a larger error. A more extensive analysis by using different LSTM networks and their respective training datasets shows that this behavior is quite prevalent. For stable phases, the 4-bit version introduces an error of 19.6%. On the other hand, for peaks/valleys, it introduces a larger error of 85 CHAPTER 6. DYNAMIC PRECISION SELECTION LSTM 1 LSTM 2 LSTM 1 LSTM 2 LSTM 1 LSTM 2        Cell State          … …  …   LSTM 3 LSTM 3 LSTM 3 ℎ (a) Cell state vector update 0 10 20 30 40 50 60 70 Timestep -3 -2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3 3.5 Cell State Cell State Value for "neuron 1" of layer 1 4 Bits 8 Bits 32 bits 8/4 Dynamic Stable region Peak region Peak region (b) Cell state for element n1 Figure 6.2: Evolution of one element (n1) in the cell state of a speech recognition LSTM network [69]. As shown in (a), on each time-step, the elements in the cell state vector are updated using a combination of the gates’ output and the previous cell output. Also, for each LSTM layer, the cell state is different, and the last layer’s output on each time-step is used to generate the output sequence. Shown in (b) is the cell state for element n1of the cell state, i.e. it plots the value of cell state element c1for different precision levels. As it can be seen, in stable regions the low precision (4-bit version) evaluation accurately tracks the behavior of the high precision (FP32) version. However, a large error is introduced when the tracked element is on a peak. 78% on average. For brevity, we will use the term peak to refer to both peaks and valleys. Based on this observation, we propose a scheme that dynamically selects the appropriate precision by monitoring the cell state of the RNN cell. Our system keeps track of the values of each element in the cell state in recent time-steps. If the value is inside a stable region, the lowest precision supported by the hardware is selected to evaluate the next time-step. Otherwise, higher precision is used (8 bits) to avoid significant errors during the peak regions. In our set of RNN models, this simple scheme allows us to use the lowest precision for more than 56.2% of the time without any accuracy loss. Note that our scheme dynamically changes the precision for all the elements of the cell state individually. Consequently, at each time-step, some neurons are evaluated using high precision, whereas the rest are evaluated using low precision. As shown in Figure 6.2b, the value of the cell state when applying our scheme (labeled 8/4 dynamic in the figure) follows the cell state of the 32-bits version closely. Note that, in the peak regions, the error of 8/4 dynamic is smaller than the error of the 4-bits version. In summary, we design a scheme that tracks the evolution of the cell state at run-time. Then, for each of its elements, it selects a high precision during the peaks and a low precision for stable regions. For this work, we use 8 bits for the high precision since it provides zero accuracy loss for all tested RNN models. On the other hand, we use 4 bits for the lower precision, which would have a significant loss in accuracy if it was used for all the time-steps. Regarding the range of values of the weights, we have noted the presence of outliers, as previously explored in [75]. As in [75], by quantizing the outliers using high precision (i.e., 8 bits), the remaining values could be quantized more aggressively (i.e., using lower precision) without affecting 86 6.3. DYNAMIC PRECISION SCHEME  I Gate G Gate F Gate O Gate Cell State Vector Select Bit-Width 8/4  ℎ   ∗  ∗  ∗   ,  ,  ,    ∗  Figure 6.3: Relationship among neurons in the four gates and elements in the LSTM cell state. The value Ctkof element nkis computed based on the outputs of the kth neuron in each of the four gates. The precision used to evaluate those neurons is based on the evolution of the element nk. Based on the selected bit width, xtand wkare quantized to xqand wk q, respectively. the overall accuracy of the network. Therefore, in this work, we follow a similar approach where outliers are quantized using higher precision than the rest of the values. In the following sections, we detail this scheme and describe its hardware implementation on top of E-PUR. For brevity, we based our explanations on an LSTM cell. However, the same principles apply to GRU cells. 6.3 Dynamic Precision Scheme 6.3.1 Overview Our principal goal is to set the precision at each time-step of execution for the input vectors xtand ht−1and their corresponding weights for each single element of the cell state individually. For a given LSTM cell, the kth element of the cell state vector is computed using a combination of the output value of the kth neuron on each gate. We refer to these four neurons simply as element nkof the LSTM cell and set the precision for the four of them in tandem, since all of them are associated with the same element of the cell state. This relationship is shown in Figure 6.3. To determine when each element nkof the cell state is on a peak, we employ the state machine depicted in Figure 6.4. To track the evolution of the value of the cell state (ck) of a given element nk, we divide the process into three phases. First, the system starts in a profiling state that samples ckfor a certain number of time-steps. This profiling is done in order to determine the peak characteristics of ck. Then, we have the stable state that indicates that ckhas had a stable value for the previously evaluated time-steps. Finally, the in-a-peak state tracks when ckis at a peak. As shown in Figure 6.4, the profiling state is performed for Ttime-steps. In each profiling step, we keep track of the maximum and minimum value of the cell state. Note that the profiling is done using low precision (4 bits) because we assume that while profiling the cell state is inside a stable region. Finally, after Ttime-steps, we use the maximum and minimum value of ckto set the limit values that define when a peak begins or ends, and then we move to the stable state. 87 CHAPTER 6. DYNAMIC PRECISION SELECTION Profiling  = 4 Stable  = 4 In-a-Peak  = 8  = 0  = −∞  = ∞  ≥  -------------------  = 0  <  ---------------------------------- = max(maxC, C) = min ,   + +  ≥  ----------------------------------- (, )  = 0  ≥  -------------------  = 0  < &&() ------------------------------------------  + +   -------------------  = 0   -------------------  = 0  < &&() -------------------------------------------  + + Figure 6.4: State machine employed to dynamically select the precision for an element ckof the cell state. r=maxCk−minCk(6.1) upperLimit =r+r∗β(6.2) lowerLimit =r−r∗β(6.3) isInPeak =lowerLimit ≤ck≤upperLimit (6.4) Figure 6.5: Positive and negative peak region definition for the cell state of a given neuron (i.e., nk). The system remains in the stable state until a peak is detected. A peak is found using the values minCkand maxCk, obtained previously in the profiling state, as shown in Figure 6.5. To determine that the value in the cell state has entered a peak, we require that it exceeds the minCk and maxCkfound during the profiling stage by a given margin to increase the confidence of the detection. To this end, we use the parameter βin Equation 6.2 and Equation 6.3 to establish the upper and lower thresholds. If the ckvalue in the cell state exceeds one of these thresholds, a peak is detected, and the system transitions to the in-peak-state to use high precision. It remains in this state until we detect that ckis no longer in a peak using Equation 6.4. In case that the end of the peak is detected, we move to the stable state to switch back to low precision, as the value of the cell state has entered a stable phase. If the system stays in a peak for a large number of time-steps (e.g., Min Figure 6.4), the profiling stage is triggered again. Note that this profiling is needed since the value of ckmay 88 6.5. EXPERIMENTAL RESULTS Table 6.1: Hardware Configuration. E-PUR Parameter Value Technology 28 nm Frequency 500 MHz Intermediate Memory 6 MiB Weight Buffer 2 MiB per CU Input Buffer 8 KiB per CU DPU Width 16 operations MU Latency 20 cycles LQ Latency 8 cycles MU Communication 2 cycles Outlier Buffer 128KiB Peak Detector Buffer 8 KiB State Machine Configuration M 5% of time-steps N 5% of time-steps β0.1 datasets. For our experiments, the baseline system is E-PUR using 8-bit parallel multipliers, labeled as E-PUR+PAR. We evaluate our scheme on top of E-PUR using SIP and parallel multi-precision multipliers. The system implementing our dynamic precision selection scheme and SIP units is labeled as SIP+DYN. In contrast, the system with the multi-precision multipliers and our technique is marked as PAR+DYN. The rest of this section is organized as follows. First, we present an evaluation of the effectiveness of our scheme. Second, we provide the performance and energy results. Third, we evaluate our scheme using three levels of precision (8, 4, 2). Finally, we analyze the area overheads of the proposed scheme. Figure 6.11 reports the effectiveness of using the cell state stability to set the precision dynamically. In this figure, we compare our proposal with a scheme that randomly selects the precision level for each element of the cell state at each time-step. The random scheme has a low precision usage of 34% on average, i.e., 34% of the evaluations are performed at low precision (4 bits) whereas 66% are done at high precision (8 bits). However, the random scheme produces a significant loss in accuracy for all the networks. On the other hand, our scheme has a 49% low precision usage on average, without any accuracy loss. Therefore, tracking the stability of the LSTM cell state provides valuable information to select the precision. Note that the IMDB model can be evaluated using only 4-bits for both approaches. Figure 6.12 shows the performance improvements for our set of RNN networks. On average, a speedup of 1.46x is obtained without any accuracy loss. SIP+DYN and PAR+DYN exhibit the same speedup since both of them have the same throughput and they operate at the same frequency. 95 CHAPTER 6. DYNAMIC PRECISION SELECTION 0.0 1.0 2.0 3.0 4.0 5.0 0 10 20 30 40 50 60 70 DEEPSPEECH EESEN SHOW TELL MNMT Accuracy Loss (%) Low Precision Usage (%) Low Precision Usage Random Low Precision Usage Peaks Accuracy Loss Employing Peaks Accuracy Loss Employing Random Figure 6.11: Comparison between our scheme (“Peaks”) and a system that randomly chooses the evaluations done at low precision (“Random”). The random scheme produces a significant degradation in accuracy. Our scheme achieves higher coverage without any accuracy loss. 1.0 1.1 1.2 1.3 1.4 1.5 IMDB EESEN SHOW TELL MNMT DEEPSPEECH AVERAGE Speedup 1.9 Figure 6.12: Speedups achieved by changing the precision dynamically. Baseline configuration is E-PUR with 8-bit parallel multipliers. As seen in Figure 6.12, all the models achieve consistent and significant speedups when compared with the baseline. The reduction in execution time is due to using lower precision (4-bit) for more than 57% of the time. Note that the baseline employs 8 bits for all the computations to maintain the accuracy. Furthermore, the smaller the bit-width the higher the performance of the E-PUR+DYN and E-PUR+SIP: switching from 8 bits to 4 bits doubles the performance of the dot product units. Hence, for time-steps and cell state elements where 4-bit precision is used (stable regions), the latency of the dot product is reduced by a factor of 2x compared to the 8-bit version. This represents around 60% of the evaluations for our set of RNN networks on average. On the contrary, 40% of the evaluations are still done using 8 bits to maintain accuracy (peaks regions of the cell state). Thus, their performance is not improved. The obtained speedup is close to the theoretical performance improvement. The foremost reason is that our scheme’s latency is largely hidden due to overlapping the DPU and multifunctional unit computations. Also, all the CUs are fully utilized. Note that most of the execution time is due to the dot product calculations to evaluate each neuron on each gate using either 4 or 8 bits. In both cases, the latency of the dot product calculations is larger than the latency to compute the activation functions in the MU and to quantize the output in the LQ unit. For all the networks, just a small execution time overhead is added when the evaluation of an LSTM cell starts (i.e., first neuron and first time-step). The IMDB network has a speedup of 1.99x since it can be evaluated entirely in low precision, and our scheme can detect it. For this model, we do not observe any peak regions in the cell state, and thus, low precision is used for all the evaluations. The networks EESEN, SHOWTELL, and NMT achieve a speedup of 1.38x, 1.40x, and 1.31x, respectively, since they require high precision for some of their evaluations. Regarding 96 6.5. EXPERIMENTAL RESULTS 0 10 20 30 40 IMDB EESEN SHOW TELL MNMT DEEPSPEECH AVERAGE Energy savings (%) SIP+DYN PAR+DYN 19.2 17 Figure 6.13: Energy savings achieved by dynamically changing the precision compared to the baseline (E-PUR-PAR). SIP+DYN and PAR+DYN refers to our scheme using SIP units and multiprecision parallel multipliers, respectively. the DeepSpeech network, a speedup of 1.32x is achieved. Figure 6.13 shows the energy savings achieved by PAR+DYN and SIP+DYN when compared to the 8-bit baseline, including both static and dynamic energy. On average, the savings in energy consumption for PAR+DYN and SIP+DYN are 19.2% and 17%, respectively. These savings come from several sources. First, using lower precision (4 bits) reduces the dynamic energy of the weight buffer, since less amount of information is fetched compared to the 8-bit version. More specifically, when using low precision, we only fetch the least significant nibble of the weights and inputs. Second, the energy cost of computing the dot product is reduced when employing 4 bits instead of 8 bits, since the activity in the DPUs is reduced. Finally, the speedups reported in Figure 6.12 provide a reduction in static energy. As it can be seen in Figure 6.13, using our scheme with parallel multipliers (DYN-PAR) provides 2% higher energy savings than the SIP implementation. The reason for this is that the SIP unit includes extra components to perform shifting and accumulation of the products computed on each cycle. However, as mentioned previously, SIP units provide finer granularity than the parallel multipliers, being able to perform the dot product at any number of bits. The LSTM networks EESEN and IMDB exhibit the most substantial energy savings: 15.9% and 34.2%, respectively, when using SIP+DYN. For PAR+DYN, their savings are 16% and 39.4%. For these networks, a large percentage of the computations are evaluated using low precision and, thus, the energy savings are significant. Most of the energy savings for these two networks are due to the reduction in static and dynamic energy of the scratchpad memories, which are used to store the weights. For the networks SHOWTELL and NMT evaluated on SIP+DYN, the energy savings are 13.5% and 15.4%, respectively, whereas when evaluated on PAR+DYN, their energy savings are 14.9% and 17%. These networks are the largest in our set of benchmarks and, hence, their dynamic and static energy consumption is larger than the other two networks. Regarding DeepSpeech, the energy savings are 12.7% and 16.5% for SIP+DYN and PAR+DYN, respectively. Our scheme can be extended to support more than two levels of precision. To assess this, we evaluated EESEN and DeepSpeech using 8, 4 or 2 bits. A smaller range inside the stable region (shown in Figure 6.4) is defined, such that values of the cell state inside this new range are computed using 2 bits, otherwise they are done using 4 bits. For this scheme, 8.5% of the EESEN computations are performed using 2-bits, whereas, for DeepSpeech, 10% are done with 2-bits. As a result, the energy consumption and execution time of these networks are improved by 3.3% and 1.02x, on average. 97 CHAPTER 6. DYNAMIC PRECISION SELECTION Regarding the area, the E-PUR baseline has an area of 31.3 mm2. SIP+DYN has an area of 33.6 mm2, whereas PAR+DYN has an area of 33.2 mm2. Therefore, a small overhead of around 8% is added by the buffers and multipliers required to support setting the precision dynamically. 6.6 Related Work The Tensor Processing Unit (TPU) [51] is an ASIC that supports convolutional, fully-connected, and LSTM, delivering performance per watt orders of magnitude higher than CPUs and GPUs. It achieves a performance of 92 TOps/s (8-bit) while dissipating 40 Watts. TPU employs a fixed precision of 8 bits for weights and inputs. Our proposal is different as it selects the precision dynamically at runtime, using 4 bits for more than 66% of the time without any accuracy loss. On the other hand, more flexible accelerators that support variable precision have been introduced in recent years. Stripes [52] uses a Serial Inner Product (SIP) unit in which the bits are fed serially, and the bit-width of the operands can be changed online. Stripes only accelerates convolutional and fully-connected networks, whereas LSTMs are the main focus of this work. BitFusion [92] is a bit-flexible accelerator that includes an array of bit-level processing elements that can be dynamically merged or split to match the bit-width of individual DNN layers. Also, it provides full support for LSTM networks. Although Stripes and BitFusion offer a significant degree of flexibility, the precision for each layer is determined offline and kept constant during inference, i.e., a layer always employs the same precision. In this work, we show that higher performance can be achieved by dynamically selecting the precision based on the cell state’s evolution. Our scheme can change the precision for every element of the cell state and every time-step, further improving performance and energy efficiency. In addition to the ASIC-based solutions, FPGA-based accelerators for LSTM inference have also been proposed in recent years. Brainwave [28] is a Neural Processing Unit that achieves an order of magnitude improvement in latency and throughput over state-of-the-art GPUs on large LSTM networks. The Efficient Speech Engine (ESE) [43] exploits pruning and sparsity to improve the performance of LSTM networks on FPGAs. C-LSTM [107] leverages structured compression techniques that reduce the LSTM model size while eliminating the irregularities of computation and memory accesses. On the other hand, DeltaRNN [31] and the work in [82] exploit temporal coherency of the LSTM data to reuse computations and avoid redundant memory accesses. Pruning, compression, and computation reuse techniques are completely orthogonal to our scheme. Regarding software-based RNN quantization, some proposals such as HitNet [106] and Binary Forget and Input gate (BFIG) [63] have been introduced. These schemes apply quantization statically. Hitnet goes as low as 2 bits, whereas BFIG uses 1 bit to represent the forget and input gates. In the case of HitNet, it is only tested on a small model (1 layer and 300 units). We have seen in our experiments that small LSTM models tend to work better when employing low precision, whereas models such as NMT tend to lose accuracy when it is quantized with less than 4 bits. In the case of BFIG, accuracy is lost for the NMT network, whereas our scheme does not lose any accuracy. Also, it only works in two of the gates, whereas our scheme can employ low precision for the four gates. Moreover, as shown in the Section 6.5 we can go as low as 2 or 1 bit. Besides, if we are more aggressive while applying our scheme (allow accuracy loss and multi-level precision), our 98 6.7. CONCLUSIONS scheme can be as low as 2 or 1. 6.7 Conclusions In this chapter, we present a novel scheme to select the precision for RNN computations dynamically at runtime. We observe that the values of the cell state can be used to determine the required bit-width: time-steps where the value changes rapidly (i.e., peaks) require higher precision to avoid large errors, whereas time-steps where the value is relatively stable can be evaluated with lower precision. Based on this observation, we propose a novel scheme that monitors recent values of the LSTM cell state and sets the appropriate precision dynamically. Unlike previous schemes that fix the precision for each DNN layer offline, our system can change the precision for every cell state element and every time-step. We evaluate our proposal on top of E-PUR using four popular LSTM networks. The experimental results show that our scheme selects the lowest precision for more than 57% of the time without any loss in accuracy, providing 1.46x speedup and 19.2% energy savings on average. The extra hardware required for our technique is quite modest, as it represents a small area overhead of 8%. 99 7 Energy-Efficient and High-Throughput RNN Batching In this chapter, we address the problem of performing RNN inference in an energy-efficient manner while providing high-throughput. First, we describe the importance of batching for RNNs and review the state-of-the-art approaches for RNN batching. Second, we analyze the primary sources of inefficiencies of current batching systems. Third, we present E-Batch, an energy-efficient batching scheme tailored to RNN accelerators. Finally, we evaluate our proposal on E-PUR and TPU. Our experimental results show that compared to the state-of-the-art RNN batching techniques, E-BATCH improves throughput by 1.8x and energy-efficiency by 3.6x in E-PUR and by 2.1x and 1.6x in TPU, respectively. 7.1 RNN Batching Nowadays, a plethora of machine learning applications using RNNs are evaluated in the cloud. In this domain, GPUs and high-performance hardware accelerators such as TPU [51] and BrainWave [29] are employed. As mentioned earlier, since RNN inference exhibits a limited amount of parallelism, the resource utilization for these accelerators is low. Specifically, it is 18% for TPU and 3.5% for BrainWave for a batch size of one input sequence. GPUs/CPUs using state-of-the-art RNN libraries also exhibit extremely low resource utilization. As an example, the high-performance library cuDNN [11] shows an average utilization of 13.5% on an NVIDIA Titan V GPU for RNN inference. Note that, for LSTM inference, although the amount of computation (matrix-vector multiplications) increases as the number of time-steps in the input sequences increase, the parallelism is limited due to data-dependencies. Servers handling multiple requests (i.e., cloud services) from a large number of edge devices, such as smartphones, employ batching to increase parallelism and throughput. During inference, 101 CHAPTER 7. ENERGY-EFFICIENT AND HIGH-THROUGHPUT RNN BATCHING batching merges several requests and feeds them to the system simultaneously, so that all their computations are done in parallel. Hence, all the requests in a batch share the high cost of accessing the model parameters. Note that batching works best when batched requests are identical in length, i.e., the number of time-steps are the same. However, this is particularly difficult in RNNs since their input sequences usually have different number of time-steps. For instance, Deepspeech2 [7] has input sequences with a number of time-steps that ranges from 60 to 1700 (Librispeech test set). State-of-the-art deep learning systems [2,77] handle this issue by padding the batched sequences such that their number of time-steps are identical to the number of time-steps of the longest sequence. The main drawback of this approach is that the latency of all the batched sequences increases since their evaluation cannot be completed until the longest sequence has been evaluated. Besides, energy is wasted performing computations on the extra added time-steps. Our experiments on E-PUR show that 30.2% of the energy consumption is due to padding, whereas the latency overhead is 28.5% on average for a set of RNNs. Moreover, we observe that when evaluating Deep RNN models on accelerators, weight reuse is severely affected by the number of requests in a batch and the number of time-steps in the batched sequences. The reason is that when evaluating a new layer of an RNN model, the model’s weights are first brought to on-chip memory, hence evicting the weights of the previous layer. Henceforth, creating batches with short sequences (i.e., low number of time-steps) incurs in a large amount of weight swapping, and, as a consequence, energy consumption increases. This issue is evident in batching strategies such as Cellular Batching [33], where batches with short sequences are created, resulting in large increase in energy consumption due to the frequent movement of weights from off-chip to on-chip memory. For instance, cellular batching on top of E-PUR consumes, on average, 4.5x more energy per request than sequence padding for DeepSpeech [7]. Motivated by the inefficiencies of current batching schemes, we propose E-BATCH: an RNN batching scheme that improves energy efficiency by avoiding padding and by increasing the temporal and spatial locality of the weights. In the next sections, we describe the state-of-the-art strategies used during RNN batching. Also, we present the primary sources of energy inefficiencies for RNN batching on hardware accelerators and E-BATCH. 7.1.1 Batching Strategies As mentioned in Section 2.3.3, Sequence Batching (batching for short) is a well-known technique that is commonly used to increase throughput. A batch is a set of one or more requests (i.e., input sequences), and the number of batched requests (i.e., batch size) is usually limited by the amount of hardware resources available in the system. In this work, we refer to the processing elements employed to evaluate one or more input sequences as processing lane. Traditionally, arriving requests are grouped into batches of size N, and batches are evaluated sequentially. Commonly, once a batch of requests is sent to the hardware for evaluation, each one of the batched requests is assigned to a processing lane. Also, the evaluation of any of those requests is not completed until all of them are computed. Henceforth, batching tends to work best when the batched requests have the same length (i.e., an identical number of time-steps among input sequences) since all the processing lanes are fully utilized, and none of the batched requests 102 7.1. RNN BATCHING idle idle idle idle req1 req2 req2 req3 req3 req3 req4 req4 req4 req4 Lane 0 Lane 1 Lane 2 Lane 3 Batch 0: requests 1-4 Hardware req5 req5 req5 req6 req6 Batch 1: requests 5-6 Runtime System Sent batch 0 Sent batch 1 0 1 2 3 4Time-step 5 6 78 01234 req2 (2) req3 (3) req4 (4) req1 (1) req5 (3) req6 (2) Time-step 5 Request Queue Waiting Padded Computation Useful Computation Idle Lane Figure 7.1: Sequence Padding. Requests are shown in the request queue from their time of arrival until they are dispatched to the hardware for evaluation. The number inside the parenthesis next to each queued request is the number of time-steps for that request. The batch size is 4. will have to wait for others to complete. However, this is an issue in RNNs since the number of time-steps on each input sequence is typically different. Henceforth, to mitigate this problem, the following strategies are commonly employed. Sequence Padding Sequence Padding is used in systems such as TensorFlow [2] and PyTorch [77] in order to handle sequences with different number of time-steps when batching is performed for RNNs. In this case, the sequence with the largest amount of time-steps (i.e. m) in a batch is found and, for each of the other sequences in the batch, their number of time-steps is increased to match the maximum length m. These extra added time-steps are filled with zeros, and the larger the difference among batched input sequences, the larger the amount of useless computations. As an example, let us consider the batches created in Figure 7.1, where requests 1-6 have 1, 2, 3, 4, 3 and 2 time-steps, respectively. Hence, in order to create a batch of size 4, requests 1-3 are padded. Note that request 1completes its execution long before request 4 (i.e. the longest request in the batch), but it is not returned to the user until request 4 is finished. Furthermore, although request 5 is available when request 1 is already finished, its computation cannot start until the whole batch is computed. Sequence Bucketing Sequence Bucketing (bucketing) [55] is an optimization technique that is implemented on top of sequence padding in systems such as MXNet [18] and TensorFlow. Its target is to reduce padding, hence decreasing the amount of wasted computations. In order to accomplish this, different sequences are clustered together into a logical group, a.k.a. bucket, based on a given heuristic. One commonly used heuristic, shown in Figure 7.2, is to assign sequences of similar length to a given bucket. Similarity is defined as the maximum difference in time-steps among all the sequences in any given bucket and is constrained to be below a given threshold (i.e., the bucket width). Then, when a batch is created, only sequences from the same bucket can be batched together. Note that some sequences in a given batch may still require some padding. The maximum amount of time-steps padded is the bucket width. For instance, let us consider the example in Figure 7.2, assuming that requests 1-6 have 1, 2, 4, 5, 3, and 2 time-steps respectively, and the bucket width is one. Requests 103 CHAPTER 7. ENERGY-EFFICIENT AND HIGH-THROUGHPUT RNN BATCHING idle idle idle idle req1 req2 req2 Lane 0 Lane 1 Lane 2 Lane 3 Batch 0 Hardware Batch 1 Sent batch 0 0 1 2 3 4Time-step 5678 req2 (2) req3 (3) req4 (4) req1 (1) req5 (3) req6 (2) Runtime System Request Queue req4 req4 req4 req4 req3 req3 req3 req5 req5 req5 req6 req6 9 Batch 2 01234Time-step 567 Padded Computation Waiting Useful Computation Idle Lane Figure 7.2: Sequence Bucketing. For this example, the maximum difference in time-steps for requests that are batched together is 1. 1, 2, and 6 are assigned to a bucket whereas request 3-5 are assigned to another bucket. Then, if batches are created using a batch size of 4, requests 1-2 will be batched together. Similarly requests 3-5 will go into the same batch. Note that, although request 6 is available when requests 3-5 are batched, it is not included since it belongs to a different bucket. Analogous to sequence padding, batches are evaluated sequentially, and new requests are not allowed to join a given batch while it is being evaluated in the hardware. Cellular Batching Cellular Batching is a recently proposed technique for RNN batching that focuses on batching requests at the granularity of cells (i.e., several time-steps) instead of whole sequences [33]. Unlike sequence padding and bucketing, in cellular batching new requests are allowed to join a batch whose execution is ongoing. Also, once a request is evaluated, it can be returned to the user immediately. Figure 7.3 shows a simple example of how requests are scheduled in cellular batching. For this example, we assume a cell represents one time-step, a batch size of 4 and an LSTM model of one layer. In this example, the first time-steps of requests 1-4 are batched together and sent to the hardware for evaluation. Once the batch is evaluated, request 1 is completed and returned to the user. After this, a new batch is created using the second time-step from requests 2-4 and time-step 1 from request 5. Once this batch is evaluated, request 2 is completed and sent to the user. Then, the process of batching and evaluation continues for the remaining time-steps of requests 3-6 until all of them are evaluated. Since batches are created using a fine granularity, new requests can start execution as soon as the processing hardware becomes available, and completed requests are sent to the user immediately. Hence, the time a request waits in the queue is reduced. Thus, improving the average latency and throughput of the system. 7.2 Source of batching inefficiencies in RNNs Both Bucketing and Cellular batching provide an improvement over sequence padding by reducing the amount of wasted computations. Cellular batching also improves latency by batching requests using a finer granularity. However, these solutions do not take into account energy consumption and the spatial and temporal locality of the weights for large RNN models (i.e., more 104 7.3. RNN BATCHING ON ACCELERATORS 147 4 req1 (1), req5(1-2) req2 (1-2) Lane 0 Lane 1 Lane 2 Lane 3 Batch 0 Hardware Batch 1 Time-step 10 13 Padded Computation Layer 1 Waiting Useful Computation Layer 1 req4 (1-3) req4 (4) req3 (1-3) req5 (3) req6( 1-3) req7 (1-2) req1 (1), req5(1-2) req2 (1-2) req4 (1-3) req3 (1-3) req4 (4) req5 (3) req6( 1-3) req7 (1-2) Padded Computation Layer 2 Useful Computation Layer 2 Layer 1 Layer 2 Layer 1 Layer 2 Batch 0 Batch 1 0123 req2 (2) req3 (3) req4 (4) req1 (1) req5 (3) req6 (3) Runtime System Time-step 5 Request Queue 67 req7 (2) N=3 Figure 7.8: Evaluation of an RNN with two LSTM layers using E-Batch. Batch 0 is evaluated for the first and second layer, before a new batch is created. req 5 arrives before finishing the evaluation of the first layer and, hence, it joins Batch 0 immediately. On the contrary, req 6-7 arrive after the evaluation of the first layer, so its evaluation is deferred until a new batch is created. RNN Accelerator E-Batch Runtime CPU interrupt RNN 0 Weights RNN N Weights req1 req2 req n weights InputsOutputs Request Queue requests Main Memory …… Batch Meta Data Figure 7.9: Overview of E-Batch System Architecture. layer. After batch 0 is completed, the output results for requests 1-2 are sent to the user, whereas a new batch is created using the remaining time-steps of request 4-5 and the new requests request 6-7. The overall architecture of E-Batch is shown in Figure 7.9. It is composed of a runtime system and an RNN accelerator. The runtime is in charge of creating and managing batches of requests, whereas evaluations are performed in the accelerator. In the next subsections, we describe in more detail these components. 7.3.3 Hardware support for E-Batch Supporting E-Batch on E-PUR The following modifications are done in E-PUR to support E-BACTH. First, we include an interrupt, which is used to signal the runtime when a lane becomes idle. Furthermore, we include a small buffer (i.e., the request buffer) to keep track of the lane where each request is being evaluated. Also, in the request buffer, we store the number of time-steps that have to be processed for each request. Finally, we include a register to store the parameter N(i.e., maximum number of timesteps). Once a batch is received, the evaluation of the first layer works as follows. For each request 111 CHAPTER 7. ENERGY-EFFICIENT AND HIGH-THROUGHPUT RNN BATCHING in the batch, an entry in the request buffer is created and initialized with its meta-information. Then, when a time-step is evaluated, the number of time-steps processed for the active requests are updated in the request buffer. In the case that all the time-steps for a given request are completed, we proceed with the next request in the lane. However, if there are no more requests in the lane, a signal is sent to the runtime to indicate that a lane is idle so that a new request can join the current batch being executed. Then, after Ntime-steps have been evaluated, we continue with the computation of the next layers. Finally, once the evaluation of a batch is completed, the number of time-steps evaluated for each request is sent back to the runtime. Supporting E-Batch on a TPU-Like Architecture TPU is a state-of-the-art accelerator for neural networks [51]. It is composed of a systolic array of processing elements (PEs) and on-chip memory for weights and activations. In order to evaluate LSTM models on TPU like architectures, an output stationary dataflow is employed [81,87]. In this regard, for an RNN model with Nneurons, neuron nkwill be mapped to all the PEs in column kof the array. Regarding the weights, they are mapped to the columns of the systolic array, whereas the input sequences are mapped to rows of the array (one input sequence per row). Thus, to evaluate nk, its weights are streamed down through column k, whereas the elements of each input sequence are streamed through the rows. Note that the maximum batch size supported is equal to the number of rows in the array and that each of them will correspond to a processing lane. To support E-Batch in a TPU-like architecture, as done in E-PUR, we add an interrupt to signal the end of a sequence to the runtime and a request buffer as described in 7.3.3. 7.3.4 Runtime support for E-Batch The runtime is in charge of the management and creation of batches. It includes a queue where new requests arriving at the system are stored. Furthermore, for each request, the runtime tracks the number of time-steps that have been evaluated. Also, it knows whether the accelerator is processing or idle. When the accelerator is idle, the system will create a new batch using all the available requests by employing the Greedy partitioning algorithm described in Section 7.3.2. Then, when a batch is created, for each batched request, the lane assigned to it and the number of time-steps that need to be evaluated are sent to the accelerator. Once the evaluation of a batch is completed, the number of time-steps evaluated are updated for all its requests. Moreover, requests that are completed (i.e., all their time-steps have been executed) are returned to the user. On the other hand, new requests and requests with time-steps pending for evaluation are batched together. If the available requests are not sufficient to create a complete batch, the runtime will wait until the batch is completed or Tmilli-seconds have passed. 112 7.4. EXPERIMENTAL RESULTS Table 7.1: Hardware configuration for E-PUR and TPU. E-PUR Parameter Value Technology 28 nm Frequency 500 MHz Weight Buffer 2 MiB per CU Input Buffer 128 KiB per CU DPU Width 64 operations TPU-like accelerator Frequency 700 MHz SRAM Buffer 24 MiB Systolic Array PEs 128x128 7.4 Experimental Results In this section, we describe the experimental evaluation of E-BATCH. We employ the methodology presented in Chapter 3 to model E-PUR and a TPU-like architecture. The configuration parameters for E-PUR and TPU are shown in Table 7.1. As benchmarks, we use the machine translation [110] and the speech recognition [7] models shown in Table 3.4. Regarding the runtime, we implemented a system that employs the timing estimation and status of the accelerator’ simulator (E-PUR or TPU) to batch new requests. For our experiments, we simulate several hours of the system execution. To this end, the train/test datasets are not sufficient since they would be processed in a short time span. Aiming to generate more requests to be processed by our system, we analyzed the distribution of the number of time-steps for each input sequence in the train and test set of the RNN models in the benchmarks. Based on this analysis, we generate requests whose number of time-steps follows the distribution observed in the original datasets. Note that the execution and energy consumption of a given request only depends on the RNN parameters and the number of time-steps. To reproduce a real environment, we simulate the arrival time of each user’s request. To this end, we use a Poisson distribution. To increase or decrease the number of requests per second arriving to the system (i.e., system load), we change the average inter-arrival time between requests. Note that, for each of our experiments, the average request arrival rate is kept constant. For the rest of this section, we detail the evaluation of our proposal on E-PUR and a TPU-like architecture. Regarding the batch size, we tested several batch sizes and found that the results are similar. Thus, we chose 64 as it delivers the best tradeoff between performance and area for E-PUR, whereas for a TPU-like architecture we use 128. First, we discuss the evaluation of bucketing and cellular batching on E-PUR. Second, we discuss performance and energy consumption of E-Batch for E-PUR. Finally, we discuss the results of E-Batch for a TPU-like architecture. 113 CHAPTER 7. ENERGY-EFFICIENT AND HIGH-THROUGHPUT RNN BATCHING 7.4.1 Sequence bucketing and cellular batching on E-PUR To evaluate the performance of bucketing and cellular batching, we implement them on E-PUR and use an LSTM model with two layers and 800 neurons, whereas the input sequences were drawn from the Deepspeech benchmark. Our experiments show that sequence padding is on average 7x faster than bucketing and delivers 1.6x higher requests per joule. As discussed in Section 7.2.2, bucketing with a small bucket width tends to create batches with a low number of requests and, thus, weights are swapped more frequently resulting in larger energy consumption than sequence padding, which manages to create batches with a larger number of requests. Moreover, with bucketing, requests have to wait longer before they are sent to the accelerator, thus increasing their latency. Note that, when the number of requests per second arriving to the system is low bucketing and padding achieve similar results since they behave similarly. Regarding cellular batching, it achieves, on average, a 1.2x speedup over padding, but energy efficiency is much worse: 4.5x reduction in requests per joule. Furthermore, the maximum throughput achieved by cellular batching is similar to sequence padding because of the large amount of weights that are evicted from on-chip memory each time a new batch of requests is evaluated. Weight eviction occurs because batches composed of requests that belong to different RNN layers do not share their parameters. Cellular batching works better on GPUs since it was not designed to consider the high degree of on-chip locality commonly found in RNN accelerators. Both bucketing and cellular batching achieve a throughput similar to padding. However, padding is more energy efficient. Therefore, for comparison purposes, we chose an accelerator (E-PUR or TPU) employing sequence padding as the baseline configuration. 7.4.2 E-Batch on E-PUR Figures 7.10 and 7.11 show the average latency per request for Machine Translation and Speech Recognition RNNs, respectively, on an E-PUR-like accelerator. Both figures include the baseline and our E-batch scheme under different loads and using 64 lanes (maximum batch size). For EBatch, we use different values of the threshold N(i.e., maximum number of time-steps in a lane) to evaluate the trade-off between energy and latency. In these plots and others, N= 0 refers to the E-Batch configuration where the maximum number of time-steps in a lane is set to the number of time-steps of the longest sequence in the batch when it is created. The Speech Recognition network has a larger average latency since its input sequences are typically larger than the input sequences of the Machine Translation model. Therefore they result in more considerable processing and memory transfer times. As it can be seen for both networks, when Nis zero the latency of using sequence padding and E-Batch are similar because, in this case, the longest sequence in a given batch is the same for both schemes. However, since E-Batch can add new requests to a batch while it is being processed, the queuing time decreases, henceforth reducing the average latency. Note that for low loads (i.e., 100 requests per second in Figure 7.10), the average latency is sightly higher for E-Batch. It is because E-batch waits for some time to increase the number of requests that are batched together, thus improving weight locality and energy efficiency. 114 7.4. EXPERIMENTAL RESULTS 0 500 1000 1500 2000 2500 Througput (req/sec) 0 100 200 300 400 Average Latency (ms/req) Machine Translation Padding E-Batch N=0 E-Batch N=128 E-Batch N=256 E-Batch N=512 Figure 7.10: Average Latency vs throughput for Machine Translation [110] using a batch size of 64 on E-PUR. 0 50 100 150 200 250 300 350 Througput (req/sec) 0 500 1000 1500 Average Latency (ms/req) Speech Recognition Padding E-Batch N=0 E-Batch N=3000 E-Batch N=4000 E-Batch N=5000 Figure 7.11: Average Latency vs throughput for Speech Recognition [7] using a batch size of 64 on E-PUR. Regarding the maximum throughput, as it can be seen in Figures 7.10 and 7.11 E-Batch achieves 1.83x and 1.77x improvement over padding for Machine Translation and Speech Recognition, respectively. This improvement in throughput comes from allowing new requests to start execution while the first layer of an RNN is being evaluated. In addition, because of the variability in the number of time-steps, when the evaluation of small requests is completed, a new request from the waiting queue can join the current batch being executed. Therefore, hardware utilization is increased, improving system throughput. The maximum throughput obtained by E-Batch for different values of Nin Figures 7.10 and 7.11 are similar, slightly increasing when Nbecomes very large. Figures 7.12 and 7.13 show the average number of requests per joule for Machine Translation and Speech Recognition, respectively. As it can bee seen, when Nis zero sequence padding tends to have a slightly better energy efficiency than E-Batch for low loads. It occurs because when the number of requests in a batch is small, as new requests arrive at the system, they are added to the batch being processed. However, since Nis 0 once the time-steps for the longest and oldest 115 CHAPTER 7. ENERGY-EFFICIENT AND HIGH-THROUGHPUT RNN BATCHING 0 200 400 600 800 1000 1200 1400 1600 1800 2000 2200 Througput (req/sec) 0 0.5 1 1.5 2 2.5 Energy Efficiency (req/J) Machine Translation Padding E-Batch N=0 E-Batch N=128 E-Batch N=256 E-Batch N=512 Figure 7.12: Average number of Requests per Joule vs Throughput for Machine Translation [110] using a batch size of 64 on E-PUR. 0 50 100 150 200 250 300 Througput (req/sec) 0 1 2 3 4 5 6 7 Energy Efficiency (req/J) Speech Recognition Padding E-Batch N=0 E-Batch N=3000 E-Batch N=4000 E-Batch N=5000 Figure 7.13: Average number of Requests per Joule vs Throughput for Speech Recognition [110] using a batch size of 64 on E-PUR. request in the batch are computed, the system proceeds to evaluate deeper layers. As a result, the computations of some requests are divided among several batches, and thus they require more memory accesses to fetch the weights. On the contrary, as the load increases, batches with a larger amount of time-steps are created, and thus weight reuse increases. As shown in Figures 7.12 and 7.13, increasing the value of Nwill dramatically increase the energy efficiency of E-Batch for both networks. The reason is that since the system waits until N time-steps are evaluated in the first layer, a large amount of time-steps are batched together and, as a result, weight reuse is increased. 7.4.3 E-Batch on a TPU-like Accelerator Figure 7.14 shows the average latency per request for sequence padding and E-Batch running on top of a TPU-like accelerator. The number of lanes used is 128 since this is the number of 116 7.4. EXPERIMENTAL RESULTS 0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 5500 Througput (req/sec) 0 100 200 300 400 Average Latency (ms/req) Machine Translation Padding E-Batch N=0 E-Batch N=128 E-Batch N=256 E-Batch N=512 Figure 7.14: Average Latency vs Throughput for Machine Translation [110] using a batch size of 128 for TPU. 0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 Througput (req/sec) 0 1 2 3 4 5 6 Energy Efficiency (req/J) Machine Translation Padding E-Batch N=0 E-Batch N=128 E-Batch N=256 E-Batch N=512 Figure 7.15: Average number of Requests per Joule vs Throughput for Machine Translation [110] using a batch size of 128 for TPU. rows of the systolic array in the TPUv1. As it can be seen, when Nis zero the average latency of sequence padding and E-Batch are similar since, in this case, the largest number of time-steps for a given batch is the same in both schemes. However, since E-Batch allows new requests to join a batch while it is being computed for the first layer, the maximum throughput of E-Batch is 2.1x higher. Figure 7.15 shows the number of requests per joule for the machine translation network evaluated on a TPU-like architecture. Like E-PUR, when the load is small, and Nis zero, a large number of batches with a small number of time-steps are created, and as a result, the number of memory accesses increases. However, as the number of requests per second increases, a more substantial amount of requests are batched together, thus increasing weight reuse. Similarly, as Nincreases, a more considerable amount of time-steps are batched together, which also increases weight reuse. For instance, when Nis 128, and the load is 2000 req/sec, E-batch achieves an energy efficiency improvement of 1.3x compared to the baseline, whereas when Nis 256 or 512 energy efficiency is improved by 1.46x and 1.6x, respectively. However, note that when improving energy efficiency, the average latency is also increased. 117 CHAPTER 7. ENERGY-EFFICIENT AND HIGH-THROUGHPUT RNN BATCHING 7.5 Related Work Several hardware accelerators [51,29,112,41] and software libraries [11,114,49] tailored to improve energy efficiency and performance of RNNs have been proposed recently. In addition to hardware acceleration, several techniques such as pruning [81,43], model compression [42], and computations reuse [82,94] have been employed. Our optimizations are orthogonal to those techniques. Regarding software libraries such as as [49,11,78], they are mainly tailored to GPUs and CPUs [114], whereas our proposal targets specialized accelerators. Previous proposals employ sequence padding or bucketing to handle sequences of different sizes. In CNTK [90], wasted computations are avoided by trying to batch small sequences when they can fit in the padded space. However, this is not always possible since short sequences may not be available. Conversely, in E-Batch, a sequence can be split among different batches so that only the amount of time-steps required to fill up the padded space is used. Batching RNN sequences is supported in hardware accelerators such as BrainWave and LSTMSharp. BrainWave [29] is highly optimized for batches of size one, and inputs are processed sequentially, by computing one single input at a time. In this accelerator, sequence padding is not required. However, employing batch sizes larger than two is unfeasible since inputs are processed sequentially. LSTM-Sharp [112] focuses on increasing resource utilization. It addresses the issue of extra padded computations that occur when performing matrix-vector multiplications, and the number of multipliers per tile are not multiples of the input vector size. This padding is different to padding several sequences to make their sizes homogeneous. Sequence padding is also needed for LSTM-Sharp, to support batching. E-batch is orthogonal to this work and can be implemented on top of this accelerator. TPU [51] supports large batch sizes by means of sequence padding. 7.6 Conclusions In this chapter, we presented E-Batch, a batching system for recurrent neural networks that increases throughput while improving energy efficiency. E-Batch consists of a runtime and minor extensions to the hardware accelerator. In E-Batch, long sequences are batched together to decrease memory accesses. Furthermore, throughput is increased by allowing requests to join other requests while their execution is ongoing. We evaluated E-Batch on top of E-PUR and TPU, two state-of-art hardware accelerators for RNNs. Our experimental results show that in E-PUR, E-Batch improves throughput by 1.8x and energy efficiency by 3.6x, whereas for TPU throughput is enhanced by 2.1x and energy efficiency by 1.6x. 118 8 Conclusions and Future Work In this chapter, the main conclusions of this thesis are presented. We summarize the main contributions and outline some open-research areas for future work. 8.1 Conclusions The purpose of this thesis is to design energy-efficient architectures tailored to the execution of RNN inference while enhancing performance. In this regard, we develop E-PUR, a highly efficient low power RNN accelerator. Moreover, we implement several techniques that improve the performance and energy efficiency of RNN inference on hardware accelerators. We first identified the main challenges regarding the evaluation of RNNs in an energy-efficient manner. We observe that most of the energy consumption when performing RNN inference is due to memory accesses to fetch the weights. Moreover, we note that due to data dependencies, the amount of parallelism is limited. Then, we design E-PUR, a custom accelerator tailored to RNN inference. E-PUR is designed to support large RNN models while providing high energy efficiency. E-PUR includes several on-chip memories to mitigate the cost of accessing main memory. Also, it improves performance by overlapping several operations of the RNN evaluation process. Compared to highly optimized software-based solutions running on a modern System-on-Chip, E-PUR increases energy efficiency by 58x on average, while the performance is improved by 6.9x. On average, the power dissipation of E-PUR is 500 mW. We further improve E-PUR by implementing Maximizing Weight Locality (MWL). MWL performs all the computations involving the forward connections in parallel since they are independent. Then, the recurrent connections are evaluated sequentially. By employing MWL, we reduce the on-chip memory requirement by 2x. Compared to a modern SoC, energy efficiency is improved by 119 CHAPTER 8. CONCLUSIONS AND FUTURE WORK 88x, while the power dissipation is 330 mW. Despite the significant energy savings and performance improvements of E-PUR, we observe that memory accesses are still the primary source of energy consumption. Thus, we propose two novel techniques to further improve the energy efficiency of RNN evaluation. The first technique is based on reusing computations, whereas the latter focuses on changing the bit-width at runtime. Regarding computations reuse, we implement a fuzzy memoization scheme to cache and reuse the neurons’ output. Our technique is based on the observation that the output of a given neuron tends to change slightly between consecutive time-steps. We exploit this observation by proposing a novel memoization scheme that employs a binary neural network as a predictor of reusability. We evaluate this technique in E-PUR. We show that by avoiding an average of 24.2% of E-PUR’s calculations and memory accesses, its energy efficiency is improved by 18.5% on average and a speedup of 1.35x is obtained. RNN inference is commonly performed using low bit-width. In this regard, a worst-case precision is traditionally assumed at the model level or layer level, such that the base accuracy is maintained. We observe that for RNNs, the precision required for computations varies on each time-step. More precisely, empirically we determine that the precision requirements of RNN computations vary according to the value of the cell state. We exploit this observation by proposing a novel technique that changes the precision used during RNN computations at runtime. In this technique, we dynamically switch between the worst-case precision and a lower precision. We show that by tracking the cell state value, on average 57% of the computations can be done in a precision lower than the static worst-case precision while maintaining the base accuracy of the model. We implement this technique on top E-PUR. Our evaluations show that by performing 57% of the computations in a lower precision, energy efficiency is improved by 19.2% on average. Also, performance is enhanced by 1.46x on average. Finally, we observe that several systems increase energy efficiency, parallelism, and throughput by batching several RNN input sequences so that they are evaluated concurrently. However, batching requires that the input sequences have a similar number of time-steps to be efficient. We analyze the state-of-the-art batching strategies and observe that they incur in a high amount of energy consumption. Hence, as a first step, we identify the primary sources of batching inefficiencies during RNN inference. After this analysis, we determine extra-padded computations, low hardware resource utilization, and evicting weights too frequently as the principal sources of energy consumption during RNN batching. To mitigate these issues, we develop E-BATCH, a novel batching scheme which reduces the amount of padded computations while maintaining the temporal and spatial locality of the weights. We implement it on top of E-PUR and a TPU-like architecture. Our evaluations show that energy efficiency is improved by 3.6x/2.1x on average for E-PUR and TPU, respectively, whereas throughput is enhanced by 1.8x/1.6x, respectively. 8.2 Summary of Contributions In this thesis, several energy-saving techniques for RNN inference have been proposed. We have observed different properties of RNNs and used them to propose several techniques, from 120 BIBLIOGRAPHY [24] Gregory Diamos, Shubho Sengupta, Bryan Catanzaro, Mike Chrzanowski, Adam Coates, Erich Elsen, Jesse Engel, Awni Hannun, and Sanjeev Satheesh. Persistent rnns: Stashing recurrent weights on-chip. In Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48, ICML’16, page 2024–2033. JMLR.org, 2016. [25] Caiwen Ding, Siyu Liao, Yanzhi Wang, Zhe Li, Ning Liu, Youwei Zhuo, Chao Wang, Xuehai Qian, Yu Bai, Geng Yuan, et al. Circnn: accelerating and compressing deep neural networks using block-circulant weight matrices. In Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture, pages 395–408, 2017. [26] Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. Conference on Learning Theory, 12 2015. [27] Asbjørn Følstad and Petter Bae Brandtzæg. Chatbots and the new world of hci. interactions, 24(4):38–42, 2017. [28] Jeremy Fowers, Kalin Ovtcharov, Michael Papamichael, Todd Massengill, Ming Liu, Daniel Lo, Shlomi Alkalay, Michael Haselman, Logan Adams, Mahdi Ghandi, et al. A configurable cloud-scale dnn processor for real-time ai. In Proceedings of the 45th Annual International Symposium on Computer Architecture, pages 1–14. IEEE Press, 2018. [29] Jeremy Fowers, Kalin Ovtcharov, Michael Papamichael, Todd Massengill, Ming Liu, Daniel Lo, Shlomi Alkalay, Michael Haselman, Logan Adams, Mahdi Ghandi, Stephen Heil, Prerak Patel, Adam Sapek, Gabriel Weisz, Lisa Woods, Sitaram Lanka, Steven K. Reinhardt, Adrian M. Caulfield, Eric S. Chung, and Doug Burger. A configurable cloud-scale dnn processor for real-time ai. In Proceedings of the 45th Annual International Symposium on Computer Architecture, ISCA ’18, pages 1–14, Piscataway, NJ, USA, 2018. IEEE Press. [30] Merlin Friesen. Linux power management optimization on the nvidia jetson platform. https://events.static.linuxfound.org/sites/events/files/slides/Linux_ Low_Power_ELC_SanDiego.pdf. [31] Chang Gao, Daniel Neil, Enea Ceolini, Shih-Chii Liu, and Tobi Delbruck. Deltarnn: A power-efficient recurrent neural network accelerator. In Proceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, FPGA ’18, page 21–30, New York, NY, USA, 2018. Association for Computing Machinery. [32] Chang Gao, Antonio Rios-Navarro, Xi Chen, Tobi Delbruck, and Shih-Chii Liu. Edgedrnn: Enabling low-latency recurrent neural network edge inference. arXiv preprint arXiv:1912.12193, 2019. [33] Pin Gao, Lingfan Yu, Yongwei Wu, and Jinyang Li. Low latency rnn inference with cellular batching. In Proceedings of the Thirteenth EuroSys Conference, EuroSys ’18, pages 31:1– 31:15, New York, NY, USA, 2018. ACM. [34] J. S. Garofolo, L. F. Lamel, W. M. Fisher, J. G. Fiscus, and D. S. Pallett. DARPA TIMIT acoustic-phonetic continous speech corpus CD-ROM. NIST speech disc 1-1.1. NASA STI/Recon Technical Report N, February 1993. 127 BIBLIOGRAPHY [35] Antonio Gonz´alez, Jordi Tubella, and Carlos Molina-Clemente. Trace-Level Reuse. In ICPP, pages 30–, 1999. [36] https://en.wikipedia.org/wiki/Google_Assistant. [37] https://www.nextplatform.com/2018/05/10/tearing-apart-googles-tpu-3-0-ai-coprocessor/. [38] https://coral.ai/docs/edgetpu/benchmarks/. [39] https://en.wikipedia.org/wiki/Grammarly. [40] Alex Graves and J¨urgen Schmidhuber. Framewise phoneme classification with bidirectional lstm networks. In Neural Networks, 2005. IJCNN’05. Proceedings. 2005 IEEE International Joint Conference on, volume 4, pages 2047–2052. IEEE, 2005. [41] Yijin Guan, Zhihang Yuan, Guangyu Sun, and Jason Cong. Fpga-based accelerator for long short-term memory recurrent neural networks. In Design Automation Conference (ASPDAC), 2017 22nd Asia and South Pacific, pages 629–634. IEEE, 2017. [42] Udit Gupta, Brandon Reagen, Lillian Pentecost, Marco Donato, Thierry Tambe, Alexander M. Rush, Gu-Yeon Wei, and David M. Brooks. Masr: A modular accelerator for sparse rnns. 2019 28th International Conference on Parallel Architectures and Compilation Techniques (PACT), pages 1–14, 2019. [43] Song Han, Junlong Kang, Huizi Mao, Yiming Hu, Xin Li, Yubin Li, Dongliang Xie, Hong Luo, Song Yao, Yu Wang, et al. Ese: Efficient speech recognition engine with sparse lstm on fpga. In FPGA, pages 75–84, 2017. [44] Song Han, Xingyu Liu, Huizi Mao, Jing Pu, Ardavan Pedram, Mark A Horowitz, and William J Dally. Eie: efficient inference engine on compressed deep neural network. ACM SIGARCH Computer Architecture News, 44(3):243–254, 2016. [45] Song Han, Huizi Mao, and William J. Dally. Deep compression: Compressing deep neural network with pruning, trained quantization and huffman coding. In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. [46] Simon Haykin. Neural Networks: A Comprehensive Foundation (3rd Edition). Prentice-Hall, Inc., USA, 2007. [47] Robert Hecht-Nielsen. Theory of the backpropagation neural network. In Neural networks for perception, pages 65–93. Elsevier, 1992. [48] Sepp Hochreiter and J¨urgen Schmidhuber. Long short-term memory. Neural computation, 9(8):1735–1780, 1997. [49] Connor Holmes, Daniel Mawhirter, Yuxiong He, Feng Yan, and Bo Wu. Grnn: Low-latency and scalable rnn inference on gpus. In Proceedings of the Fourteenth EuroSys Conference 2019, EuroSys ’19, pages 41:1–41:16, New York, NY, USA, 2019. ACM. 128 BIBLIOGRAPHY [50] Andrew Howard, Mark Sandler, Grace Chu, Liang-Chieh Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, et al. Searching for mobilenetv3. In Proceedings of the IEEE International Conference on Computer Vision, pages 1314–1324, 2019. [51] Norman P. Jouppi, Cliff Young, Nishant Patil, David Patterson, Gaurav Agrawal, Raminder Bajwa, Sarah Bates, Suresh Bhatia, Nan Boden, Al Borchers, Rick Boyle, Pierre-luc Cantin, Clifford Chao, Chris Clark, Jeremy Coriell, Mike Daley, Matt Dau, Jeffrey Dean, Ben Gelb, Tara Vazir Ghaemmaghami, Rajendra Gottipati, William Gulland, Robert Hagmann, C. Richard Ho, Doug Hogberg, John Hu, Robert Hundt, Dan Hurt, Julian Ibarz, Aaron Jaffey, Alek Jaworski, Alexander Kaplan, Harshit Khaitan, Daniel Killebrew, Andy Koch, Naveen Kumar, Steve Lacy, James Laudon, James Law, Diemthu Le, Chris Leary, Zhuyuan Liu, Kyle Lucke, Alan Lundin, Gordon MacKean, Adriana Maggiore, Maire Mahony, Kieran Miller, Rahul Nagarajan, Ravi Narayanaswami, Ray Ni, Kathy Nix, Thomas Norrie, Mark Omernick, Narayana Penukonda, Andy Phelps, Jonathan Ross, Matt Ross, Amir Salek, Emad Samadiani, Chris Severn, Gregory Sizikov, Matthew Snelham, Jed Souter, Dan Steinberg, Andy Swing, Mercedes Tan, Gregory Thorson, Bo Tian, Horia Toma, Erick Tuttle, Vijay Vasudevan, Richard Walter, Walter Wang, Eric Wilcox, and Doe Hyun Yoon. In-datacenter performance analysis of a tensor processing unit. In Proceedings of the 44th Annual International Symposium on Computer Architecture, ISCA ’17, pages 1–12, New York, NY, USA, 2017. ACM. [52] Patrick Judd, Jorge Albericio, Tayler Hetherington, Tor M. Aamodt, and Andreas Moshovos. Stripes: Bit-serial deep neural network computing. In The 49th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO-49, pages 19:1–19:12, Piscataway, NJ, USA, 2016. IEEE Press. [53] Patrick Judd, Jorge Albericio, Tayler H. Hetherington, Tor M. Aamodt, Natalie D. Enright Jerger, Raquel Urtasun, and Andreas Moshovos. Reduced-precision strategies for bounded memory in deep neural nets. CoRR, abs/1511.05236, 2015. [54] Andrej Karpathy and Li Fei-Fei. Deep visual-semantic alignments for generating image descriptions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3128–3137, 2015. [55] Viacheslav Khomenko, Oleg Shyshkov, Olga Radyvonenko, and Kostiantyn Bokhan. Accelerating recurrent neural network training using sequence bucketing and multi-gpu data parallelization. CoRR, abs/1708.05604, 2017. [56] Minje Kim and Paris Smaragdis. Bitwise neural networks. arXiv preprint arXiv:1601.06071, 2016. [57] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014. [58] Guillaume Klein, Yoon Kim, Yuntian Deng, Jean Senellart, and Alexander M Rush. Opennmt: Open-source toolkit for neural machine translation. arXiv preprint arXiv:1701.02810, 2017. 129 BIBLIOGRAPHY [59] Richard E. Korf. Multi-way number partitioning. In Proceedings of the 21st International Jont Conference on Artifical Intelligence, IJCAI’09, pages 538–543, San Francisco, CA, USA, 2009. Morgan Kaufmann Publishers Inc. [60] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 25, pages 1097–1105. Curran Associates, Inc., 2012. [61] Minjae Lee, Kyuyeon Hwang, Jinhwan Park, Sungwook Choi, Sungho Shin, and Wonyong Sung. Fpga-based low-power speech recognition with recurrent neural networks. In Signal Processing Systems (SiPS), 2016 IEEE International Workshop on, pages 230–235. IEEE, 2016. [62] Sicheng Li, Chunpeng Wu, Hai Li, Boxun Li, Yu Wang, and Qinru Qiu. Fpga acceleration of recurrent neural network based language model. In Field-Programmable Custom Computing Machines (FCCM), 2015 IEEE 23rd Annual International Symposium on, pages 111–118. IEEE, 2015. [63] Zhuohan Li, Di He, Fei Tian, Wei Chen, Tao Qin, Liwei Wang, and Tie-Yan Liu. Towards binary-valued gates for robust lstm training, 2018. [64] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Doll´ar, and C Lawrence Zitnick. Microsoft coco: Common objects in context. In European conference on computer vision, pages 740–755. Springer, 2014. [65] R. P. Lippmann. An introduction to computing with neural nets. IEEE ASSP Magazine, pages 4–22, April 1987. [66] Zachary Chase Lipton. A critical review of recurrent neural networks for sequence learning. CoRR, abs/1506.00019, 2015. [67] Xiaodong Liu, Jianfeng Gao, Xiaodong He, Li Deng, Kevin Duh, and Ye-Yi Wang. Representation learning using multi-task deep neural networks for semantic classification and information retrieval. 2015. [68] Gerald M Maggiora, David W Elrod, and Robert G Trenary. Computational neural networks as model-free mapping devices. Journal of chemical information and computer sciences, 32(6):732–741, 1992. [69] Yajie Miao, Mohammad Gowayyed, and Florian Metze. Eesen: End-to-end speech recognition using deep rnn models and wfst-based decoding. In Automatic Speech Recognition and Understanding (ASRU), 2015 IEEE Workshop on, pages 167–174. IEEE, 2015. [70] Micron Inc. TN-53-01: LPDDR4 System Power Calculator. https://www.micron.com/ support/tools-and-utilities/power-calc. [71] Naveen Muralimanohar, Rajeev Balasubramonian, and Norman P Jouppi. Cacti 6.0: A tool to model large caches. HP Laboratories, pages 22–31, 2009. 130 BIBLIOGRAPHY [72] NVIDIA. NVIDIA TEGRA X1 new mobile superchip. http://international.download. nvidia.com/pdf/tegra/Tegra-X1-whitepaper-v1.0.pdf. [73] Vassil Panayotov, Guoguo Chen, Daniel Povey, and Sanjeev Khudanpur. Librispeech: an asr corpus based on public domain audio books. In 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5206–5210. IEEE, 2015. [74] Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: a method for automatic evaluation of machine translation. In Proceedings of the 40th annual meeting on association for computational linguistics, pages 311–318. Association for Computational Linguistics, 2002. [75] Eunhyeok Park, Dongyoung Kim, and Sungjoo Yoo. Energy-efficient neural network accelerator based on outlier-aware low-precision computation. In Proceedings of the 45th Annual International Symposium on Computer Architecture, ISCA ’18, page 688–698. IEEE Press, 2018. [76] Seung-min Park, Daeyoun D Won, Brian J Lee, Diego Escobedo, Andre Esteva, Amin Aalipour, Jessie Ge T, Jung Ha Kim, Susie Suh, Elliot H Choi, Alexander X Lozano, Chengyang Yao, Sunil Bodapati, Friso B Achterberg, Jeesu Kim, Hwan Park, Youngjae Choi, Woo Jin Kim, Jung Ho Yu, Alexander M Bhatt, Jong Kyun Lee, Ryan Spitler, Shan X Wang, and Sanjiv S Gambhir. A mountable toilet system for personalized health monitoring via the analysis of excreta. Nature Biomedical Engineering, pages 1–12, 2020. [77] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In NIPS-W, 2017. [78] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. In NIPS Autodiff Workshop, 2017. [79] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, pages 8024–8035, 2019. [80] Mohammad Rastegari, Vicente Ordonez, Joseph Redmon, and Ali Farhadi. Xnor-net: Imagenet classification using binary convolutional neural networks. In European Conference on Computer Vision, pages 525–542. Springer, 2016. [81] M. Riera, J. Arnau, and A. Gonz´alez. Cgpa: Coarse-grained pruning of activations for energy-efficient rnn inference. IEEE Micro, 39(5):36–45, Sep. 2019. [82] Marc Riera, Jose-Maria Arnau, and Antonio Gonz´alez. Computation reuse in dnns by exploiting input similarity. In Proceedings of the 45th Annual International Symposium on Computer Architecture, pages 57–68. IEEE Press, 2018. [83] Anthony Rousseau, Paul Del´eglise, and Yannick Esteve. Ted-lium: an automatic speech recognition dedicated corpus. In LREC, pages 125–129, 2012. 131 BIBLIOGRAPHY [84] Sebastian Ruder. An overview of gradient descent optimization algorithms. arXiv preprint arXiv:1609.04747, 2016. [85] Christopher M. Sadler and Margaret Martonosi. Data compression algorithms for energyconstrained devices in delay tolerant networks. In Proceedings of the 4th International Conference on Embedded Networked Sensor Systems, SenSys ’06, page 265–278, New York, NY, USA, 2006. Association for Computing Machinery. [86] Ananda Samajdar, Jan Moritz Joseph, Yuhao Zhu, Paul Whatmough, Matthew Mattina, and Tushar Krishna. A systematic methodology for characterizing scalability of dnn accelerators using scale-sim. [87] Ananda Samajdar, Yuhao Zhu, Paul Whatmough, Matthew Mattina, and Tushar Krishna. Scale-sim: Systolic cnn accelerator simulator. arXiv preprint arXiv:1811.02883, 2018. [88] Murat H¨usn¨u Sazlı. A brief review of feed-forward neural networks. 2006. [89] Mike Schuster and Kuldip K Paliwal. Bidirectional recurrent neural networks. IEEE Transactions on Signal Processing, 45(11):2673–2681, 1997. [90] Frank Seide and Amit Agarwal. Cntk: Microsoft’s open-source deep-learning toolkit. In Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, pages 2135–2135, New York, NY, USA, 2016. ACM. [91] Mohammad Javad Shafiee, Brendan Chywl, Francis Li, and Alexander Wong. Fast yolo: A fast you only look once system for real-time embedded object detection in video. arXiv preprint arXiv:1709.05943, 2017. [92] H. Sharma, J. Park, N. Suda, L. Lai, B. Chau, V. Chandra, and H. Esmaeilzadeh. Bit fusion: Bit-level dynamically composable architecture for accelerating deep neural network. In 2018 ACM/IEEE 45th Annual International Symposium on Computer Architecture (ISCA), pages 764–775, June 2018. [93] Franyell Silfa, Gem Dot, Jose-Maria Arnau, and Antonio Gonz´alez. E-pur: An energyefficient processing unit for recurrent neural networks. In Proceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques, PACT ’18, pages 18:1– 18:12, New York, NY, USA, 2018. ACM. [94] Franyell Silfa, Gem Dot, Jose-Maria Arnau, and Antonio Gonz´alez. Neuron-level fuzzy memoization in rnns. In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture, MICRO ’52, page 782–793, New York, NY, USA, 2019. Association for Computing Machinery. [95] Avinash Sodani and Gurindar S. Sohi. Dynamic instruction reuse. ISCA ’97, pages 194–205, 1997. [96] V Subramaniyaswamy, R Logesh, M Abejith, Sunil Umasankar, and A Umamakeswari. Sentiment analysis of tweets for estimating criticality and security of events. In Improving the Safety and Efficiency of Emergency Services: Emerging Tools and Technologies for First Responders, pages 293–319. IGI Global, 2020. 132 BIBLIOGRAPHY [97] Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. In Advances in neural information processing systems, pages 3104–3112, 2014. [98] Daniel Svozil, Vladimir Kvasnicka, and Jiri Pospichal. Introduction to multi-layer feedforward neural networks. Chemometrics and intelligent laboratory systems, 39(1):43–62, 1997. [99] Synopsys. https://www.synopsys.com/. [100] Jie Tang, Dawei Sun, Shaoshan Liu, and Jean-Luc Gaudiot. Enabling deep learning on iot devices. Computer, 50(10):92–96, 2017. [101] Alexander Toshev and Christian Szegedy. Deeppose: Human pose estimation via deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1653–1660, 2014. [102] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998–6008, 2017. [103] Oriol Vinyals, Igor Babuschkin, Wojciech M. Czarnecki, Micha¨el Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang, Laurent Sifre, Trevor Cai, John P. Agapiou, Max Jaderberg, Alexander S. Vezhnevets, R´emi Leblond, Tobias Pohlen, Valentin Dalibard, David Budden, Yury Sulsky, James Molloy, Tom L. Paine, Caglar Gulcehre, Ziyu Wang, Tobias Pfaff, Yuhuai Wu, Roman Ring, Dani Yogatama, Dario W¨unsch, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy Lillicrap, Koray Kavukcuoglu, Demis Hassabis, Chris Apps, and David Silver. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350–354, Nov 2019. [104] Oriol Vinyals, Alexander Toshev, Samy Bengio, and Dumitru Erhan. Show and tell: Lessons learned from the 2015 MSCOCO image captioning challenge. CoRR, abs/1609.06647, 2016. [105] Guibin Wang, YiSong Lin, and Wei Yi. Kernel fusion: An effective method for better power efficiency on multithreaded gpu. In Proceedings of the 2010 IEEE/ACM Int’l Conference on Green Computing and Communications & Int’l Conference on Cyber, Physical and Social Computing, pages 344–350. IEEE Computer Society, 2010. [106] Peiqi Wang, Xinfeng Xie, Lei Deng, Guoqi Li, Dongsheng Wang, and Yuan Xie. Hitnet: Hybrid ternary recurrent neural network. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS’18, page 602–612, Red Hook, NY, USA, 2018. Curran Associates Inc. [107] Shuo Wang, Zhe Li, Caiwen Ding, Bo Yuan, Qinru Qiu, Yanzhi Wang, and Yun Liang. C-lstm: Enabling efficient lstm using structured compression techniques on fpgas. In Proceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, FPGA ’18, page 11–20, New York, NY, USA, 2018. Association for Computing Machinery. [108] G. M. Weiss, J. L. Timko, C. M. Gallagher, K. Yoneda, and A. J. Schreiber. Smartwatchbased activity recognition: A machine learning approach. In 2016 IEEE-EMBS International Conference on Biomedical and Health Informatics (BHI), pages 426–429, 2016. 133 BIBLIOGRAPHY [109] Paul J Werbos. Backpropagation through time: what it does and how to do it. Proceedings of the IEEE, 78(10):1550–1560, 1990. [110] Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. Google’s neural machine translation system: Bridging the gap between human and machine translation. arXiv preprint arXiv:1609.08144, 2016. [111] Haiying Xu, Christopher J. F. Pickett, and Clark Verbrugge. Dynamic purity analysis for java programs. PASTE ’07, pages 75–82, 2007. [112] Reza Yazdani, Olatunji Ruwase, Minjia Zhang, Yuxiong He, Jose-Maria Arnau, and Antonio Gonz´alez. Lstm-sharp: An adaptable, energy-efficient hardware accelerator for long shortterm memory, 2019. [113] Joe Yue-Hei Ng, Matthew Hausknecht, Sudheendra Vijayanarasimhan, Oriol Vinyals, Rajat Monga, and George Toderici. Beyond short snippets: Deep networks for video classification. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2015. [114] Minjia Zhang, Samyam Rajbhandari, Wenhan Wang, and Yuxiong He. Deepcpu: Serving rnn-based deep learning models 10x faster. In 2018 USENIX Annual Technical Conference (USENIX ATC 18), pages 951–965, Boston, MA, July 2018. USENIX Association. [115] Qian Zhang, Ting Wang, Ye Tian, Feng Yuan, and Qiang Xu. Approxann: An approximate computing framework for artificial neural network. In Proceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition, DATE ’15, pages 701–706, San Jose, CA, USA, 2015. EDA Consortium. [116] Qian Zhang, Ting Wang, Ye Tian, Feng Yuan, and Qiang Xu. Approxann: An approximate computing framework for artificial neural network. In Proceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition, DATE ’15, pages 701–706, San Jose, CA, USA, 2015. EDA Consortium. [117] Xiaofan Zhang, Xinheng Liu, Anand Ramachandran, Chuanhao Zhuge, Shibin Tang, Peng Ouyang, Zuofu Cheng, Kyle Rupnow, and Deming Chen. High-performance video content recognition with long-term recurrent convolutional network for fpga. In 2017 27th International Conference on Field Programmable Logic and Applications (FPL), pages 1–4. IEEE, 2017. 134 Glossary WER (Word Error Rate). Number of insertions plus deletions plus substitutions that are required to convert the recognized word sequence into the reference word sequence, divided by the total number of words of the reference utterance. Real-Time-Factor (Real Time Factor). It is the ratio between the amount of time required to decode an audio fragment and the length of the fragment. For example, a real-time factor of 0.7 xRT means that each second of audio requires 0.7 seconds to decode (lower RTF means faster decoding). Bleu (Bleu). It is a metric for evaluating a generated sentence to a reference sentence. It works by counting matching n-grams in the candidate translation to n-grams in the reference text. The larger the Bleu the better. Inference (Inference). In the context of machine learning, it refers to using a trained model to make a prediction. Deep-Neural-Network (DNN). A machine-learning algorithm which includes one input and one output layer of neurons plus several hidden layers. It is trained with a large amount of data to find the correct mathematical representation to compute the network output from a given input. Recurrent-Neural-Network (RNN). A machine-learning primitive consisting of several layers composed of one RNN cell. Each RNN cell recurrently processes an input sequence while storing information from past evaluations. Then, this information is used to compute the next output of the network. DNN-Accelerator (DNN Accelerator). A class of specialized computer system designed to improve the performance and energy efficiency of DNN algorithms. Sentiment-Analysis(Sentiment Analysis). It refers to the classification of emotions (positive, negative, and neutral) within text data using text analysis techniques such as natural language processing. cuDNN (cuDNN). A GPU-optimized library of primitives for deep neural networks. cuBlas (cuBlas). A GPU-accelerated implementation of the basic linear algebra subroutines (BLAS). Qm.n (Qm.n). It is a fixed-point format to represent decimal numbers. The mrepresents the bit-width of the integer part, whereas the nrepresents the bit-width of the fractional part. 135 BIBLIOGRAPHY Batch (Batch). It is a group of input samples that are processed concurrently either during inference or training. Batch Size (Batch Size). It is the number of samples in a batch. Verilog (Verilog). It is a Hardware Description Language for describing electronic circuits and systems. CACTI (CACTI). It is an integrated model for cache and memory access time, cycle time, area, leakage, and dynamic power. Output-Stationary-Dataflow (Output Stationary Dataflow). It is a dataflow where the accumulation of partial sums for the same output activation value is kept local in a register file. In order to keep the accumulation of each partial sum stationary in the register file, input activations are streamed across the processing elements. Neuron (Neuron). It is the basic computation unit of neural networks. Its output is computed as the dot product between the input and synaptic weights. Convolutional-Neural-Networks (Convolutional-Neural-Networks). They are DNNs that employ convolution operations instead of the general matrix multiplication in at least one of their layers. CNNs are normally employed for image classification. Synaptic-Weights (Synaptic Weights). They represent the connections between neurons. Typically, they determine the relevance of the information passed by a neuron to the network input and/or with other neurons. 136