DESIGN AND ANALYSIS OF

ALGORITHMS
Assignment - 2

Title: Cannon's Algorithm for

Matrix Multiplication

SUBMITTED BY:

ALFIYA FATHIMA(MS235204)
D H R I T I J A G A N M O H A N ( M S 2 3 5 2 17)
CL A SS : 5 B C A ' A'
SUBMITTED TO: MS. MARIA SUMAN A
S U B M I S S I O N D A T E : 3 RD O C T O B E R ,
2025
1. Introduction

Cannon’s Algorithm for Matrix multiplication is a foundation operation in computational

science, being a basic building block for an incredibly wide variety of applications. Its
relevance crosses various fields:
• Scientific computing for solving complex systems of linear equations and large-scale
simulations, e.g., computational fluid dynamics.
• Data science and machine learning for training neural networks, conducting principal
component analysis, and running several statistical models.
• Computer graphics for rendering and modeling 3D objects using transformation
matrices.
With computational problems increasing exponentially, the classical sequential
algorithm with its inherent Θ(n3) time complexity for an n×n matrix has proved to be a
serious performance bottleneck. This has driven development of advanced parallel
and distributed algorithms.

Cannon's algorithm, originally presented in 1969 by Lynn Elliot Cannon, is a classic

contribution to parallel computing.
It was designed as a distributed algorithm particularly for matrix multiplication in two-
dimensional processor meshes, an architecture particularly useful then.
Its data-management-and-communication structure is intended to reduce overhead
and achieve efficient parallel processing.
Historically significant in showing how a seemingly sequential problem could be well
decomposed and solved on a distributed-memory system.

The Core Principle: Fundamentally, Cannon's algorithm works on the divide-and-

conquer approach to tackling the matrix multiplication problem. The steps are:
Breaking down the huge matrices into small blocks.
Dividing the blocks across the processors, which then calculate a local piece of the
end product.
The key step is the structured exchange of data across neighboring processors, a
choreographed "pass-and-color" process, ensuring every processor gets the
necessary data without contention.

2. Algorithmic Technique - Divide-and-Conquer

Cannon's algorithm follows the divide-and-conquer approach. Divide-and-conquer
algorithms work according to the following general plan:

• A problem's instance is divided into several smaller instances of the same problem,
ideally of the same size.

• The smaller instances are solved typically recursively. If they're small enough, they're
solved using a different, usually simpler, algorithm.

1
• If necessary, the solutions obtained for the smaller instances are combined to get a
solution to the original instance.

The divide-and-conquer technique depicts the case of dividing a problem into two
smaller sub-problems, by far the most widely occurring case(at least for divide-and-
conquer algorithms designed to be executed on a single-processor computer).

As an example, let us consider the problem of computing the sum of n numbers

a0,…,+an−1. If n>1, we can divide the problem into two instances of the same problem:
to compute the sum of the first [n/2] numbers and then compute the sum of the
remaining [n/2] numbers. (Of course, if n=1, we simply return a 0 as the answer.) Once
each of these two sums is computed (by applying the same method, i.e., recursively),
we add these two values to get the sum in question:

a0+…+an−1=(a0+...+a[n/2]−1)+(a[n/2]+…+an−1).

2
Is this an efficient way to compute the sum of n numbers? A moment of reflection (why
could it be more efficient than the brute-force summation?), a small example of
summing, say, four numbers by this algorithm, a formal analysis (which follows), and
common sense (we do not compute sums this way, do we?) all lead to a negative
answer to this question.

Thus, not every divide-and-conquer algorithm is necessarily more efficient than even
a brute-force solution. The real power of the divide-and-conquer technique is revealed
when it yields an efficient algorithm. The time spent on executing the divide and
conquer plan can be smaller in asymptotic terms than by the straight forward method.
In fact, the divide-and-conquer approach yields some of the most important and
efficient algorithms in computer science: mergesort, quicksort, binary search,
Strassen's matrix multiplication, and many others. Though not every problem yields
itself to an efficient divide-and-conquer algorithm, here it is worth keeping in mind that
the divide-and-conquer technique is ideally suited for parallel computations, in which
each subproblem can be solved simultaneously by its own processor.

As mentioned above, in the most typical case of divide-and-conquer, a problem's

instance of size n is divided into two instances of size n/2. More generally, an
problem's instance of size n can be divided into b instances of size n/b, with a of them
needing to be solved. (Here, a and b are constants; a≥1 and b>1.). Assuming that size
n is a power of b, to simplify our analysis, we get the following recurrence for the
running time T(n):

T(n)=aT(n/b)+f(n)

where f(n) is a function that accounts for the time spent on dividing the problem into
smaller ones and on combining their solutions. (For the summation example, a= b=2
and f(n)=1.) The above recurrence is called the general divide-and-conquer
recurrence. Obviously, the order of growth of T(n) depends on the values of the
constants a and b and the order of growth of the function f(n).

3
3. Algorithm, Tracing, and Time Complexity Analysis

4
5
6
4. Applications

 In scientific computing, it is used for complex physical simulations, like

computational fluid dynamics.

 It is used to develop other parallel problems, such as graph algorithms and

parallel sorting.

 It is often used in academic and open-source projects using C/C++ with MPI
to teach the principles of distributed-memory programming.

 It is used as a performance benchmark for new parallel programming

abstractions.

 It serves as an excellent test case for validating the efficiency of high-level

frameworks and Domain-Specific Languages (DSLs).

 Its legacy has shifted from being a primary solution to a critical tool for
validating next-generation programming models.

5. Advantages and Disadvantages

Advantages:

 Exceptional Memory Scalability: The memory needed per processor is the

same and does not depend on the number of processors used.

 Minimal Memory Requirement: It requires that all three matrices (A, B, and
C) are stored in memory only once, distributed evenly across all
processors. This memory efficiency is a significant strength.

 Perfect Load Balance: Each processor performs the same amount of

computation and communication, leading to excellent strong scaling under ideal
conditions.

7
Disadvantages:

 Rigid Topology Constraint: It has a strict requirement for a

square p×p processor grid. This is often an impractical constraint on real-world
HPC clusters, where the number of available processors may not be a perfect
square, making it difficult to fully utilize all available resources.

 Inefficiency in Heterogeneous Systems: The algorithm's synchronized, lock-

step nature is poorly suited for environments with varying processor speeds. A
single slower processor can stall the entire computation during the collective
shift operation.

 Small Message Sizes/High Latency Overhead: The circular shift pattern

requires a large number of small messages, leading to high latency overhead
for networks with high startup times. This is a result of its design to be memory-
optimal, a paradigm that is inefficient on modern hardware where latency is the
primary communication bottleneck.

6. Case Study: Modern HPC Solutions and

Algorithmic Evolution

i. What it is?

Modern HPC (High-Performance Computing) Solutions are the contemporary

approaches and technologies in high-performance computing focusing on scalability,
efficiency, and integration with new paradigms such as artificial intelligence (AI),

8
machine learning, cloud computing, GPU acceleration, and sometimes quantum
elements. These solutions provide unprecedented speed for processing enormous
datasets and large-scale simulations, frequently employing cluster systems, custom
hardware (e.g., FPGAs or GPUs), and optimized software stacks. They are applied in
fields like scientific research, big data analytics, fraud detection, engineering
simulations, and AI model training.

Algorithmic Evolution in this context refers to the continuous adjustment and tuning
of computation algorithms to leverage these new architectures. This encompasses a
move from sequential to parallel and distributed environments, including mixed-
precision computing, data-intensive application flows, and bio-inspired techniques
(e.g., evolutionary algorithms) to manage growing complexity and hardware diversity.
Overall, this evolution enables progress in areas like numerical simulations,
optimization problems, and AI-driven discoveries by minimizing communication
overheads, maximizing parallelism, and solving issues such as data bottlenecks and
energy efficiency.

ii. Where is this particular algorithm implemented?

Cannon's algorithm, a distributed parallel method for matrix multiplication originally

designed for 2D processor meshes, remains foundational in modern HPC for efficient
linear algebra operations on large-scale systems. It minimizes communication costs
in parallel environments and serves as a building block or inspiration for contemporary
implementations. Key places where it is implemented or extended include:

 FPGA-based accelerators: OpenCL implementations on hardware like Intel

Stratix 10 FPGAs, enabling high-throughput matrix multiplications in HPC
workloads.
 Advanced numerical and scientific computing libraries: Variants and
adaptations in algorithms for tasks like 3D Discrete Fourier Transforms (DFT)
via block tensor-matrix multiplications, optimizing for distributed memory
systems.
 Cluster and scalable HPC software: As a foundation for algorithms such
as SRUMMA (Scalable Recursive Universal Matrix Multiplication Algorithm),
which provides similar efficiency for dense matrix operations on clusters and
heterogeneous systems.
 Polyalgorithmic frameworks: Integrated into second-generation
polyalgorithms for parallel dense matrix multiplication, supporting various
matrix shapes and memory constraints in HPC environments.
 Generalized and hybrid approaches: Extended in tools
like CA3DMM (Communication-Avoiding 3D Matrix Multiplication) for combined
parallel matrix operations, and in memory-constrained settings for
large n×n matrices on p processors. It is also seen in educational tools, GitHub
repositories for MPI-based parallel computing, and as a benchmark in HPC
research.

9
iii. What are they doing?

A typical implementation of Cannon's algorithm follows a clear, multi-step process:

1. Initial Setup and Distribution: A master process (rank 0) generates the input
matrices A and B. These matrices are partitioned into blocks, which are then
scattered to all the other processes in the processor grid.
2. Initial Alignment (Skewing): The processes perform initial, non-uniform shifts
to align their local blocks according to the algorithm's skewing pattern. For
example, the block A[i,j] shifts i positions left, and B[i,j] shifts j positions up to
align them correctly for the first multiplication.
3. Main Computation Loop: The core of the algorithm runs in a loop
for n1/2 steps (where n1/2 is the side length of the square processor grid).
o Local Multiplication: In each iteration, every process performs a local
matrix multiplication on its current blocks (A[local] and B[local]) and adds
the result to its local sum for the result
matrix C(C[local]=C[local]+A[local]×B[local]).
o Circular Shift: This is immediately followed by a synchronized circular
shift of the A and B blocks to their neighboring processes.
Block A shifts one step left (west), and block B shifts one step up (north).
4. Result Gathering: After the loop completes, each process holds its final block
of the result matrix C. Finally, the master process gathers all these blocks from
the other processes to reconstruct the final, complete matrix C.

iv. Better Solution.

While Cannon's algorithm was a foundational step, subsequent research has yielded
more flexible and performant solutions better suited for modern HPC architectures.

Scalable Universal Matrix Multiplication Algorithm (SUMMA)

The SUMMA algorithm is a direct successor to Cannon's and is considered a more

practical solution. In contrast to Cannon's "roll-roll-compute" model, SUMMA uses
a "broadcast-broadcast-multiply" approach. Its primary advantage is that it
overcomes the need for a square processor grid, allowing it to be used with arbitrary
numbers of processors. This flexibility makes it the algorithm of choice for many
modern libraries, including ScaLAPACK and Elemental.

2.5D Algorithms

A more recent and powerful class of algorithms are the 2.5D algorithms. These
generalize both Cannon's (2D) and 3D algorithms by strategically using extra
memory to replicate data, thereby significantly reducing communication costs.

 Trade-off: While Cannon's algorithm is memory-optimal (using minimal

memory O(n2/p)), the 2.5D approach demonstrates that it is often faster to
trade an increase in memory usage for a substantial reduction
in communication volume and latency.

10
  Performance: Preliminary results on modern supercomputing hardware have
shown a performance gain of up to 3X over Cannon's algorithm by employing
this strategy, as communication is the primary bottleneck in large-scale
systems.

v. Proposed Solution.

A highly effective solution for modern HPC architectures is a hybrid MPI/OpenMP

2.5D matrix multiplication algorithm. This approach leverages the strengths of both
distributed and shared memory parallelism.

 MPI (Message Passing Interface) would be used to handle the inter-node

communication, managing the data distribution and collective operations
(broadcasts, reductions) of the 2.5D algorithm's three-dimensional processor
grid.
 OpenMP (Open Multi-Processing) would be employed for the intra-node
parallelism, exploiting the shared memory of multi-core CPUs or GPUs to
perform the local matrix multiplications on each block as efficiently as possible.

This hybrid model combines the communication-avoiding principles of 2.5D

algorithms with the performance benefits of shared-memory parallelism, creating a
robust, high-performance solution.

vi. Which is better and why is it better?

The proposed hybrid 2.5D solution is superior to Cannon's algorithm for several key
reasons, primarily due to its adaptability and performance on modern hardware where
communication costs are dominant.

 Adaptability: The 2.5D algorithm overcomes Cannon's rigid requirement for

a square processor grid and is better suited for a wider range of matrix and
processor dimensions. Its communication-avoiding design also makes it more
robust to the challenges of heterogeneity (varying processor speeds), which
plague Cannon's synchronized shifts.
 Performance (Communication Bottleneck): The 2.5D approach
fundamentally addresses the communication bottleneck of Cannon's algorithm.
By using extra memory O(c⋅n2/p) to replicate data, it can significantly reduce
both the communication volume O(n2/cp) and the number of
messages(latency term O(p/c3+logc)). As the cost of communication relative
to computation continues to increase, this trade-off becomes increasingly
favorable. Experimental results have shown a speed-up of 2.4X to 3.0X over
Cannon's algorithm.
 Scalability: By substantially reducing communication costs, the 2.5D algorithm
achieves better strong scaling than Cannon's, allowing it to maintain a high
level of efficiency as the number of processors increases for a fixed problem
size.

11
The following table provides a high-level comparison of the key parallel matrix
multiplication algorithms:

Key Communication Communication

Memory
Algorithm Topology Communication Volume Messages
Requirement
Pattern (Words) (Latency)

Cannon's Square
Circular Shifts O(n2/p) O(n2/p) O(p)
(2D) Grid

Flexible
SUMMA Broadcasts O(n2/p) O(n2/p) O(logp)
2D Grid

Broadcasts +
2.5D 3D Grid O(c⋅n2/p) O(n2/cp) O(p/c3+logc)
Reductions

In conclusion, while Cannon's algorithm remains a historically and pedagogically

significant solution for parallel matrix multiplication due to its memory efficiency and
elegant design, its rigid topological constraints and high communication latency make
it less suitable for modern HPC platforms. Newer algorithms like SUMMA and the
family of 2.5D algorithms offer superior performance and flexibility by
strategically trading memory for a substantial reduction in communication costs. The
proposed hybrid 2.5D solution represents a robust, practical, and highly performant
approach for tackling this foundational problem on contemporary supercomputers.

*****

12