Multithread la variante de la multiplicación de matriz -- java campo con multithreading campo con matrix camp codereview Relacionados El problema

Multithread the variant of matrix multiplication


4
vote

problema

Español

Esta es la multiplicación de matriz. Big Matrix se divide en la submatriz y la multiplicación en paralelo, se fusionan los matrices de resultado que se fusionan. ¿Cómo puedo hacer que este código sea mejor?

  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;     } } }   
Original en ingles

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;     } } } 
        
     
     

Lista de respuestas

3
 
vote
vote
La mejor respuesta
 

Vamos a empezar con los cambios de simplificación:

  • Declare las variables y los campos como final siempre que sea posible. Esto simplifica drásticamente el razonamiento sobre el comportamiento de la mutación en su código. Dado que matrixA y matrixB se supone que cambien para la vida útil del objeto, deben ser declarados finales.

  • Hacer uso del almacenamiento en caché cuando tiene sentido: actualmente su código siempre volverá a calcular el resultado si se ejecuta el método 99887766555443333 , independientemente de si ya ha sido o no. Eso es básicamente un desperdicio de energía informática, podría evitar simplemente computar el resultado una vez y permitir que las llamadas futuras solo deben buscar ese resultado.

  • Mantenga el alcance de las variables lo más pequeñas posible. Verifique que la introducción de una variable en realidad tiene sentido antes de hacerlo. El código actualmente declara casi todas las variables que utiliza por adelantado. Eso me recuerda a los programas VBA viejos . En cualquier caso: es más fácil para usted (y el tiempo de ejecución) cuando las variables están en el alcance más pequeño posible

    future4 , start y end se puede declarar dentro del cuerpo del bucle respectivo. En call Usted solo usa n , 9988776655544339 y k Para decidir si 998877766555443310 o ejecuta el cálculo en una sola hilo. Esas variables son básicamente pelusa. Iníbalos para evitar confusiones al leer el código.

  • Parece que tiene una aversión al espacio en blanco. Es difícil subidividar el código en secciones lógicas porque no hay distinción entre los bloques. Esto hace que agarre el código significativamente más difícil.

Hay una gran posibilidad de simplificación en su diseño. Actualmente, el código intenta romper el problema en los cálculos de "SUBRESULT" por "Tareas". El problema que veo con esto es que las matrices hacen que esto sea más difícil de lo que debe ser. Para calcular el resultado en $ (i, j) $, necesita los lados de la izquierda y la fila de la derecha y la columna laterales de la derecha.
.
Dado que es un poco poco claro para mí cómo se organizan las matrices en su código, no me pondré en los detalles, pero estoy de acuerdo con OOPEXPERT Cuando él comentarios :

Si ese es el caso y no hay nada especial acerca de la multiplicación de la matriz que seguiría un enfoque totalmente. Me olvidaría de cualquier manejo de hilo y formularía el problema de una manera que pueda usar flujos paralelos

Ahora para hacerme lo suficientemente claro: no estoy proponiendo que reformule esto como una solución utilizando matrixA1 s. No he encontrado mucho la manera de hacer que ese parezca bien. En su lugar, me esforzaría por calcular cada entrada de forma independiente. Esto le permitirá controlar trivialmente la cantidad de energía de la CPU que desea lanzar en el problema (en lugar de esta solución algo desordenada).

Creo que podría tener una buena oportunidad de reformular esto utilizando una simplificación. Dado que solo leído de las matrices de entrada y las entradas de la matriz de resultados son totalmente independientes entre sí, puede tener un gran éxito en plenificación de un 998877665555443312 para cada entrada que la tarea solo necesita matrixA3 , matrixA4 , así como un matrixA5 y matrixA6 para realizar sus tareas. Puede controlar el nivel de paralelismo al establecer un límite en la cantidad de hilos que puede usar su grupo de ejecutores.

En general, la solución me sorprende como una simplificación pesada sobre el código actual, ya que no confía en subdividir las matrices en submatrims. Eso lo hace mucho más comprensible: una tarea para uno .

 

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.

 
 
2
 
vote

Me gustaría proporcionar un esquema para un enfoque diferente utilizando las corrientes paralelas de Java.

El problema aquí es identificar los elementos necesarios para que una tarea sea ejecutable independiente. Necesitas:

  1. la posición del elemento en la matriz de destino donde el producto escalar debe colocarse
  2. todas las posiciones de elementos de las dos matrices de origen para el producto escalar
  3. Leer acceso a las dos matrices de origen
  4. Acceso de escritura sincronizada a la matriz de destino

Ahora podemos formular la corriente. El arroyo proporciona la información de 1. y 2. en secuencia. Debe crear su propia función de proveedor y un Spliterator personalizado para poder finalizar el flujo si no se debe calcular más productos escalares.

Para cada elemento de la transmisión que ahora puede realizar el cálculo del producto escalar. Después de eso, puede publicar el resultado en la matriz de destino. Debe asegurarse de que la matriz de destino esté protegida por un monitor (sincronizado, bloqueo, etc.)

En este enfoque, se hará transparente para usted.

¿Dónde está la dificultad?

La parte más difícil es la función de proveedor de la corriente. Tienes que crear y "iteración", como algoritmo, que proporciona la información de 1. an 2. en un objeto en secuencia con un "nextlement" -method.

Otra cosa difícil es que las corrientes personalizadas normalmente no terminan en Java 8. En Java 9 se anunció que tenía construcciones de API fácil de usar para eso. Actualmente, debe implementar un "Spliterator", así llamado "Spliterator" (o extiende el Plitador abstracto) y construir el flujo con él.

Por fin quiero mencionar que la corriente paralela introduce un punto de "tenedor" donde se distribuye el trabajo. A medida que se distribuye el trabajo, debe unirlo en algún momento. En su caso, es la matriz objetivo que consolida los resultados. Por lo tanto, tiene que estar bajo control de un monitor, ya que los resultados se proporcionan de forma asíncrona.

Un ejemplo para eso que proporcioné en una respuesta diferente aquí .

Las siguientes afirmaciones son subjetivas:

Mi opinión personal a los cálculos como estos es: debe poder cargar la CPU equilibrada sin preocuparse por el manejo de hilos y un poco de manejo de sincronización. Hay otras aplicaciones que iría con hilos. Actualmente no estoy seguro de cuál es la regla "cuándo usar qué", ya que estoy convencido, hay uno, pero nadie lo ha descubierto todavía.

 

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.

 
 

Relacionados problema

2  La matriz hash realiza la eliminación gaussiana  ( Hash matrix performs gaussian elimination ) 
Esta es la matriz de hash que usé para procesar la matriz para mi algoritmo cuadrático de tamiz. Puede encontrar el código completo en aquí (es java 7 ), p...

5  Multiplicación de matriz y producto de punto  ( Matrix multiplication and dot product ) 
Ejercicio 2.37. Supongamos que representamos vectores v = (vi) como secuencias de números, y matrices m = (MIJ) como secuencias de vectores (las filas ...

2  Hackerank - Queens Attack II - Java  ( Hackerrank queens attack ii java ) 
La definición del problema ya se puede encontrar aquí . Dado un tablero de ajedrez con dimensiones N Ã- N (donde n es de hasta 100000) y el ( r , C )...

4  Aumentar el rendimiento de una matrícula de la multiplicación de matriz de 2x2  ( Increase performance of a spate of 2x2 matrix multiplication ) 
Me gustaría mejorar el rendimiento de la pieza de código a continuación (en Fortran). Da buenos resultados, pero el perfil le dice que es donde pasa la mayor ...

19  Clase de matriz en C #  ( Matrix class in c ) 
He estado aprendiendo C # durante mi tiempo libre en los últimos meses; Antes de eso, en su mayoría estaba escribiendo Java, por lo que la transición no ha si...

3  Análisis de simetría para arreglos atómicos en un cristal  ( Symmetry analysis for atom arrangements in a crystal ) 
Por un tiempo ahora he tenido la intención de publicar un poco de mi código Haskell aquí para que alguien pueda decirme qué partes de la biblioteca de idiomas...

3  Solución más rápida para la resta sabia de la matriz  ( Faster solution for row wise matrix subtraction ) 
Tengo 2 matrices. Tengo que calcular la distancia euclidiana entre cada fila de Matrix A y cada fila de Matrix B. En la primera solución i bucle sobre las f...

1  Integración de oscilador de fase perturbada  ( Perturbed phase oscillator integration ) 
Estoy integrando un sistema de osciladores de fase perturbados. Defino el sistema de ecuación y también la matriz jacobiana. Tengo que remodelar el vector dim...

0  Código de número de rutas posible de la longitud dada entre 2 nodos dados  ( Code for number of routes possible of the given length between 2 given nodes ) 
Recientemente me encontré en este problema , aquí hay un extracto de eso, Es bien sabido que el algoritmo de enrutamiento utilizado en Internet es altam...

4  Asignación de matrices para la modificación en el lugar  ( Allocating matrices for in place modification ) 
Este código parece estar funcionando. Estoy asignando matrices en la pila y los pasa a funciones para modificar en su lugar. ¿Es esta una práctica estándar, o...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos