September 2023 – Nick Higham

A flop is one of the elementary arithmetic operations $+$ , $-$ , $*$ , $/$ carried out on floating-point numbers. For example, evaluating the expression $(b - ax)/c$ takes three flops. A square root, which occurs infrequently in numerical computation, is also counted as one flop.

As an example, the computation of the inner product $x^Ty$ of two $n$ -vectors $x$ and $y$ can be written

s = x(1)*y(1)
for i = 2:n
    s = s + x(i)*y(i)
end

which requires $n$ multiplications and $n-1$ additions, or $2n-1$ flops. A matrix multiplication $AB$ of two $n\times n$ matrices involves computing the inner products of every row of $A$ with every column of $B$ , that is $n^2$ inner products, costing $2n^3 - n^2$ flops. As we are usually interested in flop counts for large dimensions we retain only the highest order terms, so we regard $AB$ as costing $2n^3$ flops.

The number of flops required by a numerical computation is one measure of its cost. However, it ignores the cost of data movement, which can be as large as, or even larger, than the cost of floating-point arithmetic for large computations implemented on modern machines with hierarchical memories. Nevertheless, flop counts provide a useful way to compare the cost of competing algorithms when most of the flops occur in similar types of operations, such as matrix multiplications, and they can be used to choose between algorithm variants (López et al., 2022).

This table summarizes some flop counts, where $\alpha$ is a scalar, $x,y$ are $n$ -vectors, and $A,B$ are $n\times n$ matrices, and $A^{-1}$ is computed via LU factorization.

Computation	Cost
$x + \alpha y$	$2n$ flops
$x^Ty$	$2n$ flops
$Ax$	$2n^2$ flops
$AB$	$2n^3$ flops
$A^{-1}$	$2n^3$ flops

As the table suggests, most standard problems involving $n\times n$ matrices can be solved with a cost of order $n^3$ flops or less, so the interest is in the exponent ( $1$ , $2$ , or $3$ ) of the dominant term and the multiplicative constant. For $m\times n$ matrices there can be several potentially dominant terms $m^kn^\ell$ and comparing competing algorithms is more complicated.

Early Usage

Moler and Van Loan give a different definition of “flop” in their classic paper “Nineteen Dubious Ways to Compute the Exponential of a Matrix” (1978), and their definition was adopted in the flop command in the original Fortran version of MATLAB, which counts the number of flops executed in the most recent command or since MATLAB started. In the 1981 MATLAB Users’ Guide, Cleve Moler explains that

One flop is one execution of a Fortran statement like S = S + X(I)*Y(I) or Y(I) = Y(I) + T*X(I). In other words, it consists of one floating point multiplication, together with one floating point addition and the associated indexing and storage reference operations.

This original definition attempted to account for indexing and storage costs in the computer implementation of an algorithm as well as the cost of the floating-point arithmetic. It was motivated by the fact that in linear algebra computations most arithmetic appears in statements of the form s = s + x*y, which appear in evaluating inner products and in adding one multiple of a vector to another.

In the LINPACK Users’ Guide (1979, App. B) flops were used to normalize timing data, but the word “flop” was not used.

The widespread adoption of the flop was ensured by its use in Golub and Van Loan’s book Matrix Computations (1981). In the 1989 second edition of the book a flop was redefined as in our first paragraph and this definition quickly became the standard usage. The Fortran statements given by Moler now involve two flops.

The MATLAB flop function survived until around 2000, when MATLAB started using LAPACK in place of LINPACK for its core linear algebra computations and it became no longer feasible to keep track of the number of flops executed.

It is interesting to note that an operation of the form S + X(I)*Y(I) that was used in the original definition of flop is now supported in the hardware of certain processors. The operation is called a fused multiply-add and is done in the same time as one multiplication or addition and with one rounding error.

Flops as a Measure of Computer Performance

Another usage of “flop”, in the plural, is in measuring computer performance, with “flops” meaning floating-point operations per second and having a prefix specifying a power of ten. Thus we have the terms megaflops, gigaflops, through to exaflops ( $10^{18}$ floating-point operations per second) for today’s fastest computers.

The earliest citation given in the Oxford English Dictionary for this use of the word “flops” is in a 1977 paper by Calahan, who writes

The most common vector performance measure is the number of floating point operations per second (FLOPS), obtained by dividing the number of floating point operations—known from the algorithmic complexity—by the computation time.

The term “MFLOPS” for “million floating point operations per second” is used in an earlier Cray-1 evaluation report (Keller, 1976).

If you are aware of any earlier references please put them in the comments below.

Dictionary Definitions

The word “flop” appears in general dictionaries, but there is some variation in whether it appears under “flop” or “flops”, in capitalization, and whether it means an operation or an execution rate.

Dictionary	Term	Definition
Oxford English Dictionary (online, 2023)	FLOP	“A floating-point operation per second”
Concise Oxford English Dictionary (11th ed., 2004)	flop	“Floating-point operations per second”
The Chambers Dictionary (13th ed., 2014)	flop	“A floating-point operation”
Collins English Dictionary (13th ed., 2018)	flops or FLOPS	“Floating-point operations per second”
The American Heritage Dictionary of the English Language (5th ed., 2018)	flops or flop	“A measure of the speed of a computer in operations per second, especially operations involving floating-point numbers”
Merriam-Webster (online, 2023)	flops	“A unit of measure for calculating the speed of a computer equal to one floating-point operation per second”

Notes and References

I thank Jack Dongarra, Cleve Moler, and Charlie Van Loan for comments on the history of flops.

D. A. Calahan, Algorithmic and Architectural Issues Related to Vector Processors, in: Large Engineering Systems. Proceedings of the International Symposium held at the University of Manitoba, Winnipeg, Manitoba, Canada August 9–12, 1976, Alvin Wexler, ed., Pergamon Press, Oxford, 1977.
T. Keller, CRAY-1 Evaluation. Final Report, Report LA-6456-MS, Los Alamos Scientific Laboratory, Los Alamos, New Mexico, USA, December 1976.
Francisco López, Lars Karlsson, and Paolo Bientinesi, FLOPs as a Discriminant for Dense Linear Algebra Algorithms, in Proceedings of the 51st International Conference on Parallel Processing, ACM Press, 2022.
Cleve B. Moler and Charles F. Van Loan, Nineteen Dubious Ways to Compute the Exponential of a Matrix, SIAM Rev. 20(4), 801–836. 1978.

Month: September 2023

What Is a Flop?

Early Usage

Flops as a Measure of Computer Performance

Dictionary Definitions

Notes and References

Related Blog Posts

Early Usage

Flops as a Measure of Computer Performance

Dictionary Definitions

Notes and References

Related Blog Posts

Share this: