Блог

Главная - Вопросы по программированию - Распараллелить Solve() для Ax = b?

Распараллелить Solve() для Ax = b?

#r #parallel-processing #sparse-matrix

#r #параллельная обработка #разреженная матрица

Вопрос:

Пересылается с STATS.se поскольку эта проблема может охватывать оба STATs.se/SO https://stats.stackexchange.com/questions/17712/parallelize-solve-for-ax-b

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

Использование функции solve() работает для моей проблемы Ax = b, но это занимает очень много времени. Несколько дней.

Я заметил, что http://cran.r-project.org/web/packages/RScaLAPACK/RScaLAPACK.pdf похоже, есть функция, которая может распараллеливать функцию solve, однако установка новых пакетов на этот конкретный сервер может занять несколько недель.

На сервере уже установлен пакет snow.

Итак

  1. Есть ли способ использовать snow для распараллеливания этой операции?
  2. Если нет, существуют ли другие способы ускорить этот тип операции?
  3. Существуют ли другие пакеты, подобные RScaLAPACK? Мой поиск в RScaLAPACK, похоже, показал, что у людей было много проблем с этим.

Спасибо.

[РЕДАКТИРОВАТЬ] — Дополнительные сведения

Размер матриц составляет около 370 000 x 370 000. Я использую его для решения проблемы альфа-централизации, http://en.wikipedia.org/wiki/Alpha_centrality . Изначально я использовал функцию альфа-централизации в пакете igraph, но это привело бы к сбою R.

Подробнее

  • Это на одной машине с 12 ядрами и 96 гигабайтами памяти (я полагаю)
  • Это ориентированный граф в соответствии с отношениями цитирования статей.
  • Вычисление номера условия и плотности займет некоторое время. Будет публиковаться по мере поступления.
  • Будет пересылается по статистике.SE и добавит ссылку обратно сюда

Комментарии:

1. Можете ли вы опубликовать информацию о масштабе используемой матрицы (или матриц)? В зависимости от масштаба у меня могут быть другие предложения.

2. Только что увидел ваше обновление. Нам нужно обратиться к статистической перспективе по этому вопросу. Кроме того, есть ли у вас оценка нижней границы номера условия (например, eval1 / eval100)? Если вы не абсолютно привержены идее альфа-централизации, может быть полезно опубликовать вопрос о вычислительно целесообразных альтернативах сайту statistics StackExchange.

3. ПРИМЕЧАНИЕ: Если вы опубликуете вопрос, связанный с этим, в статистике. Итак, пожалуйста, добавьте ссылку здесь (и обратную там), чтобы другие могли рассмотреть или рассмотреть одну или другую сторону медали (т. Е. Вычислительную или статистическую).). Кроме того, какую вычислительную систему вы пытаетесь использовать на одной машине с ограниченной оперативной памятью, с большим количеством ядер и большим объемом оперативной памяти или с сеткой?

4. Еще один вопрос: какова плотность матрицы? Кроме того, является ли граф направленным или неориентированным? Если неориентированный, можете ли вы построить гистограмму поддержки для каждой строки? Если указано, можете ли вы сделать то же самое для строк и столбцов? Аналогично, был бы интересен график (индекс, поддержка) для индексов, отсортированных в порядке убывания поддержки. Это может показаться статистическим, но это действительно влияет на то, какой вычислительный метод можно использовать.

Ответ №1:

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

Здесь необходимо решить множество проблем, от инфраструктурных до статистических.

Инфраструктура [Обновлено — также см. Обновление # 2 ниже.]

Что касается распараллеленных линейных решателей, вы можете заменить библиотеку BLAS / LAPACK от R библиотекой, поддерживающей многопоточные вычисления, такой как ATLAS, Goto BLAS, MKL от Intel или ACML от AMD. Лично я использую версию AMD. ATLAS раздражает, потому что количество ядер фиксируется при компиляции, а не во время выполнения. MKL является коммерческим. Goto больше не поддерживается, но часто является самым быстрым, но с небольшим отрывом. Это под лицензией BSD. Вы также можете посмотреть R от Revolution Analytics, который включает, я думаю, библиотеки Intel.

Таким образом, вы можете начать использовать все ядра сразу, с простым изменением серверной части. Это может дать вам ускорение в 12 раз (b / c от количества ядер) или, возможно, намного больше (b / c от лучшей реализации). Если это сократит время до приемлемого диапазона, тогда все готово. 🙂 Но изменение статистических методов может быть еще лучше.

Вы не упомянули объем доступной оперативной памяти (или ее распределение на ядро или компьютер), но Разреженный решатель должен быть достаточно умен в управлении доступом к оперативной памяти и не пытаться пережевывать слишком много данных сразу. Тем не менее, если это на одной машине и если все делается наивно, то вы можете столкнуться с большим количеством подкачки. В этом случае взгляните на такие пакеты, как biglm , bigmemory , ff , и другие. Первое адресует решение линейных уравнений (или, скорее, GLM) в ограниченной памяти, последние два адресуют разделяемую память (т. Е. Отображение памяти и хранилище на основе файлов), что удобно для очень больших объектов. Другие пакеты (например speedglm , и другие) можно найти в представлении задач CRAN для HPC.

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

Еще одно предложение: можете ли вы перейти на EC2 от Amazon? Это недорого, и вы можете управлять своей собственной установкой. Если ничего другого, вы можете создать прототип того, что вам нужно, и перенести его самостоятельно, как только протестируете ускорения. У JD Long есть пакет, segue который, по-видимому, упрощает распределение заданий в эластичной инфраструктуре Amazon MapReduce. Нет необходимости переходить на EC2, если у вас 96 ГБ оперативной памяти и 12 ядер — его распространение может ускорить процесс, но здесь проблема не в этом. Просто получение 100%-ной загрузки на этой машине было бы хорошим улучшением.

Статистический

Далее несколько простых статистических проблем:

  1. ПАКЕТИРОВАНИЕ Вы могли бы рассмотреть возможность выборки подмножеств ваших данных, чтобы соответствовать моделям, а затем пакетировать ваши модели. Это может дать вам ускорение. Это может позволить вам распределить ваши вычисления на столько машин и ядер, сколько у вас есть. Вы можете использовать SNOW вместе с foreach .
  2. РЕГУЛЯРИЗАЦИЯ glmnet поддерживает разреженные матрицы и выполняется очень быстро. Было бы разумно проверить это. Будьте осторожны с плохо обусловленными матрицами и очень маленькими значениями лямбда.
  3. РАНГ Ваши матрицы разрежены: они имеют полный ранг? Если это не так, это может быть частью проблемы, с которой вы столкнулись. Когда матрицы либо единичны, либо очень близки к этому (проверьте свой предполагаемый номер условия или, по крайней мере, посмотрите, как сравниваются ваши 1-е и N-е собственные значения — если происходит резкое падение, у вас проблемы — вы можете проверить eval1 по сравнению с ev2, …, ev10, …). Опять же, если у вас почти сингулярные матрицы, вам нужно вернуться к чему-то вроде glmnet сокращения, чтобы переменные были либо коллинеарными, либо имели очень низкую поддержку.
  4. ОГРАНИЧЕНИЕ Можете ли вы уменьшить пропускную способность вашей матрицы? Если вы можете заблокировать его по диагонали, это здорово, но у вас, вероятно, будут клики и члены нескольких клик. Если вы можете обрезать наиболее плохо связанные элементы, тогда вы сможете оценить их альфа-центральность как верхнюю, ограниченную наименьшим значением в той же клике. В R есть несколько пакетов, которые хороши для такого рода вещей (посмотрите Reverse Cuthill-McKee; или просто посмотрите, как вы преобразуете его в прямоугольники, часто относящиеся к кликам или гораздо меньшим группам). Если у вас есть несколько отключенных компонентов, то, во что бы то ни стало, разделите данные на отдельные матрицы.
  5. АЛЬТЕРНАТИВЫ Вы привязаны к альфа-централизации? Могут быть другие меры, которые монотонно коррелируют (т. Е. Имеют Высокую ранговую корреляцию) с тем же значением, которые можно было бы вычислить дешевле или, по крайней мере, реализовать достаточно эффективно. Если это сработает, то ваши анализы могут выполняться с гораздо меньшими усилиями. У меня есть несколько идей, но SO на самом деле не место для этого обсуждения.

Для получения более статистических перспектив соответствующие вопросы и ответы должны возникать на stats.stackexchange.com , Перекрестная проверка.

Обновление 2: я был слишком быстр в ответе и не рассматривал это с точки зрения долгосрочной перспективы. Если вы планируете проводить исследования таких систем в долгосрочной перспективе, вам следует обратиться к другим решателям, которые могут быть более применимы к вашему типу данных и вычислительной инфраструктуры. Вот очень хороший каталог опций как для решателей, так и для предварительных условий. Похоже, это не включает в себя набор решений IBM «Watson». Хотя установка программного обеспечения может занять недели, вполне возможно, что один из пакетов уже установлен, если у вас хороший администратор HPC.

Кроме того, имейте в виду, что пакеты R могут быть установлены в каталог пользователя — вам не нужно устанавливать пакет в общий каталог. Если вам нужно выполнить что-то от имени пользователя, отличного от вас, вы также можете загрузить пакет в исходное или временное пространство (если вы работаете в пределах всего 1 экземпляра R, но используете несколько ядер, проверьте tempdir ).