Dissecting FLOPs along input dimensions for GreenAI cost estimations

Artificial Intelligence, especially in its modern incarnation of Deep Learning, has achieved remarkable results in recent years, matching – and frequently trespassing – human capabilities in a number of different tasks. These techniques usually require the deployment of massive computational resources, with huge implications in terms of energy consumption. To make a couple of examples the hyper-realistic Generative Adversarial Network for face generation in [19] required training on 8 Tesla V100 GPUs for 4 days; the training of BERT [12], a well known generative model for NLP, takes about 96 hours on 64 TPU2 chips. Researchers at the University of Massachusetts [26] have recently performed a life cycle assessment relative to the training of large state-of-the-art AI models, discovering that the process can emit a quantity of carbon dioxide roughly equivalent to the lifetime emissions of five medium cars. Other authors reached similar conclusions [20].

Until a few years ago, the ecological impact of artificial intelligence was entirely neglected by researchers and industry, who were mostly focused on improving performance at any cost. However, this has changed in recent years, with a growing awareness that this trend of research is not sustainable any more [28], and an increased attention towards energetic efficiency [27].

The GreenAI paper [25] summarizes well the goal and objectives of the new philosophy: it promotes a new practice in Deep Learning, that is more focused on the social costs of training and running models [2, 7, 15], encouraging the investigation of increasingly efficient models [21, 5].

To this aim, it is essential to identify widely acceptable and reliable metrics to assess and compare the cost and efficiency of different models. Several metrics are investigated and discussed in [25]; in conclusion, the number of Floating Point Operations (FLOPs) is advocated and promoted, since it is easily computed for Neural Networks while offering a hardware independent, schematic but meaningful indication of the actual computation cost of the model [20].

Unfortunately, the mere computation of FLOPs does not cope well with the massively parallel architectures (GPU and TPU) typically used in Deep Learning [17]. Efficient implementation of neural networks on these architectures depends both on complex algorithms for General Matrix Multiplication (GEMM) [18] and sophisticated load balancing techniques [13] splitting the workload on the different execution units. As we shall see, these algorithms usually perform better for specific layers and, especially, along specific axes of the input dimension of these layers.

Our claim is that it is possible to study the performance of neural layers (especially, convolutions) as \sayblack boxes, measuring the execution time for a number of different configurations, and separately investigating the execution time for increasing dimensions along different axis.

As a result, we propose a simple correction to the formula used to compute FLOPs for convolutional layers, that provides better estimations of their actual cost, and helps to understand the discrepancy with respect to the cost of different layers.

In this section we review some of the metrics that can be used to measure the efficiency of an AI algorithm, following the discussion of [25].

The basic operation that dominates training of Neural Network models is the dense matrix-matrix product. This operation is often referred in the technical literature as GEMM (for GEneral Matrix Multiply), owing its name to the xGEMM family of functions provided by the Basic Linear Algebra Subprograms (BLAS) library [6]. BLAS is a widely used collection of subroutines implementing basic operations involving vectors and matrices, such as vector addition, dot product, vector-matrix multiplication and so on; these functions act as building blocks on which more complex linear algebra computations can be programmed. Being at the core of many applications, the performance of BLAS primitives are critical, so most hardware vendors provide their own optimized implementations, e.g., cuBLAS for nVidia GPUs [11], and clBLAS for OpenCL devices [8], including various brands of GPUs and multicore processors.

A GEMM operation takes the general form:

Assuming that the size of $\mathbf{A}$ is $m\times k$ and the size of $\mathbf{B}$ is $k\times n$, then the size of $\mathbf{C}$ must be $m\times n$ and the direct computation of (2) using vector dot products requires:

• •

  $2mkn+mn$ FLOPs for the matrix product $\alpha\mathbf{AB}$, assuming that dot products are implemented with an inner loop involving a multiply-accumulate operation like $s\leftarrow s+x_{i}y_{i}$

• •

  $mn$ FLOPs for the computation of $\beta\mathbf{C}$

• •

  $mn$ additional FLOPs for the computation of the matrix sum $\alpha\mathbf{AB}+\beta\mathbf{C}$

We can apply this result for the layers of a Neural Network. Consider a Dense layer, with input and output dimensions $D_{\textit{in}}$ and $D_{\textit{out}}$, respectively. We need to compute the product between the weight matrix of size $D_{\mathit{out}}\times D_{\mathit{in}}$ and the input, plus a bias term $B$ of dimension $D_{out}$; therefore, the number of FLOPs is

As above, we omit the lower order terms as they are asymptotically negligible. As a consequence, we will consider a Dense layer to have a number of FLOPs equal to

The case of a convolutional layer is slightly more complex. Let us consider the case of a 2D convolution. Let $(W_{\textit{in}},H_{\textit{in}},C_{\textit{in}})$ the dimension of the input (written with the notation (Width, Height, Channels)), $(W_{\textit{out}},H_{\textit{out}},C_{\textit{out}})$ the dimension of the output (depending on the stride and number of kernels), and let $K_{1},K_{2}$ be the dimensions of the kernel. Then, the number of FLOPs is given by

In the following, we shall frequently consider the case of convolutions with stride $1$ in \saysame padding modality. In this case, $W_{\textit{in}}=W_{\textit{out}}$ and $H_{\textit{in}}=H_{\textit{out}}$, so we shall drop the subscripts, and just write $W$ and $H$. Moreover, in the frequent case kernels are squared, we drop the subscripts in $K_{1},K_{2}$ and just write $K$.

A dense layer of dimension $D_{in}\times D_{out}$ is the same as a unary convolution $(K=1)$ with $C_{in}=D_{in}$, $C_{out}=D_{out}$ and $H=W=1$; it is easy to experimentally check that both require the same time to be evaluated. However, as soon as we distribute the total number of FLOPs of equation (4) across different dimensions, we observe a significant speedup, that has no justification in terms of FLOPs. This raises concerns about the use of FLOPs for estimating running time (and hence energy consumption). In this section we provide empirical evidence of this phenomenon.

In Figure 1, we compare the time required to evaluate a dense layer with several different convolutional layers with a same amount of FLOPs computed according to (4); the execution time has been measured on an NVIDIA Quadro T2000 graphics card and a Intel Core i7-9850H CPU. Times are averaged over 2000 experiments for each scenario.

In particular, in Table 1(a) we evaluate a scenario of maximum size compatible with our hardware, corresponding to a Dense layer of size $12800\times 12800$ ($163,852,800$ parameters), and compare it with several different convolutional layers with the same total amount of FLOPs. The dense layer takes about $6.4$ milliseconds (ms), while a unary convolution with $C_{in}=C_{out}=3200$ on an input of spatial dimension $4\times 4$ just takes $0.46$ ms, approximately $16$ times faster.

In Figure 1(b), we repeat the same experiment, varying the total amount of flops with powers of $2$. For the dense layer we go from dimension $100\times 100$ to dimension $(100\times 2^{7})\times(100\times 2^{7})$.

In the following experiments, we keep the number of FLOPs constant while we increase some dimensions and proportionally decrease others. If (4) had a good correlation with time, we should observe straight horizontal lines.

In all experiments, we consider four different amounts of FLOPs identified by different colors: $2025\times 10^{6}$ (red line in Figure 2), $900\times 10^{6}$ (green line), $490\times 10^{6}$ (orange line) and $225\times 10^{6}$ (blue line). We progressively increase $K$ from $1$ to $30$. In the first experiment, we compensate it by enlarging the input and output dimension of channels ($C_{in}$ and $C_{out}$), keeping a constant (small) spatial dimension $10\times 10$.

In the second test we compensate the growing convolutions by reducing the spatial dimensions, starting from an initial dimension of $300\times 300$. Channels are constant, in this case. Result are reported in Figure 2.

In the case of the first experiment (Figure 2(a)), apart from the exceptional performance of $1\times 1$ convolutions already discussed in [17], we observe the expected constant behavior. However, we have a completely different result in the case of the second experiment (Figure 2(b)). Here the execution time increases with the kernel dimension, possibly at a quadratic rate; this growth should have been compensated by the simultaneous decrease along both spatial dimensions, but clearly this is not the case.

By comparing the results of the two experiments, we can draw another conclusion. Remember that the number of FLOPs along lines of the same color is the same; therefore, the nonlinear behaviour in Figure 2(b) is not due to an overhead but, on the contrary, there is an important speed up of the computation of increasing relevance for small kernels. In other words, the formula computing FLOPs is overestimating the total number of operations, presumably because it does not take into consideration the fact that convolutions can be easily parallelized along spatial dimensions (but not quite so along kernel dimensions).

The goal of the work is to derive a simple correction to the formula for computing FLOPs explaining the observed behaviours. The correction might depend on the specific hardware, but it should be possible to evaluate the relevant parameters in a simple way.

In this section we introduce our correction to the formula for computing FLOPs, that we call $\alpha$-FLOPs. Instead of FLOPs, that count the total number of floating point operations, $\alpha$-FLOPs provide an estimation of the \sayperceived FLOPs, that are less than FLOPS due to parallelism. The crucial idea is that when we run in parallel an algorithm with a multidimensional input there is no reason to suppose that the total number of operations have similar latency along different dimensional axes. Our proposal is to adjust the formula for computing FLOPs by multiplying it by the following scaling factor:

The parameters $\beta_{K}$ and $\gamma_{K}$ can be easily evaluated by regression on a given GPU/TPU. Although they are hardware dependent, some preliminary investigations seem to suggest that fluctuations are smaller than expected.

For the purposes of this article, using an Invida Quadro T2000 GPU we obtained good predictions just distinguishing two cases: $K=1$ and $K>1$. For $K=1$, $\beta_{K}=0.02$ and $\gamma_{K}=.99$; for $K>1$, $\beta_{K}=0.001$ and $\gamma_{K}=.56$.

Before discussing the main properties of $\alpha_{K}(S)$, let us have a look at the prediction of the execution time (dashed line) for the problematic experiments shown above. More examples will be presented in Section 6.

The experiment in Figure 1 is replicated, with the time predicted by means of $\alpha$-FLOPs, in Figure 3(b). In the Table on the left, we give the computed and predicted times for the convolutional configurations (1-4) with 327.68M FLOPs.

Similarly, in Figure 4 we show the predicted execution time for the experiments of Figure 2.

We conducted several experiments to assess the rate of grow of the execution time along different input dimensions. Data providing the base for this paper are available on Github (https://github.com/asperti/alpha_flops_dataset), together with analysis tools and plotting facilities, including the predictions by means of $\alpha$-FLOPs. Additional data are currently being collected.

All experiments discussed in this Section involve convolutions where we progressively increase the dimension of a specific input axis $x$, keeping a constant dimension for the others axes $X_{c}$. For each experiment, we draw the execution time for three different dimensions of an auxiliary axis $x_{\textit{aux}}$ in $X_{c}$. We found this more understandable than plotting three dimensional surfaces, that would be quite difficult to draw and decipher.

In the case of the plot in Figure 5(a), $x$ is $W$, and $x_{\textit{aux}}$ is $C_{\textit{in}}$; $H=100$ and the Kernel dimension is $3\times 3$. For Figure 5(b), $x$ is $C_{\textit{out}}$, and $x_{\textit{aux}}$ is $C_{\textit{in}}$; $H=W=100$ and the kernel dimension is $3\times 3$. For Figure 6(a), $x$ is $C_{\textit{out}}$, and $x_{\textit{aux}}$ is $H$; $C_{\textit{in}}=50$ and the kernel dimension is $1\times 1$. Finally, for Figure 6(b), $x$ is $C_{\textit{in}}$, and $x_{\textit{aux}}$ is $K$; $H=W=10$ and $C_{\textit{out}}=1000$.

In this paper we introduced the notion of $\alpha$-FLOPs that is meant to provide a simple numerical correction to the mismatch between FLOPs and execution time in case of hardware equipped with massively parallel processing units like GPUs or TPUs. Since this kind of hardware is the norm for AI applications based on Deep Neural Networks, $\alpha$-FLOPS may become an important tool to compare the efficiency of different networks on a given hardware.

The definition of $\alpha$-FLOPs is based on the crucial observation that, in case of an input with multiple dimensions, the computational speedup offered by parallelism is typically far from uniform along the different axes. In particular, we provided extensive empirical evidence that growing spatial (and batchsize) dimensions in convolutional layers has less impact than growing different dimensions. The idea of dissecting the cost along the different input dimensions was inspired by recent investigations of the first author on computational complexity over finite types [4].

The notion of $\alpha$-FLOPs lays between the number of parameters of the layer, and the traditional notion of FLOPs; in a sense, it can be understood as a revaluation of the former as a measure of cost: if it is true that, in the case of convolutions, the number of parameters does not take into account the actual cost of the convolution, the traditional notion of FLOPs seems to largely overestimate it.

Much work is still ahead. On the experimental side, we are currently collecting more data, on architectures with different computing capabilities. On the theoretical side, it would be interesting to provide a low-level algorithmic justification of $\alpha$-FLOPs. The formula itself, that was derived empirically, can be eventually fine-tuned and possibly improved, both in view of additional observations, and of a better understanding of the phenomenon. In particular, we mostly focused on the spatial dimension, since it is the axis most affected by parallelism, but the dependency along different axes does eventually deserve additional investigation.

In this article, we mostly focused on convolutional and dense layers, since they are the most computationally intensive layers in Neural Networks. Extending the work to additional layers, or more sophisticated forms on convolutions, like Depth-Separable Convolutions, is another major research direction.