4
\$\begingroup\$

This is matrix multiplication. Big matrix split on the submatrix and multiplication in parallel, result matrices merge to result. How i can make this code better?

public class MatrixMultiplication implements Callable<int[][]> {
private static int LENGTH_OF_SIDE = 1000;
private int taskCount = 4;
private int[][] matrixA;
private int[][] matrixB;

public MatrixMultiplication(int[][] matrixA, int[][] matrixB) {
    this.matrixA = matrixA;
    this.matrixB = matrixB;
}

public void setTaskCount(int taskCount) {
    this.taskCount = taskCount;
}

@Override
public int[][] call() {
    int n = matrixA.length;
    int m = matrixA[0].length;
    int p = matrixB[0].length;
    try {
        if (n >= LENGTH_OF_SIDE || m >= LENGTH_OF_SIDE || p >= LENGTH_OF_SIDE) {
            return splitAndMerge(matrixA, matrixB);
        } else {
            return MultiplicationMatrixSingleThread.multiplicationMatrices(matrixA, matrixB);
        }
    } catch (InterruptedException | ExecutionException e) {
        e.printStackTrace();
        return null;
    }
}

public int[][] splitAndMerge(int[][] matrixA, int[][] matrixB) throws ExecutionException,
        InterruptedException {
    ExecutorService service = Executors.newCachedThreadPool();
    int n = matrixA.length;
    int m = matrixA[0].length;
    int k = matrixB[0].length;
    int bound = n / taskCount;
    int start;
    int end;
    Future<int[][]> future;
    List<Future<int[][]>> matrices = new ArrayList<>();
    for (int task = 0; task < taskCount; task++) {
        start = task * bound;
        end = (task + 1) * bound;
        future = service.submit(new MultiplicationSubMatrixN(matrixA, matrixB, start, end));
        matrices.add(future);
    }
    int[][] result = new int[n][k];
    int[][] currentMatrix;
    for (int st = 0; st < taskCount; st++) {
        currentMatrix = matrices.get(st).get();
        System.arraycopy(currentMatrix, 0, result, st * bound, currentMatrix.length);
    }
    if (n % taskCount != 0) {
        int begin = n - n % taskCount;
        currentMatrix = new int[n % taskCount][m];
        for (int i = 0; i < currentMatrix.length; i++) {
            System.arraycopy(matrixA[i + begin], 0, currentMatrix[i], 0, currentMatrix[0].length);
        }
        currentMatrix = MultiplicationMatrixSingleThread.multiplicationMatrices(currentMatrix, matrixB);
        System.arraycopy(currentMatrix, 0, result, begin, currentMatrix.length);
    }
    service.shutdown();
    return result;
}

private class MultiplicationSubMatrixN implements Callable<int[][]> {
    private int[][] matrixA;
    private int[][] matrixB;
    private int start;
    private int end;

    private MultiplicationSubMatrixN(int[][] matrixA, int[][] matrixB, int start, int end) {
        this.matrixA = matrixA;
        this.matrixB = matrixB;
        this.start = start;
        this.end = end;
    }

    @Override
    public int[][] call() throws Exception {
        int n = matrixA.length;
        int m = matrixA[0].length;
        int k = matrixB[0].length;
        int[][] matrixC = new int[n / taskCount][k];
        for (int i = start; i < end; i++) {
            for (int j = 0; j < k; j++) {
                for (int l = 0; l < m; l++) {
                    matrixC[i - start][j] += matrixA[i][l] * matrixB[l][j];
                }
            }
        }
        return matrixC;
    }
}
}
\$\endgroup\$
  • \$\begingroup\$ Do you want to have control over the amount of threads working? Or do you want to load your CPUs with max parallelism? \$\endgroup\$ – oopexpert Feb 10 '17 at 15:51
  • \$\begingroup\$ @oopexpet iam want to load my CPUs with max parallelism. \$\endgroup\$ – diofloyk Feb 10 '17 at 16:21
  • \$\begingroup\$ If that is the case and there is nothing special about the matrix multiplication I would follow a totally other approach. I would forget about any thread handling and formulate the problem in a way that I am able to use parallel streams. \$\endgroup\$ – oopexpert Feb 10 '17 at 16:34
3
\$\begingroup\$

Let's start with the simplification changes:

  • Declare variables and fields as final wherever possible. This drastically simplifies reasoning about mutation behaviour in your code. Since matrixA and matrixB are not supposed to change for the lifetime of the Object, they should be declared final.

  • Make use of caching when it makes sense: Currently your code will always recompute the result if the call method is executed, regardless of whether it has already been or not. That's basically a waste of computing power you could prevent by just computing the result once and allowing future calls to just lookup that result.

  • Keep the scope of variables as small as possible. Double check that introducing a variable actually makes sense before doing that. The code currently declares almost all variables it uses upfront. That reminds me of old vba programs. In either case: it's easier for you (and the runtime) when variables are in the smallest scope possible

    future, start and end can be declared inside the respective loop body. in call you only use n, m and k to decide whether you splitAndMerge or run the calculation on a single thread. Those variables are basically just fluff. Inline them to prevent confusion when reading the code.

  • You seem to have an aversion to whitespace. It's hard to subidivide the code into logical sections because there's no distinction between blocks. This makes grasping the code significantly harder.

There's a large possibility for simplification in your design. Currently the code attempts to break the problem into "subresult" computations by "tasks". The problem I see with this is that matrices make this harder than it needs to be. To compute the result at \$(i,j)\$ you need the left hand sides \$i\$th row and the right hand sides \$j\$th column.
Since it's a bit unclear to me how the matrices are organized in your code, I'll not get into the details, but I agree with oopexpert when he comments:

If that is the case and there is nothing special about the matrix multiplication I would follow a totally other approach. I would forget about any thread handling and formulate the problem in a way that I am able to use parallel streams

Now to make myself sufficiently clear: I'm not proposing you reformulate this as a solution using Streams. I haven't quite found a way to make that look nice. Instead I'd strive to calculate each entry independently. This will allow you to trivially control how much CPU-power you want to throw at the problem (instead of this somewhat messy solution).

I think you could have a good chance at reformulating this using a simplification. Since you only read from the input matrices and result matrix entries are fully independent of one another you can have great success enqueueing a separate Task for each entry that task only needs matrixA, matrixB as well as a row and column to perform it's duties. You can control the level of parallelism by setting a limit on how many Threads your executor pool may use.

Overall that solution strikes me as a heavy simplification over the current code, because it doesn't rely on subdividing the matrices into submatrices. That makes it much more understandable: one task for one result.

\$\endgroup\$
2
\$\begingroup\$

I'd like to provide a schema for a different approach using java parallel streams.

The problem here is to identify the elements needed for a task to be independent executable. You need:

  1. the element position in the target matrix where the scalar product has to be put
  2. all element positions of the two source matrices for the scalar product
  3. read access to the two source matrices
  4. synchronized write access to the target matrix

Now we can formulate the stream. The stream provides the information of 1. and 2. in sequence. You have to create your own Supplier-function and a custom Spliterator to be able to end the stream if no more scalar product needs to be calculated.

For each element of the stream you now can perform the calculation of the scalar product. After that you can publish the result in the target matrix. You have to ensure that the target matrix is protected by a monitor (synchronized, lock, etc.)

In this approach threading will be transparently done for you.

Where is the difficulty then?

The most difficult part is the Supplier-Function of the stream. You have to create and "iteration"-like algorithm that provides the information of 1. an 2. in ONE object in sequence with a "nextElement"-method.

Another tricky thing is that custom streams normally do not end in Java 8. In Java 9 was announced to have easy to use API constructs for that. Currently you have to implement a so called "Spliterator" (or extends AbstractSpliterator) and build the stream with it.

At last I want to mention that the parallel stream introduces a "fork" point where work is distributed. As work is distributed you have to join it at some point. In your case it is the target matrix that consolidates the results. So it has to be under control of a monitor as the results are provided asynchronously.

An example for that I provided in a different answer here.

The next statements are subjective:

My personal opinion to calculations like these is: You must be able to load the CPU balanced without caring about thread handling and little synchronization handling. There are other applications I would go with threads. I am currently not sure about what's the rule "when to use what" as I am convinced there is one but nobody has figured it out yet.

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.