HPC - Lecture 10 - Matrix multiplication in a distributed-memory environment (REVISE)

HPC - Lecture 10 - Matrix multiplication in a distributed-memory environment

Problem Definition

In a distributed-memory MIMD system, matrix multiplication depends on:

• Data distribution
• System topology
• Communication scheme

Key constraint: No process owns the entire matrices.

Data Distribution Examples

• 1D Distributions: Block distribution by columns, cyclic distribution by columns, or cyclic distribution by column blocks ().
• 2D Distributions: Block distribution, cyclic distribution of elements, or block cyclic distribution ().

1D Distribution (Ring Algorithm)

Assuming nodes logically arranged in a ring.

• , , are blocks of columns assigned to process .
• computes , which expands to .
• has its own and but needs all columns of .

Algorithm Logic (Ring)

At each step, process :

1. Receives a block of columns of from .
2. Sends its current block of to .
3. Computes a partial product.

In steps, all columns reach all nodes.

Efficiency Analysis (1D)

For square matrices :

• Execution time for each step:
• Total time:
• Efficiency: Efficiency tends to 1 as decreases.

2D Distribution (Cannon’s Algorithm)

Processes are arranged in a periodic 2D grid (torus) of processes. Block is assigned to process .

Initial Alignment

To ensure starts with compatible blocks:

1. Shift blocks of in row leftwards by positions.
2. Shift blocks of in column upwards by positions.

Main Loop

For to :

2. Shift leftwards by 1 position.
3. Shift upwards by 1 position.

Efficiency Analysis (Cannon)

• Total time:
• Efficiency: Cannon’s algorithm is more efficient than the 1D ring because . However, it is hard to generalize for non-square process grids or matrices.

SUMMA Algorithm (Scalable Universal Matrix Multiply)

SUMMA is slightly less efficient than Cannon’s but much easier to generalize for:

• Arbitrary (not perfect squares).
• Rectangular matrices.
• 2D block-cyclic distributions.

Matrix Distribution

Assuming a grid of :

• Matrix is divided into blocks.
• Matrix is divided into blocks.
• .
• Distributed in a 2D block-cyclic fashion.

Algorithm Logic (SUMMA)

For to :

1. broadcasts along its row.
2. broadcasts along its column.
3. computes .

Efficiency Analysis (SUMMA)

Assume square matrices and grid :

• Efficiency: The factor comes from the broadcast cost. Since grows slowly, efficiency remains close to Cannon’s.

Summary Table

Algorithm	Efficiency	Generalization	Used In
Ring (1D)		Easy	Simple cases
Cannon (2D)		Difficult	-
SUMMA (2D)		Easy	PBLAS (PDGEMM)