Concept

Communication lower bound — where it appears

A statement that no algorithm computing a given result can move fewer than a stated number of words, whatever its arrangement.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

A block size is a property of the machine

Three lines of counting say the best block size is √(M/3). Scanned over every integer at five fast memories, the measured optimum is √M − 2 — exactly, at all five. The count has the right scaling and the wrong constant, low by a factor of 1.56, and the wrong form: the answer is affine in √M rather than proportional to it.

cost · blocking

The message and the word

Three factorisations of one matrix on sixteen processors: 48 communication rounds, 4, and 4. The words sent are 1,170, 1,170 and 2,160 — so the method with the fewest rounds sends the most words, and the count that separates the three is the one no operation count can see.

cost · communication

Named alongside it

The objects these essays reach for when they reach for this one.

Data movement Blocked algorithm Cache Condition number Fitted exponent Flop count Householder reflection Latency Loop order Memory hierarchy Normal equations Orthogonality

All concepts