Основная строка против основной колонки макет матрицы

16

При программировании вычислений с плотной матрицей, есть ли причина выбирать макет с основной строкой над макетом с основной колонкой?

Я знаю, что в зависимости от макета выбранной матрицы нам нужно написать соответствующий код, чтобы эффективно использовать кэш-память для повышения скорости.

Раскладка с основными строками кажется более естественной и простой (по крайней мере, мне). Но основные библиотеки, такие как LAPACK, написанные на Фортране, используют основной макет столбца, поэтому должна быть какая-то причина, чтобы сделать этот выбор.

smilingbuddha
источник
Если мы рассмотрим вычисление b = A * x с вектором столбца x, для мажорной строки A мы можем использовать внутренние произведения векторов A (i,:) ^ T x, чтобы получить b (i); для больших столбцов нам могут понадобиться только скалярные умножающие векторы, sum_i A (:, i) x (i). Мне кажется, колонка Major намного лучше! Как вы думаете?
Хуэй Чжан
Приучите себя любить колонну-мажор. Это легко, когда вы визуализируете векторы в виде столбцов или их транспонирование в виде строк. Это делает визуализацию умножения матриц очень простой и позволяет легко следить за множеством опубликованных математических данных.
Майк Данлавей

Ответы:

18

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

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

внутреннее хранилище Внутреннее хранилище основного формата столбца

Брайан Борхерс
источник
11

В вакууме, без учета какого-либо существующего программного обеспечения, нет причин отдавать предпочтение главному столбцу над главным по строке с точки зрения кода. Однако большая часть математической литературы написана таким образом, что векторы группируются в матрицу, сохраняя их в виде столбцов, а не строк. Например, когда вы пишете полное уравнение на собственные значения , XAИксзнак равноИксΛИксматрица содержит все собственные векторы, записанные в столбцах. Вы никогда не увидите, чтобы это было написано иначе (хотя я слышал, что статистические данные, как векторы строк). Поэтому было вполне естественно, что в самой ранней программе предполагался основной формат столбцов, поэтому если у вас есть матрица, представляющая собой набор векторов, память для любого отдельного вектора является непрерывной. Таким образом, я полагаю, что традиция только что перенесена на сегодняшний день, и если вы хотите взаимодействовать с старым Фортраном, вы хотите использовать столбец Major. Так что в значительной степени вся высокоэффективная числовая линейная алгебра сделана в главном столбце.

Причина, по которой C является мажорной строкой, является следствием синтаксиса его массива; Вы объявляете массив размером 3 строки на 2 столбца как double a[3][2], и более поздние индексы изменяются быстрее, чем более ранние индексы, что для двумерных массивов делает его главным в ряду. Сочетание этого с естественным западным порядком чтения слева направо делает ряд строк более естественным.

Виктор Лю
источник
2
Я думаю, что это плохие аргументы. Тот факт, что последний индекс в '' 'double a [3] [2]' '' меняется быстрее всего, не является совпадением - это было разумное дизайнерское решение, точно так же, как это было сознательное проектное решение в Fortran для делайте это наоборот, когда у вас есть массив '' 'real (3,2)' ''.
Вольфганг Бангерт
1
Кроме того, это уже не так, что почти все высокоэффективные числовые линейные алгебры являются главными столбцами. Это может все еще быть верным для BLAS и LAPACK, но это совсем не так для каждой основной библиотеки линейной алгебры, которая появилась за последние 15 лет: например, и PETSc, и Trilinos используют форматы хранения крупных разреженных матриц строк.
Вольфганг Бангерт
Я знаю, что соглашение C было сознательным решением, вероятно, основанным на естественном порядке чтения. Я имел в виду, что он, вероятно, не был разработан с учетом числовой линейной алгебры, что делает его совпадением с тем, что он является главным в ряду. Во-вторых, я не собирался использовать аргумент для разреженных матриц, только для плотных. В редких случаях это немного смешанное, с сжатыми форматами строк и столбцов.
Виктор Лю
5
Не говоря уже о сути, но C изначально был системным языком, основанным на более ранних языках B и BCPL, работающих в системах, подобных PDP-11, которые изначально не имели чисел с плавающей запятой. Сказать, что они разработали его с учетом чисел, довольно сложно.
Виктор Лю
7
Присутствие там и т. Д. Матрицы причины в C перемещают последний индекс быстрее всего потому, что у C нет матриц. У него есть векторы векторов, которые могут быть прозрачно реализованы как сплошные блоки памяти или как массивы указателей на массивы. Создание порядка индекса, совместимого с Фортраном, было (я предполагаю) даже не на радаре Денниса Ричи.
Майк Данлавей
2

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

Если вы программист на C / C ++, вы должны использовать некоторые библиотеки более высокого уровня для матриц (Eigen, Armadillo, ...) с порядком старших по умолчанию столбцов. Только маньяк будет использовать необработанные указатели C с порядком основной строки, хотя C / C ++ предлагает нечто, напоминающее индексирование матрицы.

Для простоты все с порядком мажорных строк следует считать как минимум странно сформированным. Срез за срезом - это просто естественный порядок, и он означает порядок столбцов (например, Fortran). У наших отцов / матерей были очень веские причины, по которым они выбрали именно это.

К сожалению, до того, как стало ясно, несколько интересных библиотек были созданы в порядке следования строк, вероятно, из-за недостатка опыта.

Чтобы уточнить, напомним определение порядка основной строки, где правый индекс изменяется быстрее за один шаг в памяти, например, A (x, y, z) это z-индекс, это означает, что в памяти пиксели из разных срезов смежны, что мы бы не хотели не хочу Для фильма A (x, y, t) последний индекс - время t. Нетрудно представить, что просто невозможно сохранить фильм в режиме мажорной строки.

Павел
источник
2

м×N

  • мя,Jя×м+J
  • мя,JJ×N+я

Теперь представьте следующий алгоритм:

for i from 1 to m
   for j from 1 to n
      do something with m(i,j)

я×м+J

Выводы:

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

  2. практическое правило: быстро меняющийся индекс должен быть сопоставлен с последовательными местоположениями в памяти.

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

BrunoLevy
источник