3
\$\begingroup\$

Below is my code of matrix multiplication in Java. It has both implementation of matrix multiplication- one without multi-threading and another one using multi-threading.

For multi-threading implementation, I used Java's Executor Framework. I first created threads equal to the result matrix's column. Performance of the program improved for large matrix multiplication as compared to the non-threaded implementation. But the problem I am facing is when I make the number of threads less performance increased as compared to the performance of program using large number of threads.

For example, if I use only 10 threads rather than 1000 threads performance is faster, using 10 threads rather than 1000 threads for multiplying two matrices of size 1000*1000.

  • Time Taken by program using 10 threads lies between 14000 ms to 13000 ms.
  • Time Taken by program using 1000 threads lies between 15000 ms to 16000 ms.
  • Time Taken by program without threading lies between 30000 ms to 24000 ms.

I know there is overhead incurred in creating threads as each thread needs separate stack space.

My system configuration is :

  • 64 bit O/S Windows 7
  • 1 GB ram
  • 64 bit java 8

I want to know the trade-off which needs to be set to improve the performance.

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
class mainClass
{
    int row1;
    int col1;

    int row2;
    int col2;

    int A[][];
    int B[][];

    int C[][];
    int D[][];


    mainClass()
    {
        row1=1000;
        col1=1000;

        row2=1000;
        col2=1000;

        A= new int [row1][col1];
        B= new int [row2][col2];        
        C= new int [row1][col2];
        D= new int [row1][col2];

    }
    public static void main(String args[])
    {
        mainClass ob = new mainClass();
        int c=0;

        for(int i=0;i<ob.row1;i++)
        {
            for(int j=0;j<ob.col1;j++)
            {
                ob.A[i][j]=c++;
            }
        }

        c=0;

        for(int i=0;i<ob.row2;i++)
        {
            for(int j=0;j<ob.col2;j++)
            {
                ob.B[i][j]=c++;
            }
        }
        /*** Commented Below code as printing huge matrix takes long time ***/

        //System.out.print(" \nPrint Matrix A:\n\n");
        //ob.printMatrix(ob.A);
        //System.out.print(" \nPrint Matrix B:\n\n");
        //ob.printMatrix(ob.B);
        ob.matrixMulUtility();
    }

    public void matrixMulUtility()
    {
        long startTime = System.currentTimeMillis();

    // This method is for matrix multiplication without multithreading  
        matrixMultiply(); 
        long stopTime = System.currentTimeMillis();
        long elapsedTime = stopTime - startTime;
        System.out.println(" \nExecution time of matrixMultiply function is : "+ elapsedTime +"ms\n");

/*** Commented Below code as printing huge matrix takes long time ***/

        //System.out.print(" \nPrint Matrix C without multithreading:\n\n");
        //printMatrix( C);



/*** Below code is for matrix multiplication using multithreading ****/


        try{

        ExecutorService executor = Executors.newFixedThreadPool(this.col2);
        startTime = System.currentTimeMillis();
        for(int i=0;i<row1;i++)
        {
            for(int j=0;j<col2;j++)
            {
                RunnableClass ob = new RunnableClass(i,j,this);
                executor.execute(ob);
            }
        }

         executor.shutdown();
         while (!executor.isTerminated()) {
        }
        executor.awaitTermination(Long.MAX_VALUE, TimeUnit.NANOSECONDS);
        stopTime = System.currentTimeMillis();
        elapsedTime = stopTime - startTime;
        System.out.println(" \nExecution time of matrixMultiply function  using multithreadingis : "+ elapsedTime +"ms\n");
        }catch(Exception e)
        {

        }

        /*** Commented Below code as printing huge matrix takes long time ***/

        //System.out.print(" \nPrint Matrix D with multithreading:\n\n");
        //printMatrix( D);

    }
/** Non-Threaded Matrix multiplication function  **/

    void matrixMultiply()
    {
        for(int i=0;i<row1;i++)
        {
            for(int j=0;j<col2;j++)
            {
                for(int k=0;k<row2;k++)
                {
                    C[i][j]+=A[i][k]*B[k][j];
                }
            }
        }



    }

    void printMatrix(int ar[][])
    {
        int row=ar.length;
        int col=ar[0].length;
        for(int i=0;i<row;i++)
        {
            for(int j=0;j<col;j++)
            {
                System.out.print(" "+ar[i][j]);
            }
            System.out.print("\n");

        }
    }
}


/*** Runnable class for mutlithreaded matrix multiplication  ***/

class RunnableClass implements Runnable
{
    int i,j;
    mainClass ob;


    RunnableClass(int ii,int jj,mainClass ob1)
    {

        i=ii;
        j=jj;
        ob=ob1;

    }

    /*** Below code of run method is performing matrix multiplication for Each cell  and placing output in the resultant
        matrix D  ***/  

     public void run()
    {

        int sum=0;

        for(int k=0;k<ob.row2;k++)
        {

            sum+=ob.A[i][k]*ob.B[k][j];
        }

        ob.D[i][j]=sum;

    }
}
\$\endgroup\$
  • \$\begingroup\$ In theory and in practice, if your CPU has N cores spawning more than N threads will never lead to any performance increase (and like in your case it can even degrade performance). That's assuming you use your CPU for the computation. Matrix operations are much more efficiently implemented in parallel on the GPU which can have hundreds of cores. \$\endgroup\$ – TeodorD Nov 8 '17 at 19:30
  • \$\begingroup\$ Thanks TeodorD. Also can you explain in case of small size matrix multiplication like 5*5 non-threaded implementation was much faster than multi-threaded one. Its because of the Java's Executor framework or the thread creation incurring more overhead that the benefit of the parallel processing becomes null ? \$\endgroup\$ – rani rawat Nov 9 '17 at 7:58
  • \$\begingroup\$ Have a look at the wikipedia article on matrix multiplication. It has some notes on the tradeoffs involved in parallel solutions. \$\endgroup\$ – teppic Nov 9 '17 at 18:37
  • \$\begingroup\$ Also, when profiling you should perform the test several times in a row to allow the JVM to warm up. Initial runs will be slower because of the time required for class loading, memory allocation, hotspot optimisation etc. \$\endgroup\$ – teppic Nov 9 '17 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.