решено ..... Когда у нас есть профиль обеспечения, тогда нам не нужна наша учетная запись разработчика, поскольку у нас есть сертификаты и профиль обеспечения, который дает нам мост учетных записей разработчика и разрешения устройств. Подписывание без проверки автоматически управляет подписью [ 110]
Я подозреваю, что это тяжело для большинства матриц кроме тех w/специальных структур (например, разреженные матрицы или w/определенные составы блока). Существует слишком много связи между коэффициентами матрицы и собственными значениями.
PageRank использует очень разреженную матрицу специальной формы, и любые заключения из вычисления ее собственных значений почти наверняка не расширяются на общие матрицы. (редактирование: вот другая ссылка, которая выглядит интересной),
ПРЕАМБУЛА:
Учитывая правильную конфискацию имущества данных, можно было достигнуть результатов параллельных вычислений без полного набора данных на каждой машине.
Возьмите, например, следующий цикл:
for (int i = 0; i < m[].length; i++)
{
for (int j = 0; j < m[i].length; j++)
{
m[i][j]++;
}
}
И, учитывая матрицу следующего расположения:
j=0 j=1 j=2
i=0 [ ] [ ] [ ]
i=1 [ ] [ ] [ ]
i=2 [ ] [ ] [ ]
Параллельные конструкции существуют таким образом, что столбец J может быть отправлен на каждый компьютер, и отдельные столбцы вычисляются параллельно. Трудная часть распараллеливания прибывает, когда у Вас есть циклы, которые содержат зависимости.
for (int i = 0; i < m[].length; i++)
{
for (int j = 0; j < m[i].length; j++)
{
//For obvious reasons, matrix index verification code removed
m[i][j] = m[i/2][j] + m[i][j+7];
}
}
Очевидно, цикл как тот выше становится чрезвычайно проблематичным (заметьте матричные индексаторы.), Но методы действительно существуют для того, чтобы развернуть эти типы циклов и создать эффективные параллельные алгоритмы.
ОТВЕТ:
Возможно, что Google разработал решение вычислить собственное значение, не поддерживая копию матрицы на всех ведомых компьютерах. - или Они использовали что-то как Монте-Карло или некоторый другой Алгоритм аппроксимации для разработки "достаточно близко" вычисления.
На самом деле я сказал бы даже, что Google перейдет в максимально большой из длин сделать любое вычисление требуемым для их алгоритма PageRank максимально эффективный. Когда Вы - беговые дорожки, такие как они, и это (заметьте кабель Ethernet), Вы не можете передавать большие наборы данных (100 с концертов), потому что это невозможно, учитывая их аппаратные ограничения товарных плат NIC.
После этих слов Google способен удивлять сообщество программиста, и их реализация могла совершенно отличаться.
ЗАКЛЮЧИТЕЛЬНАЯ ЧАСТЬ СООБЩЕНИЯ:
Некоторые хорошие ресурсы для параллельных вычислений включали бы OpenMP и MPI. Обе параллельных реализации приближаются к параллельным вычислениям от совсем других парадигм, некоторые из которых происходят от реализации машины (кластер по сравнению с распределенными вычислениями.)
PageRank решает проблему доминантного собственного вектора, итеративно находя стационарное состояние дискретного потока в сети.
Если матрица A NxM описывает вес канала (количество потока) от узла n до узел m, затем
p_{n+1} = A . p_{n}
В пределе, когда p сходится к стационарному состоянию (p_n + 1 = p_n), это проблема собственных векторов с собственным значением 1.
Алгоритм PageRank не требует удержания матрицы в памяти, но неэффективно на плотных (не разреженных) матрицах. Для плотных матриц MapReduce является неправильным решением - вам нужна локальность и широкий обмен между узлами - и вам следует вместо этого взглянуть на LaPACK, MPI и друзей.
Вы можете увидеть работающую реализацию pagerank в библиотеке wukong (потоковая передача hadoop для ruby) или в подмодуле Heranrix Pagerank .
Я могу ответить мне теперь. Алгоритм PageRank использует в своих интересах разреженную матрицу, где это должно сходиться в собственном значении с несколькими, самоумножаются. Таким образом, в практике PageRank, Отобразить/Уменьшить процедура действительна. Можно выполнить, умножение матриц в процедуре Карты и формируются, разреженная матрица в Уменьшают процедуру. Но для общего матричного открытия собственного значения, это - все еще хитрая проблема.
В проекте apache hama есть интересная реализация алгоритма собственных значений Якоби. Он работает на hadoop. Обратите внимание, что вращение происходит при сканировании матрицы, а не при уменьшении карты.