Multithreading matrix multiplication in C#

Question

I have a task - write multithreading matrix multiplication. Each vector product must be calculated in new thread.(If we have matrices n by m and m by k we must have n by k threads). Also I must show order of calculation for elements of result matrix. I wrote code and got strange result - order of calculation is almost sequentially. But I calculate each element in new thread, so I must get random order of calculation for elements of the result matrix. What is wrong? This is my code.

using System;
using System.Threading;
using System.Collections.Generic;

namespace MatrixMultiplication
{
class Matrix
{
    public int Row{get; set;}
    public int Column { get; set;}
    double[,] arr;
    Matrix() { }
    public Matrix(int row,int column)
    {
        Row = row;
        Column = column;
        arr = new double[row, column];
    }
    public double[] GetColumn(int i)
    {
        double[] res=new double[Row];
        for (int j = 0; j < Row; j++)
            res[j] = arr[j, i];
        return res;
    }
    public double[] GetRow(int i)
    {
        double[] res = new double[Column];
        for (int j = 0; j < Column; j++)
            res[j] = arr[i, j];
        return res;
    }
    public double this[int i,int j]
    {
        get { return arr[i, j]; }
        set { arr[i, j] = value; }
    }
    public Matrix RandomValues()
    {
        Random rnd=new Random();
        for (int i = 0; i < Row; i++)
            for (int j = 0; j < Column; j++)
                arr[i, j] =rnd.Next(10);
        return this;
    }

    public void Print()
    {
        for(int i=0;i<Row;i++){
            for (int j = 0; j < Column; j++)
                Console.Write(arr[i,j]+" ");
            Console.WriteLine();
        }
    }

    public static Matrix operator*(Matrix a, Matrix b)
    {
        Matrix result=new Matrix(a.Row,b.Column);
        List<Thread> threads = new List<Thread>();
        for (int i = 0; i <a.Row*b.Column;i++ )
        {
            int tempi = i; 
            Thread thread = new Thread(()=>VectorMult(tempi, a, b, result));
            thread.Start();
            threads.Add(thread);
        }
        foreach (Thread t in threads)
            t.Join();
        return result;
    }

    public  static void VectorMult(int tmp, Matrix a, Matrix b,Matrix result){
        int i = tmp / b.Column;
        int j = tmp % b.Column;
        double[] x = a.GetRow(i);
        double[] y = b.GetColumn(j);
        for (int k = 0; k < x.Length; k++)
            result[i, j] += x[k] * y[k];
        Console.WriteLine("Calculate element{0}{1}", i, j);
    }
  }

  class Program
  {
     static void Main(string[] args)
     {
         int n = int.Parse(Console.ReadLine());
         int m = int.Parse(Console.ReadLine());
         int k = int.Parse(Console.ReadLine());
         Matrix A = new Matrix(n,m).RandomValues();
         Matrix B = new Matrix(m,k).RandomValues();
         A.Print();
         Console.WriteLine(new String('-',20));
         B.Print();
         Console.WriteLine(new String('-', 20));
         Matrix C = A * B;
         C.Print();
    }
  }
}

Answer 1

What you're describing is normal - see this post from earlier today which demonstrates how processes in separate threads don't always operate in the expected sequence. They might do so much or most of the time, but then you get some unexpected behavior.

Do the calculations need to occur in a specific sequence, or do you just need to be able to see the sequence in which they occurred?

If you're starting new threads then it's impossible to control the sequence. (You've already seen that.) You also can't capture the order in which they were completed, because completion of a calculation and recording the result (the console or any other output) isn't an atomic operation.

This could happen:

1. Calculation A finishes
2. Calculation B finishes
3. Calculation B is recorded
4. Calculation A is recorded

Multithreading isn't great when operations have to occur in a specific sequence.

You can insert the results of your calculation into a ConcurrentQueue as they are completed, and the sequence will be mostly correct.

Answer 2

Firstly, you should keep your code as simple and explicit as possible. Instead of calculating i < a.Row * b.Column you should have made 2 fors:

for (int i = 0; i < a.Row; i++)
    for (int j = 0; j < b.Column; j++)
    {
        int tempi = i;
        int tempj = j;
        Thread thread = new Thread(() => VectorMult(tempi, tempj, a, b, result));
        thread.Start();
        threads.Add(thread);
    }

And then, in the VectorMult(int tmpi, int tmpj, Matrix a, Matrix b, Matrix result) function, instead of calculating that j = tempi % b.Column stuff, you give as parameter tempj. Having i and j it becomes:

int i = tmpi;
int j = tmpj;
double[] x = a.GetRow(i);
double[] y = b.GetColumn(j);
for (int k = 0; k < x.Length; k++)
    result[i, j] += x[k] * y[k];

Finally, don't forget that when working with shared resources and threads, things can go pretty crazy. Make sure you use Mutexes.

Here you have my whole code,

using System;
using System.Threading;
using System.Collections.Generic;

namespace MatrixMultiplication
{
    class Matrix
    {
        public int Row { get; set; }
        public int Column { get; set; }
        double[,] arr;
        public static Mutex mutex = new Mutex();

        Matrix() { }
        public Matrix(int row, int column)
        {
            Row = row;
            Column = column;
            arr = new double[row, column];
        }
        public double[] GetColumn(int i)
        {
            double[] res = new double[Row];
            for (int j = 0; j < Row; j++)
                res[j] = arr[j, i];
            return res;
        }
        public double[] GetRow(int i)
        {
            double[] res = new double[Column];
            for (int j = 0; j < Column; j++)
                res[j] = arr[i, j];
            return res;
        }
        public double this[int i, int j]
        {
            get { return arr[i, j]; }
            set { arr[i, j] = value; }
        }
        public Matrix RandomValues()
        {
            Random rnd = new Random();
            for (int i = 0; i < Row; i++)
                for (int j = 0; j < Column; j++)
                    arr[i, j] = rnd.Next(10);
            return this;
        }

        public void Print()
        {
            for (int i = 0; i < Row; i++)
            {
                for (int j = 0; j < Column; j++)
                    Console.Write(arr[i, j] + " ");
                Console.WriteLine();
            }
        }

        public static Matrix operator *(Matrix a, Matrix b)
        {
            Matrix result = new Matrix(a.Row, b.Column);
            List<Thread> threads = new List<Thread>();
            for (int i = 0; i < a.Row; i++)
                for (int j = 0; j < b.Column; j++)
                {
                    int tempi = i;
                    int tempj = j;
                    Thread thread = new Thread(() => VectorMult(tempi, tempj, a, b, result));
                    thread.Start();
                    threads.Add(thread);
                }
            foreach (Thread t in threads)
                t.Join();
            return result;
        }

        public static void VectorMult(int tmpi, int tmpj, Matrix a, Matrix b, Matrix result)
        {
            mutex.WaitOne();
            int i = tmpi;
            int j = tmpj;
            double[] x = a.GetRow(i);
            double[] y = b.GetColumn(j);

            for (int k = 0; k < x.Length; k++)
                result[i, j] += x[k] * y[k];

            mutex.ReleaseMutex();
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("n=");
            int n = int.Parse(Console.ReadLine());
            Console.Write("m=");
            int m = int.Parse(Console.ReadLine());
            Console.Write("k=");
            int k = int.Parse(Console.ReadLine());
            Matrix A = new Matrix(n, m).RandomValues();
            Matrix B = new Matrix(m, k).RandomValues();
            A.Print();
            Console.WriteLine(new String('-', 20));
            B.Print();
            Console.WriteLine(new String('-', 20));
            Matrix C = A * B;
            C.Print();
            Console.ReadLine();
        }
    }
}

Wish you all the best! :)