Strassen Algorithm Multithreading using Callable (Thread Pool)

[subhaac]

I'm trying to implement Callable for Strassen's algorithm to multiply two matrices. I'm new to this, and i'm having a few issues and I can't figure it out for the life of me :( .

The first problem is that the program prints out 0 for all the elements of the resultant matrix. For example, if my n (size of matrices to be multiplied) is 4, i get a 4x4 resultant matrix with 0 as all the elements. Second thing is, my execution time increases as I increase the number of threads. Below is my code.

package strassen2;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.Callable;
import java.io.*;
import java.util.concurrent.ExecutionException;

/**
 *
 * @author Subhaa
 */
public  class Strassen2 implements Callable<int[][]>
{
    private  int[][] A;
    private  int[][] B;
    private  int n;
    private int C[][] = new int [n][n];

    public Strassen2 (int A[][], int B[][])
    {
        this.A = A;
        this.B = B;
        this.n = n;
        this.C = C;
    }

   @Override
   public int[][] call() throws Exception
   {

       if(A.length <= 2)
       {
       for (int i = 0 ; i < n ; i++)
       {
           for (int j = 0 ; j < n ; j++)
           {
               for (int k = 0 ; k < n ; k++)
               {
                    C[i][j] = A[i][k] * B[k][j];
               }
           }
       }
       }
       else
           strassenMatrixMultiplication(A,B);
       return C;
   }

    ExecutorService executor = Executors.newFixedThreadPool (4);

    public Strassen2() throws IOException, InterruptedException, ExecutionException
    {
        int n;
        int[][] a, b, c;

        n = 4; // Set size of matrices
        a = new int[n][n];
        b = new int[n][n];
        c = new int[n][n];

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                a[i][j] = 1;
            }
        }

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {

                b[i][j] = 1;

            }
        }

        long start_time = System.nanoTime();

        c = strassenMatrixMultiplication(a,b);

        long end_time = System.nanoTime();
        double difference = (end_time - start_time)/1e6;

        printArray(c);

        System.out.println("Time taken : " + difference);
                executor.shutdown();
                System.exit(0);

    }

    public int [][] strassenMatrixMultiplication(int [][] A, int [][] B) throws InterruptedException, ExecutionException
    {
        int n = A.length;
        int [][] result = new int[n][n];
        if((n%2 != 0 ) && (n !=1))
        {
            int[][] a1, b1, c1;
            int n1 = n+1;
            a1 = new int[n1][n1];
            b1 = new int[n1][n1];
            c1 = new int[n1][n1];
            for(int i=0; i<n; i++)
                for(int j=0; j<n; j++)
                {
                     a1[i][j] =A[i][j];
                     b1[i][j] =B[i][j];
                }

                c1 = strassenMatrixMultiplication(a1, b1);
                for(int i=0; i<n; i++)
                    for(int j=0; j<n; j++)
                        result[i][j] =c1[i][j];
                    return result;
        }
        if(n == 1)
        {
            result[0][0] = A[0][0] * B[0][0];
        }
        else
        {
        int [][] A11 = new int[n/2][n/2];
        int [][] A12 = new int[n/2][n/2];
        int [][] A21 = new int[n/2][n/2];
        int [][] A22 = new int[n/2][n/2];
        int [][] B11 = new int[n/2][n/2];
        int [][] B12 = new int[n/2][n/2];
        int [][] B21 = new int[n/2][n/2];
        int [][] B22 = new int[n/2][n/2];

        divideArray(A, A11, 0 , 0);
        divideArray(A, A12, 0 , n/2);
        divideArray(A, A21, n/2, 0);
        divideArray(A, A22, n/2, n/2);
        divideArray(B, B11, 0 , 0);
        divideArray(B, B12, 0 , n/2);
        divideArray(B, B21, n/2, 0);
        divideArray(B, B22, n/2, n/2);

        Future<int[][]> future1;
        Future<int[][]> future2;
        Future<int[][]> future3;
        Future<int[][]> future4;
        Future<int[][]> future5;
        Future<int[][]> future6;
        Future<int[][]> future7;

            int [][] P1 = null ;
            int [][] P2= null ;
            int [][] P3 = null;
            int [][] P4 = null;
            int [][] P5 = null;
            int [][] P6 = null;
            int [][] P7 = null;

        future1 = executor.submit(new Strassen2(addMatrices(A11, A22), addMatrices(B11, B22)));
        future2 = executor.submit(new Strassen2(addMatrices(A21, A22), B11));
        future3 = executor.submit(new Strassen2(A11, subtractMatrices(B12, B22)));
        future4 = executor.submit(new Strassen2(A22, subtractMatrices(B21, B11)));
        future5 = executor.submit(new Strassen2(addMatrices(A11, A12), B22));
        future6 = executor.submit(new Strassen2(subtractMatrices(A21, A11), addMatrices(B11, B12)));
        future7 = executor.submit(new Strassen2(subtractMatrices(A12, A22), addMatrices(B21, B22)));

        P1 = future1.get();
        P2 = future2.get();
        P3 = future3.get();
        P4 = future4.get();
        P5 = future5.get();
        P6 = future6.get();
        P7 = future7.get();

        int [][] C11 = addMatrices(subtractMatrices(addMatrices(P1, P4), P5), P7);           
        int [][] C12 = addMatrices(P3, P5);
        int [][] C21 = addMatrices(P2, P4);
        int [][] C22 = addMatrices(subtractMatrices(addMatrices(P1, P3), P2), P6);

        copySubArray(C11, result, 0 , 0);
        copySubArray(C12, result, 0 , n/2);
        copySubArray(C21, result, n/2, 0);
        copySubArray(C22, result, n/2, n/2);
    }
    return result;
}

    public int [][] addMatrices(int [][] A, int [][] B)
    {
        int n = A.length;
        int [][] result = new int[n][n];
        for(int i=0; i<n; i++)

            for(int j=0; j<n; j++)

                result[i][j] = A[i][j] + B[i][j];

         return result;
    }

    public int [][] subtractMatrices(int [][] A, int [][] B)
    {
        int n = A.length;
        int [][] result = new int[n][n];
        for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
        result[i][j] = A[i][j] - B[i][j];
        return result;
    }

    public void divideArray(int[][] parent, int[][] child, int iB, int jB)
    {
        for(int i1 = 0, i2=iB; i1<child.length; i1++, i2++)
        {
            for(int j1 = 0, j2=jB; j1<child.length; j1++, j2++)
            {
                child[i1][j1] = parent[i2][j2];
            }
        }

    }

    public void copySubArray(int[][] child, int[][] parent, int iB, int jB)
    {
        for(int i1 = 0, i2=iB; i1<child.length; i1++, i2++)
        for(int j1 = 0, j2=jB; j1<child.length; j1++, j2++)
        {
            parent[i2][j2] = child[i1][j1];
        }
    }

    public void printArray(int [][] array)
    {
        int n = array.length;
        System.out.println();
        for(int i=0; i<n; i++)
        {
         for(int j=0; j<n; j++)
            {
             System.out.print(array[i][j] + "\t");
            }
           System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) throws IOException, InterruptedException, ExecutionException 
    {
         new Strassen2();
    }

}

[Traevel]

If you look at the call()

else
    strassenMatrixMultiplication(A,B);
return C;

Nothing is being done with the result of strassenMatrixMultiplication(A,B).

All your P# = future#.get()'s are 0.

A few general remarks:

• Variable names should be lower case in Java, uppercase implies Objects.
• Always use { and } in if/else statements and loops to improve readability and avoiding mistakes, even if it's only one line.
• When you have to declare 7 different P's you're probably hard coding too much (and should use collections), although in this particular case it might make it easier to follow. Keep it in mind though.

[subhaac]

Oh thank you! I assigned the result of strassenMatrixMultiplication(A,B) to C. But i'm still getting zeroes. Also, any idea why this implementation of Strassen's algorithm is much slower than a naive algorithm like ijk-algorithm?

[JamesCherrill]

With 4x4 matrices I'm surprised you can even measure execution time meaningfully. I'm not surprised that the overheads of a thread pool would greatly exceed the time to do a few array maipulations. I guess each thread will complete within its first time slice.