Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 10 лет назад пользователемsyminar.ru
1 Pregel Анцелевич Антон
2 Река Преголя
3 Авторы Grzegorz Malewicz Matthew H. Austern Aart J. C. Bik James C. Dehnert Ilan Horn Naty Leiser Grzegorz Czajkowski
4 Распараллеливание графа Структура вычислений не известна а- приори Трудно локализовать вычисления Всем нужна структура графа
5 Существующие подходы По мере поступления MapReduce – ужасно функциональный Sawzall, PigLatin – только данные Не параллелить – BGL (C++), LEDA (С++), NetworkX (Python) и пр. Parallel BGL и CGMgraph – не отказоустойчивы.
6 Valiant's Bulk Synchronous Parallel Компоненты Главный – «роутер» Интервалы, супершаги
7 Поиск максимального значения 3621
8 6626
9 6666
10 6666
11 class Vertex template class Vertex const VertexValue& GetValue(); VertexValue* MutableValue(); OutEdgeIterator GetOutEdgeIterator(); void SendMessageTo(const string& dest_vertex, const MessageValue& message); void VoteToHalt();
12 Изменение структуры графа частичное упорядочение удаление рёбер, удаление вершин, добавление вершин, добавление рёбер обработчики.
13 Инфраструктура Google clusters GFS BigTable
14 Работа всей системы Master, workers Разбиение графа Раздача кусочков графа Мастер: «Run, workers, run» + супершаг Воркеры: «Да, о, повелитель!» Мастер: «Приберегите свои кусочки»
15 Отказоустойчивость Точки восстановления Confined recovery
16 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))
17 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(); } };
18 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(); } };
19 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); } };
20 Максимальное паросочетание 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
21 Тестирование Бинарные деревья (1 млрд вершин)
22 Тестирование Бинарные деревья (800 workers)
23 Тестирование Графы с логнормальным распределением полустепеней исхода
24 Что можно сделать? Ослабить синхронность Перебросить данные на диски Уменьшить количество сообщений
25 Спасибо за внимание
26 GoogleGoogleGoogleGoogle 80%: MapReduce – индексирование, Google News, Google Trends, Google Maps, Google Translate =( 20%: Видимо, Pregel – всякое разное, что именно – неизвестно =(
Еще похожие презентации в нашем архиве:
© 2024 MyShared Inc.
All rights reserved.