Быстрое умножение матриц в C # - PullRequest
Новая
       11

Быстрое умножение матриц в C #

9 голосов
/ 29 декабря 2010

У меня такой же маленький проект на c #, который включает в себя матрицы. Я обрабатываю большие объемы данных, разбивая их на куски n-длины, обрабатывая их как векторы и умножая на матрицу Вандермонда **. Проблема заключается в том, что в зависимости от условий размер патронов и соответствующей матрицы Вандермонда ** может варьироваться. У меня есть общее решение, которое легко прочитать, но слишком медленно: 

    public byte[] addBlockRedundancy(byte[] data) {
        if (data.Length!=numGood) D.error("Expecting data to be just "+numGood+" bytes long");

        aMatrix d=aMatrix.newColumnMatrix(this.mod, data);
        var r=vandermonde.multiplyBy(d);
        return r.ToByteArray();
    }//method

Это может обрабатывать около 1/4 мегабайта в секунду на моем i5 U470 @ 1,33 ГГц. Я могу сделать это быстрее, вручную вставляя матричное умножение: 

        int o=0;
        int d=0;
        for (d=0; d<data.Length-numGood; d+=numGood) {
            for (int r=0; r<numGood+numRedundant; r++) {
                Byte value=0;
                for (int c=0; c<numGood; c++) {
                    value=mod.Add(value, mod.Multiply(vandermonde.get(r, c), data[d+c]));
                }//for
                output[r][o]=value;
            }//for
            o++;
        }//for

Это может обрабатывать около 1 мегабит в секунду.

(Обратите внимание, что "мод" выполняет операции над GF (2 ^ 8) по модулю моего любимого неприводимого полинома.)

Я знаю, что это может быть намного быстрее: в конце концов, матрица Вандермонда ** в основном нули. Я должен быть в состоянии создать процедуру или найти процедуру, которая может взять мою матрицу и вернуть оптимизированный метод, который будет эффективно умножать векторы на данную матрицу, но быстрее. Затем, когда я даю этой подпрограмме матрицу Вандермонда 5x5 (единичную матрицу), просто не нужно выполнять арифметику, а исходные данные просто копируются.

** Обратите внимание: что я использую термин «Вандермонде», я на самом деле имею в виду матрицу идентичности с некоторым количеством строк из матрицы Вандермонда (см. Комментарии). Эта матрица замечательна из-за всех нулей, и потому что, если вы удалите достаточно строк (по вашему выбору), чтобы сделать ее квадратной, это обратимая матрица. И, конечно же, я хотел бы использовать эту же процедуру для преобразования любой из этих инвертированных матриц в оптимизированный ряд инструкций.

Как мне ускорить умножение матриц?

Спасибо!

(отредактировано, чтобы исправить мою ошибку с помощью матрицы Вандермонда)

Ответы [ 5 ]

3 голосов
/ 29 декабря 2010

Я видел решения, использующие Reflection.Emit, и я видел решения, в которых используется TPL. Реальный ответ здесь в большинстве случаев заключается в том, что вы хотите использовать существующую неуправляемую библиотеку, такую ​​как Intel MKL через P / Invoke. В качестве альтернативы, если вы используете GPU, вы можете использовать подход GPGPU, который будет намного быстрее.

И да, SSE вместе с многоядерной обработкой - это самый быстрый способ сделать это на процессоре. Но я бы не советовал писать свой собственный алгоритм - вместо этого поищите что-то, что уже есть. Скорее всего, это будет библиотека C ++, возможно, с оболочкой C #.

2 голосов
/ 16 февраля 2011

Вы можете попробовать: http://research.microsoft.com/en-us/projects/accelerator

Описание: Accelerator - это высокоуровневая параллельная библиотека данных, которая использует параллельные процессоры, такие как графический процессор или многоядерный процессор, для ускорения выполнения.

Вы можете использовать его из C # / F #

2 голосов
/ 29 декабря 2010

Может быть, вы можете определить матричный интерфейс и построить реализации во время выполнения, используя Reflection.Emit . 

IMatrix m = MatrixGenerator.CreateMatrix(data);

m.multiplyBy(...)

Здесь MatrixGenerator.CreateMatrix создаст адаптированную реализацию IMatrix с развертыванием полного цикла и дальнейшим сокращением кода (0 ячейка, идентификатор и т. Д.) MatrixGenerator.CreateMatrix может кэшировать матрицы, чтобы избежать повторного создания его позже для того же набора данных.

1 голос
/ 29 декабря 2010

Хотя это не ускорит математику, вы можете по крайней мере использовать все свои ядра с Parallel.For в .Net 4.0. ссылка Microsoft

0 голосов
/ 29 декабря 2010

С математической точки зрения

Вы можете посмотреть на собственные пространства, собственные векторы, собственные значения. Я не уверен, что делает ваше приложение и поможет ли оно.

Вы можете посмотреть на разложение LU.

Все вышеперечисленные темы можно найти в википедии

С точки зрения программирования

Вы можете попробовать SIMD, но они рассчитаны на матрицы 4x4 для выполнения однородных преобразований трехмерного пространства, в основном для компьютерной графики.

Вы можете написать специальные алгоритмы для ваших наиболее распространенных измерений.

Возможно ли использование SSE в c #?

...