OOC matrix matrix computation #348
Description
Understanding Matrix Multiplication Data Structures and Calculations
Matrix Representation and Indexing
Let's visualize matrix blocks with an example of 3×3 blocks for each matrix:
Matrix A (4×3 blocks) Matrix B (3×5 blocks) Result Matrix C (4×5 blocks)
┌───┬───┬───┐ ┌───┬───┬───┬───┬───┐ ┌───┬───┬───┬───┬───┐
│A₁₁│A₁₂│A₁₃│ │B₁₁│B₁₂│B₁₃│B₁₄│B₁₅│ │C₁₁│C₁₂│C₁₃│C₁₄│C₁₅│
├───┼───┼───┤ ├───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┤
│A₂₁│A₂₂│A₂₃│ │B₂₁│B₂₂│B₂₃│B₂₄│B₂₅│ │C₂₁│C₂₂│C₂₃│C₂₄│C₂₅│
├───┼───┼───┤ ├───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┤
│A₃₁│A₃₂│A₃₃│ │B₃₁│B₃₂│B₃₃│B₃₄│B₃₅│ │C₃₁│C₃₂│C₃₃│C₃₄│C₃₅│
├───┼───┼───┤ ├───┼───┼───┼───┼───┤
│A₄₁│A₄₂│A₄₃│ │C₄₁│C₄₂│C₄₃│C₄₄│C₄₅│
└───┴───┴───┘ └───┴───┴───┴───┴───┘
Phase 1: The Shuffle Phase
Data Structure: groupedBlocks Map
┌─────────────────────────────────────────────────────────────────────┐
│ Map<MatrixIndexes, List<TaggedMatrixValue>> groupedBlocks │
├─────────────┬───────────────────────────────────────────────────────┤
│ Key (i,j) │ Value: List of TaggedMatrixValue │
├─────────────┼───────────────────────────────────────────────────────┤
│ (1,1) │ [A₁₁*, A₁₂*, A₁₃*, B₁₁*, B₂₁*, B₃₁*] │
├─────────────┼───────────────────────────────────────────────────────┤
│ (1,2) │ [A₁₁*, A₁₂*, A₁₃*, B₁₂*, B₂₂*, B₃₂*] │
├─────────────┼───────────────────────────────────────────────────────┤
│ ... │ ... │
├─────────────┼───────────────────────────────────────────────────────┤
│ (4,5) │ [A₄₁*, A₄₂*, A₄₃*, B₁₅*, B₂₅*, B₃₅*] │
└─────────────┴───────────────────────────────────────────────────────┘
* Each block is a tagged copy (deep copy with source and k-index information)
TaggedMatrixValue Structure
┌─────────────────────────────────────────────────────────────────┐
│ TaggedMatrixValue │
├───────────────┬─────────────────────────────────────────────────┤
│ Field │ Description │
├───────────────┼─────────────────────────────────────────────────┤
│ value │ Deep copy of original IndexedMatrixValue │
├───────────────┼─────────────────────────────────────────────────┤
│ isFromInput1 │ true = from Matrix A, false = from Matrix B │
├───────────────┼─────────────────────────────────────────────────┤
│ kIndex │ The k dimension index for matching (column │
│ │ index for A blocks, row index for B blocks) │
└───────────────┴─────────────────────────────────────────────────┘
Visual Representation of Block Copying and Distribution
For Matrix A blocks (example for block A₂₃):
┌─────────────────┐
┌───▶│ groupedBlocks │
│ │ Key: (2,1) │
│ └─────────────────┘
│ ┌─────────────────┐
┌─────────────┐ Deep copy & │ │ groupedBlocks │
│ Block A₂₃ │ distribute ┌┼───▶│ Key: (2,2) │
│ i=2, k=3 ├────────────────┘│ └─────────────────┘
└─────────────┘ │ ┌─────────────────┐
│ │ groupedBlocks │
└───▶│ Key: (2,3) │
│ └─────────────────┘
│ ...
│ ┌─────────────────┐
└───▶│ groupedBlocks │
│ Key: (2,5) │
└─────────────────┘
Tag: {isFromInput1: true, kIndex: 3}
For Matrix B blocks (example for block B₃₂):
┌─────────────────┐
┌───▶│ groupedBlocks │
│ │ Key: (1,2) │
│ └─────────────────┘
│ ┌─────────────────┐
┌─────────────┐ Deep copy & │ │ groupedBlocks │
│ Block B₃₂ │ distribute ┌┼───▶│ Key: (2,2) │
│ k=3, j=2 ├────────────────┘│ └─────────────────┘
└─────────────┘ │ ┌─────────────────┐
│ │ groupedBlocks │
└───▶│ Key: (3,2) │
│ └─────────────────┘
│ ┌─────────────────┐
└───▶│ groupedBlocks │
│ Key: (4,2) │
└─────────────────┘
Tag: {isFromInput1: false, kIndex: 3}
Phase 2: The Reduce Phase
Data Organization for Processing C₂₃ Block
┌───────────────────────────────────────────────────────────────────────┐
│ Blocks in groupedBlocks[(2,3)] │
├───────────────────────┬─────────────────────┬───────────────┬─────────┤
│ Original Block │ Tagged As │ From Matrix │ k-Index │
├───────────────────────┼─────────────────────┼───────────────┼─────────┤
│ A₂₁ │ TaggedMatrixValue │ A (true) │ 1 │
├───────────────────────┼─────────────────────┼───────────────┼─────────┤
│ A₂₂ │ TaggedMatrixValue │ A (true) │ 2 │
├───────────────────────┼─────────────────────┼───────────────┼─────────┤
│ A₂₃ │ TaggedMatrixValue │ A (true) │ 3 │
├───────────────────────┼─────────────────────┼───────────────┼─────────┤
│ B₁₃ │ TaggedMatrixValue │ B (false) │ 1 │
├───────────────────────┼─────────────────────┼───────────────┼─────────┤
│ B₂₃ │ TaggedMatrixValue │ B (false) │ 2 │
├───────────────────────┼─────────────────────┼───────────────┼─────────┤
│ B₃₃ │ TaggedMatrixValue │ B (false) │ 3 │
└───────────────────────┴─────────────────────┴───────────────┴─────────┘
Organized into leftBlocks and rightBlocks
┌─────────────────────────────────┐ ┌─────────────────────────────────┐
│ leftBlocks (Matrix A) │ │ rightBlocks (Matrix B) │
├─────────┬─────────────────────┬─┤ ├─────────┬─────────────────────┬─┤
│ k-Index │ Matrix Block │ │ │ k-Index │ Matrix Block │ │
├─────────┼─────────────────────┼─┤ ├─────────┼─────────────────────┼─┤
│ 1 │ A₂₁ │ │ │ 1 │ B₁₃ │ │
├─────────┼─────────────────────┼─┤ ├─────────┼─────────────────────┼─┤
│ 2 │ A₂₂ │ │ │ 2 │ B₂₃ │ │
├─────────┼─────────────────────┼─┤ ├─────────┼─────────────────────┼─┤
│ 3 │ A₂₃ │ │ │ 3 │ B₃₃ │ │
└─────────┴─────────────────────┴─┘ └─────────┴─────────────────────┴─┘
The Multiplication and Aggregation Process
Computing C₂₃ Block
┌────────────────────────────────────────────────────────────────────┐
│ Step 1: Match and multiply blocks with the same k-index │
├────────────┬────────────┬────────────────────────┬─────────────────┤
│ k-Index │ Left Block │ Right Block │ Multiplication │
├────────────┼────────────┼────────────────────────┼─────────────────┤
│ 1 │ A₂₁ │ B₁₃ │ A₂₁ × B₁₃ │
├────────────┼────────────┼────────────────────────┼─────────────────┤
│ 2 │ A₂₂ │ B₂₃ │ A₂₂ × B₂₃ │
├────────────┼────────────┼────────────────────────┼─────────────────┤
│ 3 │ A₂₃ │ B₃₃ │ A₂₃ × B₃₃ │
└────────────┴────────────┴────────────────────────┴─────────────────┘
┌────────────────────────────────────────────────────────────────────┐
│ Step 2: Aggregate all multiplication results │
├────────────────────────────────────────────────────────────────────┤
│ C₂₃ = (A₂₁ × B₁₃) + (A₂₂ × B₂₃) + (A₂₃ × B₃₃) │
└────────────────────────────────────────────────────────────────────┘
Visual Representation of Complete Computation Flow
┌────────────────────────────────────────────────────────────┐
│ │
│ Matrix A Blocks Matrix B Blocks │
│ ┌───┬───┬───┐ ┌───┬───┬───┬───┬───┐ │
│ │A₁₁│A₁₂│A₁₃│ │B₁₁│B₁₂│B₁₃│B₁₄│B₁₅│ │
│ ├───┼───┼───┤ ├───┼───┼───┼───┼───┤ │
│ │A₂₁│A₂₂│A₂₃│ │B₂₁│B₂₂│B₂₃│B₂₄│B₂₅│ │
│ ├───┼───┼───┤ ├───┼───┼───┼───┼───┤ │
│ │A₃₁│A₃₂│A₃₃│ │B₃₁│B₃₂│B₃₃│B₃₄│B₃₅│ │
│ ├───┼───┼───┤ │
│ │A₄₁│A₄₂│A₄₃│ │
│ └───┴───┴───┘ │
│ │ │ │
└────────┼─────────────────────────────────┼──────────────────┘
│ │
▼ ▼
┌────────────────────────────────────────────────────────────┐
│ SHUFFLE PHASE │
│ │
│ ┌───────────────────────────────────────────────────┐ │
│ │ groupedBlocks │ │
│ │ │ │
│ │ Key (1,1): [A₁₁*, A₁₂*, A₁₃*, B₁₁*, B₂₁*, B₃₁*] │ │
│ │ Key (1,2): [A₁₁*, A₁₂*, A₁₃*, B₁₂*, B₂₂*, B₃₂*] │ │
│ │ ... │ │
│ │ Key (2,3): [A₂₁*, A₂₂*, A₂₃*, B₁₃*, B₂₃*, B₃₃*] │ │
│ │ ... │ │
│ └───────────────────────────────────────────────────┘ │
│ │ │
└────────────────────────┼───────────────────────────────────┘
│
▼
┌────────────────────────────────────────────────────────────┐
│ REDUCE PHASE │
│ │
│ For each output block location (i,j): │
│ │
│ 1. Separate A and B blocks into two maps by k-index │
│ ┌─────────┬────────┐ ┌─────────┬────────┐ │
│ │ k-Index │ A Block│ │ k-Index │ B Block│ │
│ ├─────────┼────────┤ ├─────────┼────────┤ │
│ │ 1 │ A₁₁ │ │ 1 │ B₁₁ │ │
│ │ 2 │ A₁₂ │ │ 2 │ B₂₁ │ │
│ │ 3 │ A₁₃ │ │ 3 │ B₃₁ │ │
│ └─────────┴────────┘ └─────────┴────────┘ │
│ │
│ 2. Multiply matching blocks: A₁₁×B₁₁, A₁₂×B₂₁, A₁₃×B₃₁ │
│ │
│ 3. Sum all products to get final C₁₁ block │
│ │
└────────────────────────────────────────────────────────────┘
│
▼
┌────────────────────────────────────────────────────────────┐
│ OUTPUT MATRIX C │
│ │
│ ┌───┬───┬───┬───┬───┐ │
│ │C₁₁│C₁₂│C₁₃│C₁₄│C₁₅│ │
│ ├───┼───┼───┼───┼───┤ │
│ │C₂₁│C₂₂│C₂₃│C₂₄│C₂₅│ │
│ ├───┼───┼───┼───┼───┤ │
│ │C₃₁│C₃₂│C₃₃│C₃₄│C₃₅│ │
│ ├───┼───┼───┼───┼───┤ │
│ │C₄₁│C₄₂│C₄₃│C₄₄│C₄₅│ │
│ └───┴───┴───┴───┴───┘ │
│ │
└────────────────────────────────────────────────────────────┘
This diagram illustrates how we transform the matrix multiplication problem from a memory-intensive operation to a streaming operation using the shuffle-reduce paradigm. Each output block C₍ᵢⱼ₎ is computed independently using only the blocks it needs, allowing us to process matrices larger than available memory.