Как сохранить матрицу в C ++ нелинейным способом

Question

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

Теперь я могу вычислять диагональные элементы одновременно. Это все в порядке.

Моя проблема теперь связана с кэшем. Матрицы в c ++ обычно сохраняются в памяти построчно, верно? Ну, это не очень хорошо для меня, так как мне нужно 2 элемента предыдущей строки и 1 элемент текущей строки, чтобы вычислить мой результат, это ужасно в отношении кеша. Кэш будет содержать текущую строку (или ее часть), затем я запрашиваю предыдущую, которая, вероятно, больше не будет храниться. Затем для другой мне нужна другая часть диагонали, поэтому еще раз, я прошу совершенно разные строки, и в кеше не будет готовых для меня.

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

Как ты это делаешь? Я пытался искать в Интернете, но я никогда не мог найти ничего, что показало бы мне путь. Можно ли сказать с ++, как упорядочить этот тип в памяти?

РЕДАКТИРОВАТЬ: Как некоторые из вас, кажется, запутались в природе моего вопроса. Я хочу сохранить матрицу (не имеет значения, сделаю ли я ее двумерным массивом или любым другим способом) в MEMORY по своему усмотрению. Как правило, двумерный массив будет сохранять строку за строкой, мне нужно работать с диагоналями, поэтому кэши будут сильно пропускать огромные матрицы, над которыми я буду работать (возможно, миллионы строк и столбцов).

Answer 1

Я полагаю, что у вас может быть неправильное восприятие (CPU) кеша.

Это правда, что кеширование ЦП является линейным - то есть, если вы обращаетесь к адресу в памяти, оно принесет в кэш некоторые предыдущие и последующие местоположения памяти - что похоже на «угадывание», что последующие обращения будут включать1-мерно-близкие элементы.Однако это верно на микроуровне.Кэш ЦП состоит из большого количества маленьких «строк» ​​(64 байта на всех уровнях кеша в последних процессорах Intel).Местность ограничена линией;разные строки кэша могут приходить из совершенно разных мест в памяти.

Таким образом, если вам «нужны два элемента предыдущей строки и один элемент текущей строки» вашей матрицы, то кэш должен работать очень хорошо дляВы: Часть кеша будет содержать элементы предыдущей строки, а некоторые будут содержать элементы текущей строки.И когда вы переходите к следующему элементу, общий кэш обычно будет содержать элементы матрицы, к которым вам нужен доступ.Просто убедитесь, что ваш порядок итераций соответствует порядку прогрессии в строке кэша.

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

Редактировать: Как gezaпримечания: если строки вашей матрицы длинные, вы все равно будете дважды читать каждую ячейку памяти с простым подходом: сначала как текущая строка, затем снова как предыдущая строка, так как каждое значение будет удалено из кэша до егоиспользуется в качестве значения предыдущей строки.Если вы хотите избежать этого, вы можете перебрать плитки вашей матрицы, чей размер (длина x ширина x sizeof (элемент)) помещается в кэш L1 (наряду со всем остальным, что там должно быть).Вы также можете рассмотреть хранение ваших данных в тайлах, но я не думаю, что это было бы слишком полезно.

Answer 2

Предварительный комментарий: «Расстояние Левенштейна» - это расстояние редактирования (согласно общему определению). Это очень распространенная проблема; Вам, вероятно, даже не нужно беспокоиться о написании решения самостоятельно. Ищите существующий код.

Теперь, наконец, для правильного ответа ... На самом деле вам вообще не нужна матрица, и вам, конечно, не нужно ее "сохранять": достаточно просто держать "переднюю часть" своего матрица динамического программирования, а не целое.

Но какой «фронт» вы выберете и как его продвигать? Я предлагаю вам использовать антидиагонали в качестве фронта, и, учитывая каждую антидиагональность, одновременно вычислять следующую антидиагональность. Таким образом, это будет {(0,0)}, затем {(0,1), (1,0)}, затем {(0,2), (1,1), (2,0)} и т. Д. на. Каждая антидиагональ требует не более двух более ранних антидиагоналей - и если мы будем хранить значения каждой антидиагонали последовательно в памяти, то схема доступа, идущая вверх по следующей антидиагональности, представляет собой линейную прогрессию вдоль предыдущих антидиагоналей - что отлично подходит для кеша (см. мой другой ответ ).

Таким образом, вы будете "согласовывать" вычисления, предоставляя каждому потоку кучу последовательных антидиагональных элементов для вычисления; Это должно делать свое дело. И в любой момент вы сохраните только 3 антидиагональных в памяти: тот, над которым вы работаете, и два предыдущих. Вы можете переключаться между тремя такими буферами, чтобы не перераспределять память все время (но затем убедитесь, что предварительно выделяете буферы с максимальной антидиагональной длиной).

Все это должно работать в основном одинаково для неквадратного случая.

Answer 3

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

В противном случае вы можете легко реализовать его как этот тип и реализовать оператор [int, int] для вашей матрицы