Как транспонировать матрицу в java (параллельно/многопоточно)

Все мы знаем, насколько полезна транспозиция матриц, и написать общий алгоритм для последовательного использования не составит труда. Однако у меня возникли некоторые проблемы с тем, чтобы сделать то же самое для многопоточных целей, и я получил только этот небольшой случай для правильной работы 4 x 4.

Мой подход заключается в назначении равных частей структуры double[][], в данном случае 2 x 2, каждому из четырех потоков. В данном случае это означает начальные позиции 0,0, 0,2, 2,0 и 2,2. Это передается с помощью «kol» и «rad».

Однако я не могу заставить это работать с большими матрицами, поэтому любая помощь будет оценена. Ближайший ответ на эту проблему, который я нашел, находится здесь: Как распараллелить транспонировать матрицу?

Это также вдохновило меня на разделение структуры double[][] на четыре части. Мой (рабочий) код 4 x 4 можно найти ниже, так как я могу изменить его для работы с четырьмя потоками?

Ваше здоровье!

public double[][] transponerMatrise(double[][] matrise, int rad, int 
kol, int id)
{
  if((id != 2))
   {
      for (int i = rad; i < n/2 + rad; i++)
      {
        for (int j = kol+1; j < n/2 + kol; j++)
        {
          System.out.println("Traad " + id + " bytter " + i + "," + j + " med " + j + "," + i);
          System.out.println("Value is " + matrise[i][j] + ", " + matrise[j][i]);
            element = matrise[i][j];
            matrise[i][j] = matrise[j][i];
            matrise[j][i] = element;
        }
      }
    }
    else
    {
      for (int i = rad; i < n/2 + rad-1; i++)
      {
        for (int j = kol; j < n/2 + kol; j++)
        {
          System.out.println("Traad " + id + " bytter " + i + "," + j + " med " + j + "," + i);
          System.out.println("Value is " + matrise[i][j] + ", " + matrise[j][i]);
            element = matrise[i][j];
            matrise[i][j] = matrise[j][i];
            matrise[j][i] = element;
        }
      }
    }
    return matrise;
}

PS: я знаю, что код работает правильно, потому что у меня есть метод проверки рабочего последовательного варианта.


java multithreading transpose parallel-processing matrix
person Torstein Norum Bugge    schedule 01.03.2018    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Это априори проигранная борьба с функцией затрат O(N^2).

Если я могу обратить ваше внимание на более разумный подход, имеющий почти O(1) (постоянную) стоимость, этот трюк поможет вам начать работать в более перспективном направлении.

Можно попробовать добавить один тонкий слой абстракции поверх высокопроизводительного настроенного (кэш-линий, дружественного к «сырому»-хранилищу матричных элементов. Этот абстрактный слой поможет получить доступ к «сырому»-хранилищу (используя оси индексации, трюки с шагами и нарезками - точно так же, как библиотеки HPC FORTRAN вдохновили известные numpy и его трюки с шагами), и таким образом .T-метод не будет делать ничего дорогого (аналогично стиранию N^2 областей памяти, подкачке туда и обратно), но просто меняем местами параметры осей в абстрактном слое, отвечающем за отображение косвенности, что занимает несколько десятков наносекунд для любого большого matrise[N,N]; where N = 10, 100, 1000, 10000, 100000, 1000000, 10000000+< /strong> еще несколько [ns].

Нет ничего более быстрого в выполнении той или иной, более сложной, матричной операции, и методы FORTRAN и numpy, отполированные до совершенства, сами по себе являются доказательством такого наблюдения.

person user3666197    schedule 01.03.2018

arrow_upward
1
arrow_downward

Может быть, было бы просто использовать поток для замены строки на столбец, но поэтому вам нужно вдвое больше памяти для вашей матрицы, что может быть проблемой для огромных матриц. также, если у вас 6-ядерный процессор, я думаю, что от использования 100 потоков не так много пользы, поэтому мой пул потоков очень мал. И, как упомянул @user3666197, это все еще дорогое решение, но параллельно ;-)

import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class MatrixTransposition {

    public static void main(final String[] args) throws InterruptedException {
        final MatrixTransposition transposition = new MatrixTransposition();
        final int[][] source = transposition.create(32);
        final int[][] transposed = transposition.solve(source);
        System.out.println("Compare source and transpositon = " + transposition.compare(source, transposed));
        final int[][] result = transposition.solve(transposed);
        System.out.println("Compare source and double transpositon = " + transposition.compare(source, result));

        transposition.print(source);
        transposition.print(transposed);
    }

    public boolean compare(final int[][] a, final int[][] b) {
        for (int r = 0; r < a.length; r++) {
            for (int c = 0; c < a[0].length; c++) {
                if (a[r][c] != b[r][c]) return false;
            }
        }
        return true;
    }

    public int[][] create(final int size) {
        final int[][] result = new int[size][size];
        for (int r = 0; r < size; r++) {
            for (int c = 0; c < size; c++) {
                result[r][c] = r * size + c;
            }
        }
        return result;
    }

    public void print(final int[][] input) {
        final int size = input.length;
        final int maxNr = size * size;
        final int digits = new String(maxNr + "").length();
        final String cellFormat = "%0" + digits + "d ";

        for (int r = 0; r < input.length; r++) {
            final int[] row = input[r];
            for (final int c : row) {
                System.out.print(String.format(cellFormat, c));
            }
            System.out.println("");
        }

        System.out.println("");
    }

    public int[][] solve(final int[][] input) throws InterruptedException {
        final int width = input.length;
        final int height = input[0].length;

        final int[][] result = new int[width][height];
        final CountDownLatch latch = new CountDownLatch(width);
        for (int r = 0; r < width; r++) {
            final int row = r;
            threadPool.execute(() -> {
                solvePart(result, input, row);
                latch.countDown();
            });
        }

        latch.await();
        return result;
    }

    private void solvePart(final int[][] result, final int[][] input, final int r) {
        System.out.println("Solve row " + String.format("%02d", r) + " in thread " + Thread.currentThread().getName());
        final int[] row = input[r];
        for (int c = 0; c < row.length; c++) {
            result[c][r] = row[c];
        }
    }
    private final ExecutorService threadPool = Executors.newFixedThreadPool(6);
}
person IEE1394    schedule 01.03.2018

arrow_upward
0
arrow_downward

на основе подхода пользователя 3666197 вы можете сделать что-то вроде этого:

public class Matrix {

        private class Index {
            Index(final int row, final int col) {
                super();
                this.row = row;
                this.col = col;
            }

            int col;
            int row;
        }

        public Matrix(final int rows, final int cols) {
            this.rows = rows;
            this.cols = cols;
            data = new int[rows][cols];
        }

        public int get(final int row, final int col) {
            return get(getIndex(row, col));
        }

        public void set(final int row, final int col, final int value) {
            set(getIndex(row, col), value);
        }

        public void transpose() {
            transpositioned = !transpositioned;
        }

        private int get(final Index index) {
            return data[index.row][index.col];
        }

        private Index getIndex(final int row, final int col) {
            return transpositioned ? new Index(col, row) : new Index(row, col);
        }

        private void set(final Index index, final int value) {
            data[index.row][index.col] = value;
        }

        private final int cols;
        private final int[][] data;
        private final int rows;
        private boolean transpositioned;

    }
person IEE1394    schedule 01.03.2018