MPI Fox Algorithm

Implementation of the Fox algorithm for square matrix multiplication using MPI

The objective of this project is to show the execution time and RAM usage of the algorithm for different matrix sizes and number of processes.

The program will run the algorithm for all the matrix sizes \( 2^x\ \forall\ x \in [n, m] \) five times and will calculate the average execution time and RAM usage. The results will be used to generate a graph that will be saved in the charts folder.

Developed by

José Felipe Marcial Rojas. Github
Miguel Ángel Hernández Moreno. Github

TO DO

• Add RAM measurement for Windows.
• Create CSV files with the results.
• Add a script to generate the charts from the CSV files.
• Add charts to docs page.

References

• Dean, N. (2017). Matrix Multiplication. https://www.cs.csi.cuny.edu/~gu/teaching/courses/csc76010/slides/Matrix%20Multiplication%20by%20Nur.pdf
• mpi4py. (2023). https://mpi4py.readthedocs.io/en/stable/
• Matplotlib (2023) https://matplotlib.org/
• Manim (2023) https://docs.manim.community/en/stable/

How It Works

This chapter is a detailed explanation of how the algorithm works, its implementation in Python and its dependencies, how to measure the time and ram memory consumption, as well as its graphing.

Algorithm Explanation

• Checkerboard
• Fox Algorithm
• Example 2x2 Fox's Algorithm

Checkerboard

Most parallel matrix multiplication functions use a checkerboard distribution of the matrices. This means that the processes are viewed as a grid, and, rather than assigning entire rows or entire columns to each process, we assign small sub-matrices. For example, if we have four processes, we might assign the element of a 4x4 matrix as shown below, checkerboard mapping of a 4x4 matrix to four processes.

Fox Algorithm

Fox‘s algorithm is a one that distributes the matrix using a checkerboard scheme like the above.

In order to simplify the discussion, lets assume that the matrices have order \(n\), and the number of processes, \(p\), equals \(n^2\). Then a checkerboard mapping assigns \(a_{ij}\), \(b_{ij}\) , and \(c_{ij}\) to process (\(i\), \(j\)).

Fox‘s algorithm takes \(n\) stages for matrices of order n one stage for each term aik bkj in the dot product

\(C_{i,j} = a_{i,0}b_{0,j} + a_{i,1}b_{1,i} +. . . +a_{i,n−1}b_{n−1,j}\)

Initial stage, each process multiplies the diagonal entry of A in its process row by its element of B:

Stage \(0\) on process\((i, j)\): \(c_{i,j} = a_{i,i} b_{i,j}\)

Next stage, each process multiplies the element immediately to the right of the diagonal of A by the element of B directly beneath its own element of B:

Stage \(1\) on process\((i, j)\): \(c_{i,j} = a_{i,i+1} b_{i+1,j}\)

In general, during the kth stage, each process multiplies the element k columns to the right of the diagonal of A by the element \(k\) rows below its own element of B:

Stage \(k\) on process\((i, j)\): \(c_{i,j} = a_{i,i+k} b_{i+k,j}\)

Example 2x2 Fox's Algorithm

Consider multiplying 2x2 block matrices \(A\), \(B\), \(C\):

\[ \begin{aligned} A \times B &= C \\ \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} &= \begin{bmatrix} 2 & 2 \\ 2 & 2 \end{bmatrix} \end{aligned} \]

Stage 0:

\[ \begin{bmatrix} a_{00}, b_{00} & a_{00}, b_{01}\\ a_{11}, b_{10} & a_{11}, b_{11}\\ \end{bmatrix} \]

Process (\(i\), \(j\)) computes:

\[ \begin{aligned} C_{\text{Stage 0}} = \begin{bmatrix} 1 \times 1 & 1 \times 1 \\ 1 \times 1 & 1 \times 1 \end{bmatrix} &= \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} \end{aligned} \]

Shift-rotate on the columns of \(B\)

Stage 1:

\[ \begin{matrix} a_{01}, b_{10} & a_{01}, b_{11}\\ a_{10}, b_{00} & a_{10}, b_{01}\\ \end{matrix} \]

Process (\(i\), \(j\)) computes:

\[ \begin{aligned} C_{\text{Stage 1}} = \begin{bmatrix} 1+1 \times 1 & 1+1 \times 1 \\ 1+1 \times 1 & 1+1 \times 1 \end{bmatrix} &= \begin{bmatrix} 2 & 2 \\ 2 & 2 \end{bmatrix} \end{aligned} \]

Fox in Secuencial

• Imports
• Check Operating System and Define Constants
• Matrix Multiplication Function:**
• Matrix Initialization
• Matrix Multiplication Loop
• Print Results
• Main Execution

Sequential implementation of the Fox matrix multiplication algorithm. It initializes matrices, performs the multiplication, prints execution time and resource usage. The progress bar (tqdm) visualizes the iteration progress.

Imports

import os
import numpy as np
from sys import argv
from tqdm import tqdm
from time import perf_counter

We import necessary libraries, including os, numpy, sys, tqdm (for progress bar), and time.

Check Operating System and Define Constants

isLinux = os.name == 'posix'
if isLinux:
   from resource import getrusage, RUSAGE_SELF

Determines if the operating system is Linux and imports resource-related functions for measuring resource usage.

Matrix Multiplication Function:**

def fox_SEC(exponent: int, isInt: bool) -> float:

Defines a function fox_SEC that takes the exponent and a flag isInt as parameters and returns the execution time.

Matrix Initialization

MATRIX_SIZE = 2**exponent
matrix_A = ...
matrix_B = ...
matrix_C = np.zeros((MATRIX_SIZE, MATRIX_SIZE), dtype=int) if isInt else np.zeros((MATRIX_SIZE, MATRIX_SIZE))

Initializes square matrices (A), (B), and (C) of size (2^{\text{exponent}} \times 2^{\text{exponent}}) with random integers or floats based on the isInt flag.

Matrix Multiplication Loop

start_time = perf_counter()

for x in tqdm(range(MATRIX_SIZE)):
   for i in range(MATRIX_SIZE):
       y = (x + i) % MATRIX_SIZE
       matrix_C[i] += matrix_A[i, y] * matrix_B[y]

Performs matrix multiplication using nested loops. It calculates the product matrix (C) by iterating through rows and columns.

Print Results

print(perf_counter() - start_time)
print(getrusage(RUSAGE_SELF).ru_maxrss) if isLinux else print(0)

Prints the execution time and the RAM usage if the operating system is Linux.

Main Execution

if __name__ == '__main__':
   fox_SEC(int(argv[1]), bool(argv[2]))

Calls the fox_SEC function with command-line arguments for exponent and isInt flag if we want matrices with integers or float type number.

Fox MPI

• Imports
• Check Operating System and Define Constants
• Command Line Arguments
• MPI Initialization
• Matrix Initialization on Rank 0
• Broadcast Data to All Processes
• Matrix Multiplication Loop
• MPI Allreduce
• Print Results

We use MPI to parallelize the matrix multiplication of randomly generated squared matrices A and B, and it calculates the product matrix C. The matrices are distributed among processes, and each process computes a portion of the final result. The MPI Allreduce function is used to combine the partial results from all processes.

Imports

import os
import numpy as np
from sys import argv
from mpi4py import MPI
from time import perf_counter

The code imports necessary libraries, including os, numpy, sys, mpi4py, and time. mpi4py is used for MPI (Message Passing Interface) communication in parallel computing.

Check Operating System and Define Constants

isLinux = os.name == 'posix'

Determines if the operating system is Linux.

if isLinux:
   from resource import getrusage, RUSAGE_SELF

On Linux, it imports resource-related functions to measure resource usage.

Command Line Arguments

exponent = int(argv[1])
isInt = bool(argv[2])

Reads command line arguments: exponent and isInt. These are used to define the size of the matrices and the type of matrix elements.

MPI Initialization

comm = MPI.COMM_WORLD  # get the communicator object
size = comm.Get_size() # total number of processes
rank = comm.Get_rank() # rank of this process

Initializes MPI communication, retrieves the total number of processes, and the rank of the current process.

Matrix Initialization on Rank 0

if rank == 0:
   MATRIX_SIZE = 2**exponent
   # generate two random matrices of size MATRIX_SIZE
   # initialize the matrices A, B, and C
   # matrices A and B contain random integers or floats based on 'isInt'
   matrix_A = ...
   matrix_B = ...
   matrix_C = np.zeros((MATRIX_SIZE, MATRIX_SIZE), dtype=int) if isInt else np.zeros((MATRIX_SIZE, MATRIX_SIZE))
   data = (MATRIX_SIZE, matrix_A, matrix_B, matrix_C)
else:
   data = None

On the master process (rank 0), it initializes matrices A, B, and C, and packs the data into a tuple (data). Other processes receive None.

Broadcast Data to All Processes

data = comm.bcast(data, root=0)  # broadcast the data to all processes
MATRIX_SIZE, matrix_A, matrix_B, matrix_C = data  # unpack the data

All processes receive the data using MPI broadcast.

Matrix Multiplication Loop

start_time = perf_counter()
for x in range(MATRIX_SIZE):
   if rank == x % size:
       for i in range(MATRIX_SIZE):
           y = (x + i) % MATRIX_SIZE
           matrix_C[i] += matrix_A[i, y] * matrix_B[y]

Each process calculates a row of the matrix C. The rows are distributed among processes, and the multiplication is performed locally.

MPI Allreduce

comm.Allreduce(MPI.IN_PLACE, matrix_C, op=MPI.SUM)

MPI Allreduce function is used to sum the rows of matrix C calculated by each process.

Print Results

if rank == 0:
   print(perf_counter() - start_time)
   print(getrusage(RUSAGE_SELF).ru_maxrss) if isLinux else print(0)

The master process prints the execution time and the RAM memory usage if the operating system is Linux.

Time and Memory Measurement

• Time Measurement
• Memory Consumption Measurement (RAM)

This code measures the execution time and memory consumption using the time and resource modules. Let's break down how the time and memory measurements are implemented:

Time Measurement

The perf_counter function from the time module is used to measure the execution time.

start_time = perf_counter()
# ... (code to be measured)
print(perf_counter() - start_time)

• start_time is recorded using perf_counter() before the code to be measured.
• The execution time is calculated by subtracting start_time from the current time after the code has executed.
• The result is printed, representing the time taken for the code to run.

Memory Consumption Measurement (RAM)

getrusage only works in linux/unix and FreeBSD operative systems based, therefore, this functionality is disabled in windows. For more compatibility information check the resource library docs.

The getrusage function from the resource module is used to measure the maximum resident set size, which is an indicator of memory consumption.

print(getrusage(RUSAGE_SELF).ru_maxrss) if isLinux else print(0)

• getrusage(RUSAGE_SELF).ru_maxrss retrieves the maximum consumption of RAM used by the process.
• This value is printed only if the operating system is Linux (isLinux is True); otherwise, it prints 0.

Charts Generator

• Matplotlib
  • Calculate Mean Times and Memory Usage
  • Prepare Data for Plotting
  • Configure Bar Chart Parameters
  • Create Matplotlib Figure
  • Configure Plot Titles and Labels
  • Plot Execution Time Bars
  • Plot Memory Usage Bars
  • Display Labels and Legends
  • Save Plots
• Manim
  • Manim Scene Class
  • Configure Frame Dimensions
  • Create Bar Chart
  • Create Axes Labels
  • Create Group for Chart and Labels
  • Create Title and Architecture Information
  • Display Elements
  • Animate Chart Bars
  • Display Bar Labels
  • Save and Display Animation
  • Main Execution Loop
  • Move Generated Files

We have used the matplotlib and manim library to represent the comparison of the execution times and memory usage of the Fox algorithm with matrices of either integers or floats.

Matplotlib

Calculate Mean Times and Memory Usage

times_MPI, times_SEC, memory_MPI, memory_SEC = data(min_e, max_e, isInt=isInt)

Calls the data function to obtain execution times and memory usage for sequential and parallel executions.

Prepare Data for Plotting

y_Time_MPI   = [np.mean(times_MPI [exponent]) for exponent in times_MPI ]
y_Time_SEC   = [np.mean(times_SEC [exponent]) for exponent in times_SEC ]
y_Memory_MPI = [np.mean(memory_MPI[exponent]) for exponent in memory_MPI]
y_Memory_SEC = [np.mean(memory_SEC[exponent]) for exponent in memory_SEC]

Calculates the mean times and memory usage for both MPI and sequential executions.

Configure Bar Chart Parameters

bar_w = 0.35
x_Time_MPI   = np.array([exponent - bar_w/2 for exponent in times_MPI])
x_Time_SEC   = np.array([exponent + bar_w/2 for exponent in times_SEC])
x_Memory_MPI = np.array([exponent - bar_w/2 for exponent in memory_MPI])
x_Memory_SEC = np.array([exponent + bar_w/2 for exponent in memory_SEC])

Sets parameters for the bar chart, including bar width and positions for both time and memory plots.

Create Matplotlib Figure

fig, (Time_ax, Memory_ax) = plt.subplots(1, 2, figsize=(20, 5)) if isLinux else plt.subplots(1, 1, figsize=(10, 5))

Creates a Matplotlib figure with one or two subplots, depending on whether the operating system is Linux.

Configure Plot Titles and Labels

fig.suptitle(f'Comparison of Fox Algorithm Executions with {num_type} numbers.\n{PROCESSOR} - {nthreads} Threads - {RAM}GB')
Time_ax.set_title('Sequential and Parallel Execution Time Comparison')
Time_ax.set_xlabel('Matrix Order')
Time_ax.set_ylabel('Execution Time (s)')

Sets titles and labels for the plots.

Plot Execution Time Bars

bars_Time_MPI = Time_ax.bar(x_Time_MPI, y_Time_MPI, bar_w, label='MPI', color='#EA75FA')
bars_Time_SEC = Time_ax.bar(x_Time_SEC, y_Time_SEC, bar_w, label='Sequential', color='#4590FA')

Plots bars for execution times for both MPI and sequential executions.

Plot Memory Usage Bars

In the background we use getrusage. This function only works in linux/unix and FreeBSD operative systems based, therefore, this functionality is disabled in windows. For more compatibility information check the resource library docs.

if isLinux:
   Memory_ax.set_title('Memory Usage (RAM) Comparison')
   Memory_ax.set_xlabel('Matrix Order')
   Memory_ax.set_ylabel('Memory Used (MB)')
   bars_Memory_MPI = Memory_ax.bar(x_Memory_MPI, y_Memory_MPI, bar_w, label='MPI', color='#EA75FA')
   bars_Memory_SEC = Memory_ax.bar(x_Memory_SEC, y_Memory_SEC, bar_w, label='Sequential', color='#4590FA')

Plots bars for memory usage for both MPI and sequential executions.

Display Labels and Legends

for bar in bars_Time_SEC + bars_Time_MPI:
   x_pos   = bar.get_x() + bar.get_width()/2.0
   y_value = bar.get_height()
   Time_ax.text(x_pos, y_value, f'{y_value:5.5}s', va='bottom', ha='center')
Time_ax.legend()

if isLinux:
   for bar in bars_Memory_SEC + bars_Memory_MPI:
       x_pos   = bar.get_x() + bar.get_width()/2.0
       y_value = bar.get_height()
       Memory_ax.text(x_pos, y_value, f'{(y_value/1024):5.5}MB', va='bottom', ha='center')
   Memory_ax.legend()

Displays labels and legends on the plots.

Save Plots

plt.tight_layout()
fig.savefig(create_dir('charts', f'{2**(min_e)}-{2**(max_e-1)}', 'int' if isInt else 'float'))

Saves the plots to a file.

Manim

This Manim script defines a scene that creates an animated bar chart using data from different matrix multiplication scenarios. The script loops over various parameters, generates animations, and saves the results in an organized directory structure.

Manim Scene Class

class chart(Scene):
   def construct(self):

Defines a Manim scene class named chart.

Configure Frame Dimensions

config["frame_width"] = 12
config["frame_height"] = 8

Sets the width and height of the animation frame.

Create Bar Chart

chart = BarChart(
   values = np.zeros(len(data)),
   y_range=[0, round(max_v + max_v/8,2), round(max_v/4,2)],
   x_length=16,
   y_length=6,
   bar_width=0.8,
   bar_names=[2**exp for exp in EXP],
   y_axis_config={"font_size": 24},
   x_axis_config={"font_size": 24},
).scale(0.7)

Creates a bar chart using Manim's BarChart class with specified configurations.

Create Axes Labels

x_label = chart.get_x_axis_label('Matrix Size', edge=DOWN, direction=DOWN, buff=0.05).scale(0.6)
y_l = 'Time (s)' if MEASURE == 'time_mean' else 'Memory (MB)'
y_label = chart.get_y_axis_label(y_l, edge=UP, direction=UP, buff=-1).scale(0.6).rotate(PI/2).next_to(chart, LEFT)

Adds labels for the x-axis and y-axis.

Create Group for Chart and Labels

gv = VGroup(chart, x_label, y_label).to_edge(DOWN)

Groups the chart and labels together.

Create Title and Architecture Information

Title = f'Comparison of RAM used by the Fox algorithm with {dt} numbers using the {meth} method' if MEASURE == 'memory_mean' else f'Comparison of execution time of the Fox algorithm with {dt} numbers using the {meth} method'
t_top = Tex(Title).scale(0.75).to_edge(UP)
architecture = Tex(f'{PROCESSOR} {THREADS} {RAM} DDR4 3200MHz', color='purple_a').scale(0.6).next_to(t_top, DOWN)

Creates a title and information about the system architecture.

Display Elements

self.play(Create(gv), Create(t_top), Create(architecture))

Displays the grouped chart, labels, title, and architecture information.

Animate Chart Bars

self.play(chart.animate.change_bar_values(data), run_time=1.5)

Animates the bars in the chart based on the data.

Display Bar Labels

self.play(Create(chart.get_bar_labels(font_size=30, color=WHITE)))

Displays labels for the bars in the chart.

Save and Display Animation

self.wait(3)

Waits for 3 seconds before completing the animation.

Main Execution Loop

if __name__ == '__main__':
    # Loop over different parameters (DTYPE, METHOD, EXP) and generate animations for each case.

Uses nested loops to iterate over different data parameters and create animations for each case.

Move Generated Files

shutil.move('manim/media/images/chart.png', f'{path}/{file}.png')
shutil.move('manim/media/videos/720p30/chart.mp4', f'{path}/{file}.mp4')

Moves the generated image and video files to a specified directory.

Results

• AMD Ryzen 5 3600
  • Characteristics
  • Float
    • Float Sequential Time
    • Float MPI Time
  • Integer
    • Integer Sequential Time
    • Integer MPI Time
• AMD Ryzen 3 5300U with Radeon Graphics
  • Characteristics
  • Float
    • Float Sequential Time
    • Float Sequential Memory
    • Float MPI Time
    • Float MPI Memory
  • Integer
    • Integer Sequential Time
    • Integer Sequential Memory
    • Integer MPI Time
    • Integer MPI Memory

AMD Ryzen 5 3600

Characteristics

• 6 Core Processor 12 Threads
• 16GB RAM DDR3
• Windows 11

Float

Float Sequential Time

Float MPI Time

Integer

Integer Sequential Time

Integer MPI Time

AMD Ryzen 3 5300U with Radeon Graphics

Characteristics

• 4 Threads
• 8 GB RAM
• Ubuntu 20.01 LTS

Float

Float Sequential Time

Float Sequential Memory

Float MPI Time

Float MPI Memory

Integer

Integer Sequential Time

Integer Sequential Memory

Integer MPI Time

Integer MPI Memory

Installation

This chapter explains how to test this implementation on both unix/linux and Windows based systems.

Linux Installation

For this installation we used:

• Arch Linux 2023.11.1 and Ubuntu 20.04 LTS
• Python 3.11.5
• pip 23.3.1

First, clone the github repository:

git clone https://github.com/miguehm/fox-algorithm.git && cd fox-algorithm

or alternatively, download the zip file and extract it:

Then, create a virtual environment

python3 -m venv venv

activate the virtual environment

source ./venv/bin/activate # for linux

and install requirements

pip install -r requirements.txt

Windows installation

For this installation we used:

• Windows 11 Nov 2023 update
• Python 3.11.5
• pip 23.3.1

You need to have MPI installed, you can download the installer from the microsoft official page.

First, clone the github repository:

git clone https://github.com/miguehm/fox-algorithm.git && cd fox-algorithm

or alternatively, download the zip file and extract it:

Then, create a virtual environment

python -m venv venv

activate the virtual environment

.\venv\Scripts\Activate

and install requirements

pip install -r requirements.txt

Usage

WARNING: The program will execute the algorithm for all the matrix sizes \(2^x\ \forall\ x \in [n, m]\). For values of \(n\) and \(m\) greater than 11, the execution time will be very long. For example, for \(n=11\) and \(m=12\), the execution time will be approximately 1 hour.

python3 is for linux/unix OS based, if you have windows use python instead.

• Help
• Default execution
• Multiple matrix multiplication by range
• Specify threads number

Help

python3 src/main.py --help

Output

Usage: main.py [OPTIONS]                        
                                                 
╭─ Options ─────────────────────────────────────╮
│ --help          Show this message and exit.   │
╰───────────────────────────────────────────────╯
╭─ Matrix order range ──────────────────────────╮
│ --min-exp        INTEGER  Exponent of base 2  │
│                           matrix order (2^)   │
│                           [default: 6]        │
│ --max-exp        INTEGER  Exponent of base 2  │
│                           matrix order (2^)   │
│                           [default: 13]       │
╰───────────────────────────────────────────────╯
╭─ MPI options ─────────────────────────────────╮
│ --threads        INTEGER  Number of cores to  │
│                           use                 │
│                           [default: 4]        │
╰───────────────────────────────────────────────╯

Default execution

python3 src/main.py

The execution will be done for the matrix of size \(2^6\) with 4 threads.

Multiple matrix multiplication by range

python3 src/main.py --min-exp 6 --max-exp 13

The charts with the results will be created in the charts folder.

Specify threads number

python3 src/main.py --threads 4

You can find out the number of threads available on your computer using top command.