как на карту памяти огромную матрицу?

Question

Предположим, вы получили огромную (40+ ГБ) матрицу значений объектов (с плавающей запятой), строки - это различные объекты, а столбцы - образцы / изображения.

Таблица предварительно рассчитана по столбцам.Затем он полностью доступен по строкам и многопоточно (каждый поток загружает целый ряд) несколько раз.

Каков наилучший способ обработки этой матрицы?Я особенно размышляю над 5 пунктами:

1. Так как он работает на компьютере x64, я могу отобразить всю матрицу памяти сразу, но будет ли это иметь смысл?
2. Как насчет эффектовмногопоточности (а также многопоточные начальные вычисления?)?
3. Как расположить матрицу: мажор строки или столбца?
4. Поможет ли пометить матрицу как доступную только для чтения после предварительного вычисления?закончено?
5. Может ли что-то вроде http://www.kernel.org/doc/man-pages/online/pages/man2/madvise.2.html быть использовано для ускорения этого?

Answer 1

Отображение памяти всего файла может значительно упростить процесс.

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

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

madvise может оказаться полезным, как только ваше приложение написано и работает.

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

Согласно упоминанию JimR о страницах размером 4 МБ в его комментарии, вы, возможно, захотите заглянуть в hugetlbfs или использовать версию Linux Kernel с прозрачной поддержкой огромных страниц (объединенная для 2.6.38, возможно, будет исправлена ​​в более ранние версии). Это, скорее всего, сэкономит вам массу промахов TLB и убедит ядро ​​выполнить дисковый ввод-вывод достаточно большими порциями, чтобы амортизировать любые затраты на поиск.

Answer 2

1. Может быть, см. Ниже.
2. Размер общего рабочего набора всех потоков не должен превышать доступную оперативную память, в противном случае программа будет работать со скоростью улитки из-за подкачки.
3. Макет должен соответствовать шаблонам доступа при условии соблюдения условия 2.
4. Что вы подразумеваете под "пометить только для чтения"?
5. Мера.

Re 3: Если у вас, например, 8 процессоров, но недостаточно ОЗУ для загрузки 8 строк, вы должны заставить каждый поток последовательно обрабатывать свои строки в управляемых блоках. В этом случае имеет смысл использовать блочную компоновку матрицы. Если поток ДОЛЖЕН иметь целую строку в памяти, чтобы обработать его, я боюсь, что вы не можете использовать все процессоры, так как процесс начнет перебивать, т. Е. Выбрасывать из памяти некоторое подмножество матрицы и перезагружать другое необходимое подмножество. Это немного менее опасно, чем полная замена, так как матрица никогда не изменяется, поэтому содержимое страниц не нужно записывать в файл подкачки перед тем, как выгнать. Но это все еще сильно ухудшает производительность.

Кроме того, выполнение ввода-вывода с произвольным доступом из нескольких потоков - плохая идея, и это то, что вы в конечном итоге будете делать, если используете mmap (). У вас есть (предположительно) только один диск, и параллельный ввод-вывод сделает его медленнее. Так что mmap () может не иметь смысла, и вы можете добиться лучшей производительности ввода-вывода, последовательно считывая данные в оперативную память.

Обратите внимание, что 40 ГБ - это примерно 10,5 миллионов страниц размером 4096 байт. Выполняя mmap (), вы в худшем случае замедляете вычисления из-за того, что ищет много жестких дисков. При 8 мс на запрос (взято из Википедии) вы потратите 83666 секунд, т. Е. Почти целый день!

Answer 3

Если вы могли бы поместить все это в основную память, тогда да: память отображает все это, и не имеет значения, майор столбца или мажор строки.Тем не менее, на 40+ Гб, я уверен, что он слишком велик для основной памяти.В этом случае:

1. Нет, не отображайте все это!По крайней мере, не ожидайте, что память будет работать как обычная память, если вы все отобразите.Ваша программа будет работать вечно, если вы не справитесь с проблемами ввода / вывода должным образом.
2. Проблема многопоточного доступа решается, если вы храните ее в мажорной строке (похоже, у вас нет-потоковый столбец пишет).
3. Вы должны расположить его построчно, предполагая, что каждая ячейка записана один раз, а затем прочитано много раз.
4. Да, я думаю, что это поможет пометить матрицутолько для чтения после написания, но исключительно как способ предотвращения ошибок (случайных записей).Это не повлияет на производительность.
5. Нет, никакие умные возможности чтения с ядра не помогут решить ваши проблемы с производительностью.Вам нужно решить это на уровне алгоритма.

Я думаю, что у вас будут проблемы с производительностью при наивной реализации.Либо компьютер с thrash во время записи (если вы храните его в мажоре строк), либо он будет зависать во время запросов (если вы храните его в столбце major).Последнее, вероятно, хуже, но это проблема в обоих направлениях.

Правильное решение - использовать промежуточное представление, которое не является ни основным, ни основным, а «большими квадратами».Возьмите первые 50 000 столбцов и сохраните их в файле с отображением в памяти (фаза 1).Неважно, является ли это основной столбец или основной ряд, так как он будет исключительно резидентным.Затем возьмите каждую строку и запишите ее в окончательный файл отображения основной строки (фаза 2).Затем повторите цикл для следующих 50 000 столбцов и т. Д.