MACs, FLOPs and operations

Start with one neuron that has four inputs. Its output before the activation function is w₁x₁ + w₂x₂ + w₃x₃ + w₄x₄. A processor evaluates that as four identical steps: multiply a weight by an input, add the product to a running total. Each step is one multiply-accumulate operation, and the whole of neural network inference is this step repeated a few hundred million times.

The definition is standard well beyond this course. The Wikipedia entry on the multiply-accumulate operation gives exactly a ← a + (b × c), and notes that IEEE 754-2008 defines a fused multiply-add that performs the whole step with a single rounding. Sze, Chen, Yang and Emer call the MAC "the fundamental component" of DNN processing in their survey of efficient DNN hardware. Counting MACs is therefore counting what the hardware executes, not an abstraction layered over it.

From one neuron to a matrix-vector product

A layer of m neurons that each read the same n inputs is a matrix-vector multiplication: an m × n weight matrix times an n-vector. Each of the m outputs needs n MACs, one per weight in its row, so the product costs m · n MACs. Notice that this is also the number of weights. In a matrix-vector product, every weight is touched exactly once.

Feed the layer a batch of inputs at once and the vector becomes a matrix. The slide renames the dimensions here: the input count becomes k and the letter n is reused for the batch, the number of columns of B. The result is a general matrix-matrix multiplication: A of size m × k times B of size k × n gives C of size m × n. Every one of the m · n cells of C is a dot product over the shared dimension k, so it costs k MACs, and the whole product costs m · n · k.

Why a whole network reduces to this

A Linear layer is literally a matrix-vector product at batch size one and a GEMM for a batch. Convolution looks different but is executed the same way: frameworks reorder the input patches into columns (the im2col trick described in the CS231n notes) so that a convolution becomes one large GEMM, and the MobileNets paper points out that this is why convolutions can ride on "highly optimized general matrix multiply (GEMM) functions". NVIDIA's performance guide states the cost of a GEMM as 2 · M · N · K floating point operations because "each FMA is 2 operations, a multiply and an add", which previews the FLOP conversion at the end of this part. Once you can count MACs for a matrix product, you can count them for every layer.

Take the first layer of AlexNet. One filter spans all 3 input channels with an 11 × 11 window, so it holds 3 × 11 × 11 = 363 weights. Producing a single output pixel is one dot product of those 363 weights against a patch of the image: 363 MACs. But the filter does not produce one pixel. It slides to every one of the 55 × 55 = 3,025 output positions, and there are 96 filters. So the layer costs 363 × 3,025 × 96 = 105,415,200 MACs from only 34,848 weights.

That example contains the whole rule. In a convolution layer every weight is applied once per output position, so the MAC count is the parameter count from part 02 multiplied by the output height and width:

The other rows of the slide's table follow from the same idea. A Linear layer has h_o = w_o = 1, so its MACs equal its parameters, c_o · c_i. A Grouped convolution splits the channels into g groups, so each filter sees only c_i / g input channels and both parameters and MACs are divided by g. A Depthwise convolution is the extreme case g = c_i = c_o: each filter sees exactly one channel, so c_i disappears from the formula entirely and only c_o · k_h · k_w weights remain, each still applied h_o · w_o times.

How a convolution slides, how padding and stride set the output size, and how groups partition channels were covered in lecture 02, part 02 and part 03. This part only counts, and it takes the kernel size and output shape of each layer as given.

Why this mirrors part 02

Goodfellow, Bengio and Courville explain parameter sharing in one sentence that is the whole story of this part: sharing "does not affect the runtime of forward propagation, it is still O(k × n), but it does further reduce the storage requirements of the model to k parameters". Convolution saves storage by reusing weights, and reusing weights is exactly what makes the arithmetic grow. That is why parts 02 and 04 are mirror images. The layers cheapest to store are the most expensive to run.

Worked example: the MobileNet block that makes depthwise worth it

The MobileNets paper replaces one standard 3 × 3 convolution with a depthwise 3 × 3 followed by a pointwise 1 × 1. Its equations 4 and 5 give the depthwise and separable costs, and dividing by the standard cost gives the ratio 1 / N + 1 / D_K², where N is the number of output channels and D_K the kernel size. The formulas in the table let you reproduce that with real numbers.

The calculator below lets you scrub every symbol in the table. Its FLOPs, OPs and hardware rows are explained in the last concept of this part; for now watch how parameters and MACs move apart as the output size grows.

Slide 25 hands you the eight weighted layers of AlexNet with their output shapes and an empty MACs column. Slide 26 fills it in, except for one layer hidden behind a question mark. Work through the column yourself before you read the answers. Every entry is the formula from the previous concept with the layer's numbers substituted, and the pooling layers contribute nothing because they hold no weights.

Put the parameters next to the MACs

The total is not the interesting number. The interesting number appears when you place the parameter counts from part 02 beside the MACs and add a column for their ratio, which by the previous concept is just h_o · w_o.

The five convolutions hold 2,332,704 parameters, under 4% of the network, yet perform 665,784,864 MACs, 92% of the compute. The three linear layers hold 58,621,952 parameters, 96% of the network, yet perform only 58,621,952 MACs, 8% of the compute. The last column explains it: each conv1 weight is used 3,025 times, each conv3 to conv5 weight 169 times, each linear weight once. Large spatial maps early in the network make convolution compute heavy. Large c_i · c_o products late in the network make the linear layers parameter heavy.

What this means for making a model faster

The inversion sets the strategy for the rest of the course. Pruning or quantizing the linear layers shrinks Model size dramatically, because that is where the weights are, but it barely changes the MAC count and therefore barely changes computation time. To make inference faster you must attack the convolutions: fewer channels, grouped or depthwise filters as in MobileNet, or a lower input resolution so that h_o · w_o shrinks in every layer at once. The pruning lecture that follows will keep returning to this table, and when you profile a model for the research project, report both columns, not one.

A MAC hides two arithmetic operations: a multiply and an add. When each is counted as one floating point operation, one MAC is two FLOPs, and AlexNet's 724,406,816 MACs become 1,448,813,632 FLOPs. The slide rounds that to 1.4G; the exact figure is 1.449G, and showing the factor of two matters more than the rounding.

The count on its own says nothing about time. To get time you need to know how fast a processor can drain it, and that is a different quantity with an almost identical name. FLOPS, with a capital S, is floating point operations per second: a throughput that belongs to the hardware. FLOPs, with a lowercase s, is a plural count that belongs to the model. TOP500 ranks supercomputers by exactly this rate, reporting Linpack results as Rmax and Rpeak in Flop/s, and NVIDIA's GPU performance background guide writes the time a math-limited kernel takes as its number of operations divided by the processor's math bandwidth, which is FLOPs over FLOPS.

This is the computation time term of the latency model on slide 8, where the numerator is a network specification and the denominator a hardware specification. Run AlexNet's count through a few devices and the scale of the answer changes by orders of magnitude while the model does not change at all.

OPs: the same count for any data type

The F in FLOP assumes floating point arithmetic. A quantized network, the kind you deploy on a microcontroller or an INT8 accelerator, stores weights and activations at an Bit width of 8 bits and multiplies integers. Those are not floating point operations, but they are still operations, and there are still two per MAC. The lecture therefore generalizes: an operation (OP) is one multiply or add of any data type, AlexNet is 724M × 2 = 1.4G OPs, and OPS is operations per second. The layer compute calculator in the second concept of this part uses OPS in its hardware box for exactly this reason: the formula for time does not care whether the operands were floats.

Slide 29 lists the ten works the lecture draws on. Six were used directly in this lecture's counting and examples; the other four appear here as context for the architectures and normalization layers of lecture 02 and the pruning lectures ahead.

Used in this lecture

• Dumoulin and Visin, Convolution arithmetic (GitHub repository and arXiv 1603.07285): the output-shape arithmetic behind every h_o × w_o in this part.
• Stanford CS231n, lecture 5, Image Classification with CNNs: parameter sharing, the output-size formula and im2col.
• Krizhevsky, Sutskever and Hinton, ImageNet Classification with Deep Convolutional Neural Networks, NeurIPS 2012: the AlexNet layers counted on slides 25 and 26.
• Sandler et al., MobileNetV2: Inverted Residuals and Linear Bottlenecks, CVPR 2018: the depthwise design that cuts both parameters and MACs, and the "MAdd" convention.
• Deng, Li, Han, Shi and Xie, Model Compression and Hardware Acceleration for Neural Networks: A Comprehensive Survey, Proceedings of the IEEE 108(4), 2020: the wider map of compression techniques that these metrics evaluate.
• Song Han, MIT 6.5940 TinyML and Efficient Deep Learning Computing, lecture 2: the direct source of slides 23 to 28.

Context for other lectures

• Ioffe and Szegedy, Batch Normalization, ICML 2015.
• Wu and He, Group Normalization, ECCV 2018.
• Simonyan and Zisserman, Very Deep Convolutional Networks for Large-Scale Image Recognition, ICLR 2015.
• He, Zhang, Ren and Sun, Deep Residual Learning for Image Recognition, CVPR 2016.