Details of theoretical computational costs

January 31, 2019 · View on GitHub

This document explains how chainer-computational-cost estimates theoretical computational cost of each type of layer. Unless otherwise specified, $\normal x$ stands for the input to the layer and $\normal y$ is output. $\normal \| x \|$ is the number of elements in $\normal x$ (equivalent to x.size), if $\normal x$ is empty or does not exist, $\normal \| x \| = 0$ .

The basic strategy of how the "theoretical computational cost" is defined is written in README.md.

Activation
- PReLUFunction
- ReLU
- LeakyReLU
- Sigmoid
- Softmax
Array
- BroadcastTo
- Concat
- Reshape
- ResizeImages
- Transpose
- GetItem
Connection
Math
- Add
- AddConstant
- Div
- DivFromConstant
- Mul
- MulConstant
- Sub
- SubFromConstant
- Max
- Min
- ArgMax
- ArgMin
- Sum
Normalization
Pooling

Activation

PReLUFunction

Max operation can be executed by a single instruction. chainer-computational-cost considers it as one floating point operation.

In case $\normal W$ is neither scalar nor same shape as $\normal x$ , it is broadcasted internally, but cost for broadcasting operation is ignored.

Item	Value
FLOPs	$\normal \\| x \\|$
mread	$\normal \\| x \\| + \\|W\\|$ , where $\normal W$ is learned parameter
mwrite	$\normal \\| x \\|$
params	`w_shape`: shape of $\normal W$

ReLU

Max operation can be executed by a single instruction. chainer-computational-cost considers it as one floating point operation.

Item	Value
FLOPs	$\normal \\| x \\|$
mread	$\normal \\| x \\|$
mwrite	$\normal \\| x \\|$
params	N/A

LeakyReLU

Leaky ReLU applies an elementwise multiplication with slope gradient followed by a max operation. Strictly speaking, the number of multiplication to be conducted is depend on the input data, but for simplicity, chainer-computational-cost treats Leaky ReLU as $\normal y=\max(x, ax)$ .

Item	Value
FLOPs	$\normal 2 \\| x \\|$
mread	$\normal \\| x \\|$
mwrite	$\normal \\| x \\|$
params	N/A

Sigmoid

Sigmoid is an elementwise operation that consists of four floating point operations, which are minus, exp, +1 and inv, for each element.

Item	Value
FLOPs	$\normal 4 \\| x \\|$
mread	$\normal \\| x \\|$
mwrite	$\normal \\| x \\|$
params	N/A

Softmax

Here, let $\normal c$ be the depth of the input $\normal x$ over the specified axis (c = x.shape[axis]) and $\normal s$ be the product of spatial size (size of $\normal x$ without axis axis).

In Softmax, at first exp is calculated for each element, that is $\normal \| x \|$ FLOPs. Then they are summed over the axis axis, which requires $\normal c-1$ FLOPs for each spatial position ( $\normal s * (c-1)$ FLOPs). Finally each elements are devided by the sum ( $\normal \| x \|$ FLOPs).

Item	Value
FLOPs	$\normal 2 \\| x \\| + s(c-1)$
mread	$\normal \\| x \\|$
mwrite	$\normal \\| x \\|$
params	`axis`: axis of the softmax operation

Array

BroadcastTo

As index calculation is ignored in chainer-computational-cost, broadcasting is theoretically 0 FLOPs.

Item	Value
FLOPs	$\normal 0$
mread	$\normal \\| x \\|$
mwrite	$\normal \\| y \\|$
params	`shape`: output shape

Concat

Concatenation is just a memory copy, hense no floating point operation will be conducted. Depending on concatenation axis, index calculation might be needed but chainer-computational-cost ignores such operations.

Item	Value
FLOPs	$\normal 0$
mread	$\normal \sum_{i} \\|x_{i}\\|$
mwrite	$\normal \sum_{i} \\|x_{i}\\|$
params	`axis`: concatenation axis

Reshape

Reshape operation basically neither changes nor reads the data. It just makes an array with same data reference with different metadata.

If your environment cannot do in-place reshape, consider overwriting by a custom cost calculator (refer README.md).

Item	Value
FLOPs	$\normal 0$
mread	$\normal 0$
mwrite	$\normal 0$
params	`in_shape`: input shape, `out_shape`: output shape

ResizeImages

In bilinear resize operation, each output pixel value is calculated by 4 neighboring source pixels in the input image.

In order to know where the source pixel is, a few index calculations including floating point arithmetic is needed, but these are ignored since chainer-computational-cost ignores such index calculations.

To calculate an output value from 4 source pixels, first 3 FLOPs is spent for horizontal interpolation from 2 source pixels, then another 3 FLOPs for vertical, and finally 3 FLOPs for inter-axis interpolation, therefore in total 9 FLOPs for each output pixel.

As for memory access, especially in case of expanding the source image, duplicated memory read will happen. For example, if the input image is 8x8 and the output size is 32x32, naively reading memory runs 4096 times, even though the actual size of the input is only 64. In order to avoid such a contradiction, chainer-computational-cost introduces a policy to treat such case as if it loads the entire input data only once.

Conversely, in case not all the image is needed (for example input is 32x32 and the output is 8x8, where memory read is only 128), chainer-computational-cost simply counts 4 memory reads for each output pixel.

Either smaller number is used for memory read estimation. In other words, memory read is formulated as $\normal \max(4 \| y\|, \|x\|)$ .

Considering extreme cases like shrinking horizontally and expanding vertically, this logic should be much complicated, but for simplicity chainer-computational-cost only uses the above formula.

Item	Value
FLOPs	$\normal 9 \\| y \\|$
mread	$\normal \min(4 \\| y\\|, \\|x\\|)$
mwrite	$\normal \\| y \\|$
params	`size`: output size

Transpose

Transpose operation is just copying memory with no FLOPs.

Item	Value
FLOPs	$\normal 0$
mread	$\normal \\| x \\|$
mwrite	$\normal \\| x \\|$
params	`axes`: transpose axes

GetItem

Extract part of an array. This operation is zero FLOPs. Most of tensor libraries have view feature, which doesn't actually create a new array unless necessary, but this is not considered in chainer-computational-cost. Memory read runs only for the necessary elements, so both memory read and write are same as the size of output tensor.

Item	Value
FLOPs	$\normal 0$
mread	$\normal \\| y \\|$
mwrite	$\normal \\| y \\|$
params	`slices`: list of slices, a slice is an int or a tuple with 3 elements

Connection

Convolution2DFunction

Convolution operator essentially calculates an output value by convolving the input feature map by a corresponding filter whose size is $\normal k_{h} k_{w} {c_{\mathrm{in}}}$ . The computational cost is $\normal 2 k_{h} k_{w} {c_{\mathrm{in}}} - 1$ FLOPs for each output pixel. Including bias, it becomes simply $\normal 2 k_{h} k_{w} {c_{\mathrm{in}}}$ . So in total $\normal 2 k_{h} k_{w} {c_{\mathrm{in}}} h_{\mathrm{out}} w_{\mathrm{out}} c_{\mathrm{out}}$ . Here, output size $\normal h_{\mathrm{out}}$ and $\normal w_{\mathrm{out}}$ can be calculated by chainer.utils.get_conv_outsize.

If there is no bias, it will be $\normal (2 k_{h} k_{w} {c_{\mathrm{in}}}-1) h_{\mathrm{out}} w_{\mathrm{out}} c_{\mathrm{out}}$ FLOPs.

In case of grouped convolution, it can be considered as just concatenating result of convolution whose input has $\normal c_{\mathrm{in}}/G$ channels and output is $\normal c_{\mathrm{out}}/G$ channels. Each group costs $\normal 2 k_{h} k_{w} c_{\mathrm{in}} h_{\mathrm{out}} w_{\mathrm{out}} c_{\mathrm{out}}/G^2$ FLOPs/group, so in total $\normal 2 k_{h} k_{w} c_{\mathrm{in}} h_{\mathrm{out}} w_{\mathrm{out}} c_{\mathrm{out}} / G$ FLOPs.

If fma_1flop is set to True, it will be $\normal k_{h} k_{w} c_{\mathrm{in}} h_{\mathrm{out}} w_{\mathrm{out}} c_{\mathrm{out}} / G$ FLOPs. Exsistence of bias does not matter this case.

Dilated convolution does not change theoretical computational cost explained above, although it usually significantly affects to the actual performance.

Although a source pixel can be read multiple times in the most native convolution implementation, chainer-computational-cost counts them only once, therefore the memory read is counted as if the entire input data and parameters (weights, biases) are loaded from memory only at once. Padding is ignored, too.

FMA option can be switched by fma_1flop: bool keyword argument specified to ComputationalCostHook.

Item	Value
FLOPs(FMA)	$\normal c_{\mathrm{in}} c_{\mathrm{out}} k_{h} k_{w} h_{\mathrm{out}} w_{\mathrm{out}} / G$
FLOPs(no-FMA)	$\normal 2 c_{\mathrm{in}} c_{\mathrm{out}} k_{h} k_{w} h_{\mathrm{out}} w_{\mathrm{out}} / G$
FLOPs(no-FMA nobias)	$\normal G(2 (c_{\mathrm{in}}/G) (c_{\mathrm{out}}/G)-1) k_{h} k_{w} h_{\mathrm{out}} w_{\mathrm{out}}$
mread	$\normal \\| x \\| + \\| W \\| + \\| b \\|$
mwrite	$\normal c_{\mathrm{out}} h_{\mathrm{out}} w_{\mathrm{out}}$
params	conv parameters `k`, `s`, `p`, `d`, `groups`, `nobias`

Deconvolution2DFunction

Deconvolution, also as known as transposed convolution, can be thought as going backward to the convolution operation. Each input pixel is multiplied to convolution filter kernel ( $\normal (c_{\mathrm{out}}, k_h, k_w)$ ). Its result is summed up on the output tensor, among adjacent result and result of other filters (there are $\normal c_{\mathrm{in}}$ filters), then bias is added if exists.

In order to understand the behavior of this operation and why it is called "transposed" convolution, these materials are helpful.

The theoretical computational cost is $\normal 2 c_{\mathrm{out}} k_h k_w h_{\mathrm{in}} w_{\mathrm{in}} c_{\mathrm{in}}$ FLOPs.

In case of groups is not 1, similarly to convolution, it becomes $\normal 2 c_{\mathrm{out}} k_h k_w h_{\mathrm{in}} w_{\mathrm{in}} c_{\mathrm{in}} / G$ FLOPs.

Item	Value
FLOPs(FMA)	$\normal 2 c_{\mathrm{in}} c_{\mathrm{out}} k_h k_w h_{\mathrm{in}} w_{\mathrm{in}} / G$
FLOPs(no-FMA)	$\normal c_{\mathrm{in}} c_{\mathrm{out}} k_h k_w h_{\mathrm{in}} w_{\mathrm{in}} / G$
mread	$\normal \\| x \\| + \\| W \\| + \\| b \\|$
mwrite	$\normal c_{\mathrm{out}} h_{\mathrm{out}} w_{\mathrm{out}}$
params	conv parameters `k`, `s`, `p`, `d`, `groups`, `nobias`

LinearFunction

Let $\normal n_{\mathrm{in}}$ be the input size and $\normal n_{\mathrm{out}}$ be the output size. Each output value is calculated by $\normal n_{\mathrm{in}}$ product and $\normal n_{\mathrm{in}} - 1$ sum operations. So, in case fma_1flop==False, $\normal 2 n_{\mathrm{in}} - 1$ FLOPs/element, or $\normal 2 * n_{\mathrm{in}}$ if there is bias. In FMA mode $\normal n_{\mathrm{in}}$ FLOPs (regardress of existence of bias).

FMA option can be switched by fma_1flop: bool keyword argument specified to ComputationalCostHook.

Item	Value
FLOPs(FMA)	$\normal \\| n_{\mathrm{in}} n_{\mathrm{out}} \\|$
FLOPs(no-FMA)	$\normal \\| 2 n_{\mathrm{in}} n_{\mathrm{out}} \\|$
FLOPs(no-FMA no-bias)	$\normal \\| (2 n_{\mathrm{in}} - 1) n_{\mathrm{out}} \\|$
mread	$\normal \\|x\\| + \\|W\\| + \\|b\\|$ , where $\normal W$ and $\normal b$ are learned parameter
mwrite	$\normal \\|y\\|$
params	`nobias`

Shift

Shift only conducts memory read, index calculation and memory write. There might be unnecessary memory read around corners, but for simplicity chainer-computational-cost treats it as just reading the entire data.

Item	Value
FLOPs	$\normal 0$
mread	$\normal \\| x \\|$
mwrite	$\normal \\| x \\|$
params	shift parameters `k` and `d`

Math

Add

Elementwise Add operation. In case shape of inputs are different, broadcast will run and then elementwise arithmetic is conducted. Cost for broadcasting is ignored. For simplicity, it assumes all the arrays are first broadcasted to the output size then elementwise sum is calculated. The output size is the largest size of the input.

Item	Value
FLOPs	$\normal (N-1) \max_{i}^{N} \\| x_{i} \\|$
mread	$\normal \sum_{i}^{N} \\| x_{i} \\|$
mwrite	$\normal \max_{i}^{N} \\| x_{i} \\|$
params	N/A

AddConstant

AddConstant is elementwise Add operation where the operand is a constant (not a chainer.Variable but a numpy.array or a cupy.array).

In case shape of inputs are different, broadcast will run and then elementwise arithmetic is conducted. Cost for broadcasting is ignored. The output size is same as the larger one of either the input ( $\normal x$ ) or the operand (<img src="https://latex.codecogs.com/png.latex?%5Cdpi%7B100%7D%20%5Cnormal%20c"/>).

Item	Value
FLOPs	$\normal \max(\\| x \\|, \\| c \\|) \\|$
mread	$\normal \\| x \\| + \\| c \\|$
mwrite	$\normal \max(\\| x \\|, \\| c \\|) \\|$
params	N/A

Div

See the documentation for Add

DivFromConstant

See the documentation for AddConstant

Mul

See the documentation for Add

MulConstant

See the documentation for AddConstant

Sub

See the documentation for Add

SubFromConstant

See the documentation for AddConstant

Max

In case axis is None, it just calculates maximum value of a tensor, which costs simply $\normal \|x\|-1$ .

Here, let's consider a 4-dimensional array whose shape is $\normal (A, B, C, D)$ . When axis is set to (1, 2),

First it calculates max over the axis 1, which is $\normal (B-1)ACD$ FLOPs, and this makes a tensor shaped $\normal (A, C, D)$
Next, max over the original axis 2 is conducted in $\normal (C-1)AD$ FLOPs, and a tensor $\normal (A, D)$ is remained. Total FLOPs is just a sum of above, and the output is $\normal (A, D)$ .

Therefore, FLOPs is calculated by the following algorithm.

input: x, axes
output: f (FLOPs), s (output size)
s <- x.size
f <- 0
foreach i in axes
    d <- x.shape
    s <- s / d
    f <- f + (d-1)s

Item	Value
FLOPs	See the above explanation
mread	$\normal \\| x \\|$
mwrite	See the above explanation
params	`axis`

Min

See the documentation for Max.

ArgMax

Theoretical cost of Argmax is exactly same as Min/Max, except that Argmax can receive only one axis. See the documentation for Max.

ArgMin

Theoretical cost of Argmin is exactly same as Min/Max, except that Argmax can receive only one axis. See the documentation for Max.

Sum

Sum of an array among the specified axis(axes) also costs equivalently to max operation, since it just replaces $\normal \max(a, b)$ by $\normal a+b$ . See the documentation for Max.

Normalization

FixedBatchNormalization

Test-mode batch normalization. It consists of normalization part (using $\normal \mu$ and $\normal \sigma$ ) and bias part ( $\normal \gamma$ and $\normal \beta$ ), both are composed of elementwise scale and shift. However this can actually be fused into single scale and shift operation. Therefore, regardless of existence of bias ( $\normal \gamma$ and $\normal \beta$ ), computational cost is always $\normal 2 \|x\|$ FLOPs.

Since scale-and-shift operation can be done by FMA, it becomes $\normal \|x\|$ FLOPs if fma_1flop is set to True.

Due to the same reason as explained above, reading learned scale and shift parameter is required only once (not twice) regardless of bias existence. Both are 1-dimensional array with $\normal c_{\mathrm{in}}$ elements.

Item	Value
FLOPs(FMA)	$\normal \\| x \\|$
FLOPs(no-FMA)	$\normal 2 \\| x \\|$
mread	$\normal \\|x\\| + 2 c_{\mathrm{in}}$
mwrite	$\normal \\| x \\|$
params	`eps`: epsilon for BN

NormalizeL2

Let us assume that axis is channel axis, then each spatial position has a $\normal c$ -dimensional vector. Cacululation L2-norm of this vector is, with no FMA mode, first it applies elementwise square in $\normal c$ FLOPs and summation in $\normal c-1$ FLOPs finally sqrt in $\normal 1$ FLOP, so in total $\normal 2c$ FLOPs. With FMA mode, $\normal c$ FLOPs for square and sum, then $\normal 1$ FLOP for summing up, in total $\normal c+1$ FLOPs.

Then $\normal \eps$ is added to the L2-norm and elementwise division is applied in total $\normal c+1$ FLOPs.

Hense, total cost for L2-normalizing an array is $\normal (2c+c+1)wh$ FLOPs with no FMA mode, or $\normal (c+1+c+1)wh$ FLOPs.

Chainer's NormalizeL2 implementation supports axis to be up to 2 elements, but it's undocumented, so chainer-computational-cost only assumes that axis is only one dimension.

In the below table, 3-dimensional array with shape $\normal (c,h,w)$ is assumed and the axis is channel dimension, but any other shape/axis is the same.

Item	Value
FLOPs(FMA)	$\normal \\| (2c+2)wh \\|$ when shape of $\normal x$ is $\normal (c,h,w)$ and `axis` is 0
FLOPs(no-FMA)	$\normal \\| (3c+1)wh \\|$ when shape of $\normal x$ is $\normal (c,h,w)$ and `axis` is 0
mread	$\normal \\| x \\|$
mwrite	$\normal \\| x \\|$
params	`axis`

LocalResponseNormalization

Let $\normal c$ , $\normal h$ and $\normal w$ be the shape of $\normal x$ , so $\normal \|x\| = chw$ First all the values are squared ( $\normal chw$ FLOPs). Then it is integrated among the channel axis ( $\normal (c - 1)hw$ FLOPs). Sum of a local response for a value can be calculated by a subtraction (in total $\normal chw$ FLOPs). Then elementwise multiplication of $\normal \alpha$ , addition of $\normal k$ and power by $\normal \beta$ are conducted ( $\normal 3chw$ FLOPs, or $\normal 2chw$ if fma_1flop is set to True, as $\normal \alpha$ and $\normal k$ can be done by FMA).

In total, FLOPs will be sum of them, $\normal chw + (c-1)hw + chw + 3chw == (6c-1)hw$ FLOPs with no-FMA and $\normal (5c-1)hw$ with FMA.

Item	Value
FLOPs(FMA)	$\normal (5c-1)hw$
FLOPs(no-FMA)	$\normal (6c-1)hw$
mread	$\normal chw == \\| x \\|$
mwrite	$\normal chw == \\| x \\|$
params	`n`, `k`, `alpha` and `beta`

Pooling

AveragePooling2D

Each output pixel is calculated by averaging $\normal k * k$ elements from the input ( $\normal k*k$ FLOPs). Output size is calculated by chainer.utils.get_conv_outsize.

Item	Value
FLOPs	$\normal \\| y \\| k_{\mathrm{w}} k_{\mathrm{h}}$
mread	$\normal \\| x \\|$
mwrite	$\normal \\| y \\|$
params	AvgPooling parameter `k`, `s` and `p`

MaxPooling2D

Each output pixel is calculated by taking max of $\normal k * k$ elements from the input ( $\normal k*k - 1$ FLOPs). Output size is calculated by chainer.utils.get_conv_outsize.

Item	Value
FLOPs	$\normal \\| y \\| (k_{\mathrm{w}} k_{\mathrm{h}} - 1)$
mread	$\normal \\| x \\|$
mwrite	$\normal \\| y \\|$
params	AvgPooling parameter `k`, `s` and `p`

Upsampling2D

Upsampling2D only reads the data from memory and writs to the certain position in the output using indices. Other pixels are filled by 0. Indices array has always the same shape as the input. Although its data type is not float but int, since their data size is usually the same (float32 and int32), chainer-computational-cost ignores this difference and considers indices to be same as input.

Item	Value
FLOPs	$\normal 0$
mread	$\normal 2 \\| x \\|$
mwrite	$\normal \\| y \\|$
params	Upsampling parameter `k`, `s`, `p`, `outsize` and `cover_all`

Unpooling2D

Unpooling2D only reads the data from memory and writes to the certain position in the output. Unlike the upsampling2D, it does not use indices and all pixels are filled by corresponding pixels in the input tensor.

Item	Value
FLOPs	$\normal 0$
mread	$\normal \\| x \\|$
mwrite	$\normal \\| y \\|$
params	Unpooling parameter `k`, `s`, `p`, `outsize` and `cover_all`