Как на карте памяти огромная матрица?

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

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

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

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

Ответы

Ответ 1

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

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

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

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

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

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

Ответ 2

  • Возможно, см. ниже.
  • Размер общего рабочего набора всех потоков не должен превышать доступную ОЗУ, в противном случае программа будет работать со скоростью улитки из-за свопинга.
  • Макет должен соответствовать шаблонам доступа, если соблюдается условие 2.
  • Что вы подразумеваете под "mark as read only"?
  • Измерьте это.

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

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

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

Ответ 3

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

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

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

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