Matrix Multiplication FLOPs (2mnk) and Arithmetic Intensity

In everyday life

The spec sheet of an AI chip usually lists two kinds of numbers. One is how many calculations it can do per second. The other is how many bytes it can move from memory per second. For example, NVIDIA's H100 (announced in 2022, SXM version) does about 1,000 trillion 16-bit matrix calculations per second. It can move 3.35 TB per second.

So which number sets the speed of the AI you are running? The answer is "it depends on the calculation." This article counts the work in a matrix multiplication and the data it must move. Then it shows how to tell which of the two sets the speed.

"Why Are GPUs Used for AI?" explained that a GPU runs matrix calculations on many calculation units at the same time. This article goes one step further and focuses on counting.

How it works 1: vectors and matrices are "tables of numbers"

A list of numbers in a single row is called a vector. One student's scores in History, Math and English (80, 60, 70) form a vector of three numbers. In text AI, one word is represented by a vector of thousands of numbers.

Numbers arranged in a grid of rows and columns form a matrix. A matrix with m rows and k columns is written "m×k." An AI's weights are stored as matrices too. Weights are numbers that say how much importance to give each input.

Multiplying a matrix by a vector means doing one "multiply by the inputs, then add" for each row of the table. You get one answer per row. This is a matrix-vector product. Turning one student's scores into a STEM score and an arts score is this kind of calculation.

Calculate scores for 100 students at once, and the input becomes a table too (3×100). Now it is a matrix-matrix product. Its key feature is that the same table of weights is reused for all 100 students. When a chat AI builds its answer one word at a time, the calculation for one user is close to the first kind. Grouping many users together makes it closer to the second.

How it works 2: counting the calculations (2mnk)

Multiply an m×k matrix A by a k×n matrix B, and the result C is an m×n matrix. The number of columns in A and the number of rows in B must both be k, or you cannot multiply them. Each cell of the result comes from one row of A and one column of B: multiply k pairs of numbers and add them up.

One multiplication plus one addition is called a multiply-accumulate. It is also written MAC, from the English initials. The result has m×n cells, and each cell needs k multiply-accumulates, so the total is m×n×k.

In computing, a multiplication and an addition are often counted as one operation each. Then the total is 2×m×n×k. One operation counted this way is called a FLOP (one calculation on a decimal number, short for "floating-point operation"). NVIDIA's performance guides also count matrix multiplication as 2mnk.

Let's check with a small example. Multiply a 2×3 matrix by a 3×2 matrix. The result has 4 cells, and each needs 3 multiply-accumulates. That is 12 multiply-accumulates, or 24 FLOP. Counting with a triple loop written in Python gave 12 multiplications and 8 additions. There are fewer additions because the first product in each cell has nothing to be added to.

The gap is just the number of result cells (m×n). In real calculations, where k is in the thousands, it is less than 1/1,000 of the total, so 2mnk is the standard count. For two square matrices of 4,096×4,096, it is 2×4,096×4,096×4,096, about 137 billion FLOP.

The number of FLOP per second is called FLOPS, and it describes a chip's speed. With the prefix "tera" for trillion, it is written TFLOPS. Calculations on whole numbers are counted as "operations," and trillions of them per second are written TOPS.

How it works 3: counting the data moved

For the calculation circuits to work, the numbers of A and B must be read from memory, and the result C must be written back. That is m×k+k×n+m×n numbers to read and write. Multiply by the bytes per number, and you get the amount of data moved.

The size of one number depends on its format. A 16-bit decimal number (FP16), common in AI, is 2 bytes. An 8-bit whole number (INT8) is 1 byte. "FP32 vs. FP16 vs. BF16 vs. INT8" compares the formats.

For the 4,096×4,096 example in FP16, the three matrices hold about 50 million numbers, or about 100 million bytes (about 100 MB). This counts the ideal case, where every number is moved only once. As we will see later, how the program is written can multiply the real amount many times over.

How it works 4: arithmetic intensity is "calculations per byte"

The number of calculations divided by the number of bytes moved is called arithmetic intensity. It tells you how many calculations each byte brought in can feed. The unit is FLOP/byte.

For a matrix-vector product, the arithmetic intensity is only about 1. Each FP16 weight (2 bytes) is used for one multiply-accumulate (2 FLOP), and then it is never needed again. NVIDIA's guide also explains that matrix-vector products have an arithmetic intensity below 1, so memory speed always sets their speed.

Matrix-matrix products are different. In the 4,096×4,096 example, about 137 billion FLOP divided by about 100 million bytes gives an arithmetic intensity of about 1,365. Each number moved is used thousands of times, once for each entry in a row or column of the result. You can think of arithmetic intensity as a measure of "how many times each number moved gets reused."

How it works 5: the roofline is the lower of two limits

A chip's speed has two limits. One is the number of calculations its circuits can do per second. The other is the bytes it can move per second (memory bandwidth) times the arithmetic intensity. Nothing can be calculated before the numbers arrive. So the real speed can never beat the lower of the two.

A graph of this, with arithmetic intensity across and calculation speed up, is called the roofline model. Williams and colleagues proposed it in 2009 as a way to estimate performance. The sloped line on the left is the limit set by moving data. The flat line on the right is the calculation limit.

You find the arithmetic intensity where the two lines meet by dividing the calculation limit by the memory bandwidth. For the H100, about 989 trillion ÷ 3.35 trillion is about 300. For jobs below this value, the calculation circuits spend much of their time waiting for memory. This state is called memory-bound. The opposite, where the circuits work without a break, is called compute-bound.

A matrix-vector product for one user (arithmetic intensity about 1) sits far to the left of the bend. It can use only about 0.3% of the H100's calculation power. A large matrix multiplication (about 1,365) sits on the right and can run at the calculation limit.

How it works 6: batching reuses the same weights for many users

The simplest way to raise arithmetic intensity is to group inputs together. The number of inputs processed together is called the batch size. Read the weight table once, and you can use it for everyone in the group.

Take a 4,096×4,096 weight table (about 34 million bytes in FP16) with a batch of B. While B is small, the arithmetic intensity is also about B. The calculations grow B times, but the data moved stays close to just the weights. To reach the H100's bend at about 300, you have to group several hundred users (see the table in "By the numbers" later).

How it works 7: tiling reuses data in small on-chip memory

So far we have assumed that every number is moved only once. But the fast memory right next to the calculation circuits (on-chip memory) is fairly small. It is much smaller than outside memory such as HBM, and a large matrix does not fit in it whole.

Without any tricks, you would reread a row of A and a column of B from outside memory for each result cell. Then the data moved grows to about the number of multiply-accumulates. The arithmetic intensity falls to around 1, no better than a matrix-vector product.

So the matrices are cut into small square blocks. A block of A and a block of B are loaded into the chip. Every calculation those two blocks allow is finished before moving on to the next pair. This method is called tiling. If each block is b numbers on a side, the data moved from outside memory drops to about 1/b of the no-trick case.

According to NVIDIA's guide, GPUs split the result matrix into blocks when they calculate. Special circuits such as Tensor Cores also multiply small blocks together in a single instruction.

How it works 8: image convolution can become a matrix multiplication

Image AI often uses convolution. This is the core step of a CNN (convolutional neural network). A small window (for example, 3×3 pixels) slides across the image, and the numbers in the window are multiplied by weights and added. Lay out each window's contents in a single row, and stack one row per window position. That makes a large matrix. Multiply it by the weight matrix, and the convolution becomes a matrix multiplication. This rearranging is called im2col.

The windows overlap, though, so rearranging copies the same number many times. With a 3×3 window moving one pixel at a time, one number can appear up to 9 times, which uses that much more memory. So another method builds the rearranged matrix bit by bit, inside the chip only (cuDNN paper, 2014). You can try counting the multiply-accumulates per layer with the CNN output size calculator.

How it works 9: quantization shortens numbers to move less

In AI, replacing decimal numbers with something shorter, such as whole numbers with fewer bits, is called quantization. It shrinks the size of each number. Going from FP16 to INT8 halves the bytes moved. Going from 32-bit decimals (FP32) cuts them to a quarter.

For a memory-bound job, halving the data moved roughly halves the time. For a one-user matrix-vector product, INT8 raises the arithmetic intensity to about 2. Compute-bound jobs gain too. On the H100's spec sheet, the INT8 calculation limit is twice the 16-bit one. But if numbers are made too coarse, the answers drift, so accuracy is checked while using it.

How it works 10: the systolic array builds reuse into the circuit

Picture multiply-accumulate circuits laid out in a grid. Numbers are handed from each circuit to its neighbor in turn, and the matrix multiplication happens along the way. This design is called a systolic array. H. T. Kung and C. E. Leiserson proposed it in the late 1970s. Data leaves memory, flows through the circuits in a regular rhythm, and returns to memory. In a 1982 article, Kung compared this flow to blood flowing in and out of the heart.

Google's first TPU calculates matrix multiplications this way. The weights stay in place in each circuit. Input numbers flow from left to right, and partial sums flow from top to bottom. Each number read from memory is used by the 256 circuits in its row, so memory reads drop sharply.

The first TPU had 256×256=65,536 8-bit multiply-accumulate circuits. It could do up to 92 trillion operations per second (2017 paper). The design builds the trick of raising arithmetic intensity into the layout of the circuits itself.

Common misconceptions

By the numbers: what changes with batch size

We estimated multiplying a 4,096×4,096 weight table (FP16) by a batch of inputs, using the H100's spec values. These are ideal values: calculating and moving data are assumed to overlap, and the longer of the two sets the time. "Compute" and "Move" are the time each takes (µs is a millionth of a second). "Busy" is the share of time the calculation circuits are working.

From batch 1 to 256, the time stays at about 10 to 11 µs, so grouping is pure gain. At 512, compute time passes move time. From there on, doubling the batch doubles the time. The speed per user stops improving, and only the wait for each run grows.

Learn more

• Terms in depth: arithmetic intensity / roofline model / systolic array / post-training quantization / mixed precision
• Compare in a table: AI training vs. inference / CPU vs. GPU vs. NPU / DDR vs. LPDDR vs. GDDR vs. HBM
• Try the numbers: memory bandwidth calculator / CNN output size and multiply-accumulate count
• See it in a figure: all figures (the roofline model, the GPU thread hierarchy)
• Start from the foundation: "Why Are GPUs Used for AI?" / "What Is a CPU?"