#c #arrays #matrix #multiplication
#c #массивы #матрица #умножение
Вопрос:
В середине кода на c , eclipse, мне нужно вычислить умножение матриц A и B размером 2400 * 3600 (поэтому размеры не совпадают). Матрицы хранятся в двумерных массивах с плавающей точкой.Они не разрежены, никаких ограничений.
Каждое умножение занимает очень много времени (несколько минут), и мне серьезно нужно сократить его, потому что у меня есть цикл, который повторяется 50 миллионов раз. и каждый раз новые A и B должны быть перемножены. Приветствуются любые рекомендации по сокращению временных затрат. (даже изменение структуры хранения данных, если вы считаете, что это может помочь). Например, что, если я сохраню данные в одномерных массивах? Или использовать векторы вместо массивов?
В одном конкретном случае первый столбец всегда равен 1, а значения равны либо 1, -1, либо нулю. Есть идеи для этого случая?
В других случаях значения могут быть любыми. ** одним из этих умножений является X, умноженное на его транспонированное. Есть ли какие-либо рекомендации по этому конкретному?
Комментарии:
1. Наивный алгоритм для общего умножения матриц в O (n ^ 3), но есть способы сократить это до O (n ^ (2.7ish)). Это просто очень большие вычисления, если вы не можете немного сократить объем работы перед началом. Если большое число возникает в результате последовательного набора преобразований, возможно, вы можете выполнить по одному на строку и найти дельты . Или что -то еще.
2. В ваших матрицах в основном нули? Если это так, то, возможно, вы сможете найти алгоритм умножения, который работает с разреженными матрицами. Разреженная матрица — это, по сути,
(i,j)->valueотображение.
Ответ №1:
Я бы не стал валять дурака, пытаясь написать свой собственный: Google для LAPACK или BLAS, двух проверенных временем пакетов для численных вычислений, оба оптимизированы в энной степени. Оба имеют C API, которые вы можете использовать.
Комментарии:
1. 1: обе библиотеки используют не только оптимизированные алгоритмы, они также используют оптимизированные реализации, основанные на инструкциях SSE.
Ответ №2:
Это определенно поможет сохранить вашу вторую матрицу транспонированной, чтобы столбцы совпадали со строками кэша вместо строк. Разница во времени доступа между кэшем L2 и основной памятью составляет около 10 раз.
Комментарии:
1. Хотя это кажется довольно очевидным, я не понял, что вы имеете в виду. Не могли бы вы объяснить немного больше? Что, если я действительно хочу умножить A на его транспонирование?
2. @Pegah: Если вы посмотрите на алгоритм умножения матриц, вы обнаружите, что внутренний цикл выглядит примерно так:
sum = 0; for( int k = 0; k < n; k ) sum = a[i][k] * b[k][j]; c[i][j] = sum;. Последовательные итерации обращаются кa[i][0],a[i][1]a[i][2],,, что прекрасно, потому что они хранятся рядом друг с другом в памяти, поэтому кэш может считывать большой фрагмент из основной памяти за раз. Но вы также получаете доступ кb[0][j],b[1][j]b[2][j],, у которого очень плохая локальность, и кешу приходится выполнять много отдельных передач из основной памяти, что очень расточительно.
Ответ №3:
Вы могли бы попробовать собственный алгоритм.
Ответ №4:
Если вы говорите о миллионах умножений, первое, что я бы сделал, это обратился к чему-то вроде CUDA или DirectCompute, чтобы разгрузить работу на GPU, что намного лучше подходит для такого рода вещей. Это то, что сделал MATLAB, даже если ускорение GPU необязательно.
Существует множество примеров умножения матриц с ускорением GPU, поэтому ваша работа не должна быть слишком сложной.
Комментарии:
1. на самом деле мне нужно сделать это в середине кода на c , и его результаты будут использоваться остальным кодом. таким образом, это не независимая работа. Насколько я понял (я только что искал в Интернете), GPU — это аппаратная реализация, а Directcompute — это отдельное приложение. Я ошибаюсь? или я все еще могу использовать GPU в своем коде?
2. Я понятия не имею, о чем вы говорите.. CUDA и DirectCompute — это API, которые позволяют выполнять арифметические вычисления на вашем графическом процессоре. Аппаратная реализация чего? В середине кода C ? В отличие от чего?..
3. @Pegah Да, ваш графический процессор, вероятно, является аппаратной реализацией 🙂
4. @Pegah: Графический процессор означает просто чип процессора на вашей видеокарте. Он очень хорош при выполнении многих одинаковых операций одновременно, но не так хорош при сложном ветвлении. Умножение матрицы — это ВО многом одна и та же операция, поэтому она выполняется очень-очень быстро на графическом процессоре. DirectCompute, CUDA и OpenCL — это библиотеки, которые позволяют программе на C выдавать инструкции вашей видеокарте и перемещать данные туда и обратно.