Pregel Анцелевич Антон

Река Преголя

Авторы Grzegorz Malewicz Matthew H. Austern Aart J. C. Bik James C. Dehnert Ilan Horn Naty Leiser Grzegorz Czajkowski

Распараллеливание графа Структура вычислений не известна а- приори Трудно локализовать вычисления Всем нужна структура графа

Существующие подходы По мере поступления MapReduce – ужасно функциональный Sawzall, PigLatin – только данные Не параллелить – BGL (C++), LEDA (С++), NetworkX (Python) и пр. Parallel BGL и CGMgraph – не отказоустойчивы.

Valiant's Bulk Synchronous Parallel Компоненты Главный – «роутер» Интервалы, супершаги

Поиск максимального значения 3621

6626

6666

6666

class Vertex template class Vertex const VertexValue& GetValue(); VertexValue* MutableValue(); OutEdgeIterator GetOutEdgeIterator(); void SendMessageTo(const string& dest_vertex, const MessageValue& message); void VoteToHalt();

Изменение структуры графа частичное упорядочение удаление рёбер, удаление вершин, добавление вершин, добавление рёбер обработчики.

Инфраструктура Google clusters GFS BigTable

Работа всей системы Master, workers Разбиение графа Раздача кусочков графа Мастер: «Run, workers, run» + супершаг Воркеры: «Да, о, повелитель!» Мастер: «Приберегите свои кусочки»

Отказоустойчивость Точки восстановления Confined recovery

PageRank Sergey Brin и Lawrence Page PR(A) = (1-d)+ d(PR(T1)/C(T1)+... +PR(Tn)/C(Tn)) Итеративный алгоритм: PR(A)/n=(0.15/n *sum)/(C(A))

PageRank – Код на C++ class PageRankVertex : public Vertex { public: virtual void Compute(MessageIterator* msgs) { if (superstep() >= 1) { double sum = 0; for (; !msgs->Done(); msgs->Next()) sum += msgs->Value(); *MutableValue() = 0.15 / NumVertices() * sum; } if (superstep() < 30) { const int64 n = GetOutEdgeIterator().size(); SendMessageToAllNeighbors(GetValue() / n); } else { VoteToHalt(); } };

SSSP class ShortestPathVertex : public Vertex { void Compute(MessageIterator* msgs) { int mind = IsSource(vertex_id()) ? 0 : INF; for (; !msgs->Done(); msgs->Next()) mind = min(mindist, msgs->Value()); if (mindist < GetValue()) { *MutableValue() = mind; OutEdgeIterator it = GetOutEdgeIterator(); for (; !it.Done(); it.Next()) SendMes(it.Target(), mind + it.GetV ()); } VoteToHalt(); } };

SSSP Combiner class MinIntCombiner : public Combiner { virtual void Combine(MessageIterator* msgs) { int mindist = INF; for (; !msgs->Done(); msgs->Next()) mindist = min(mindist, msgs->V()); Output("combined_source", mindist); } };

Максимальное паросочетание High Speed Switch Scheduling for Local Area Networks, 1993 Thomas E. Anderson, Susan S. Owicki, James B. Saxe, and Charles P. Thacker Этапы: 0,1,2,3 – номер супершага mod 4

Тестирование Бинарные деревья (1 млрд вершин)

Тестирование Бинарные деревья (800 workers)

Тестирование Графы с логнормальным распределением полустепеней исхода

Что можно сделать? Ослабить синхронность Перебросить данные на диски Уменьшить количество сообщений

Спасибо за внимание

GoogleGoogleGoogleGoogle 80%: MapReduce – индексирование, Google News, Google Trends, Google Maps, Google Translate =( 20%: Видимо, Pregel – всякое разное, что именно – неизвестно =(