https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?action=history&feed=atom&title=Bellman-Ford%2C_scalability 2026-10-22T18:05:07Z История изменений этой страницы в вики MediaWiki 1.43.5 https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Bellman-Ford,_scalability&diff=28932&oldid=prev 2022-07-04T13:22:11Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 13:22, 4 июля 2022</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l4">Строка 4:</td> <td colspan="2" class="diff-lineno">Строка 4:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>= Ссылки =</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>= Ссылки =</div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Для проведения экспериментов использовалась реализация алгоритма Беллмана-Форда, реализованная для CPU.</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>= Локальность данных и вычислений =</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>= Локальность данных и вычислений =</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l29">Строка 29:</td> <td colspan="2" class="diff-lineno">Строка 31:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>= Динамические характеристики и эффективность реализации алгоритма =</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>= Динамические характеристики и эффективность реализации алгоритма =</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">Для проведения экспериментов использовалась реализация алгоритма Беллмана-Форда, реализованная для CPU.  </del>Все результаты получены на суперкомпьютере «Ломоносов-2». Использовались процессоры Intel Xeon E5-2697v3, задача решалась для графа большого размера на одном узле.  </div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Все результаты получены на суперкомпьютере «Ломоносов-2». Использовались процессоры Intel Xeon E5-2697v3, задача решалась для графа большого размера на одном узле.  </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>На рисунках показана эффективность реализации алгоритма Беллмана-Форда, запуск проводился на 1 узле для графа 2^27, выполнялась 1 итерация.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>На рисунках показана эффективность реализации алгоритма Беллмана-Форда, запуск проводился на 1 узле для графа 2^27, выполнялась 1 итерация.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[file:Bellman-Ford cpu.png|thumb|center|700px|Рисунок 2. График загрузки CPU при выполнении алгоритма Беллмана-Форда]]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[file:Bellman-Ford cpu.png|thumb|center|700px|Рисунок 2. График загрузки CPU при выполнении алгоритма Беллмана-Форда]]</div></td></tr> </table>

ASA https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Bellman-Ford,_scalability&diff=28931&oldid=prev 2022-07-04T13:20:46Z

<p>Новая страница: «{{level-i}} Основные авторы описания: . = Ссылки = = Локальность данных и вычислений = == Локаль...»</p> <p><b>Новая страница</b></p><div>{{level-i}}<br /> <br /> Основные авторы описания: .<br /> <br /> = Ссылки =<br /> <br /> = Локальность данных и вычислений =<br /> == Локальность реализации алгоритма ==<br /> === Структура обращений в память и качественная оценка локальности ===<br /> === Количественная оценка локальности ===<br /> = Масштабируемость алгоритма и его реализации =<br /> == Масштабируемость алгоритма ==<br /> <br /> Алгоритм обладает значительным потенциалом масштабируемости, так как каждое ребро обрабатывается независимо и можно поручить каждому вычислительному процессу свою часть рёбер графа. Узким местом является доступ к разделяемому всеми процессами массиву расстояний. Алгоритм позволяет ослабить требования к синхронизации данных этого массива между процессами (когда один процесс может не сразу увидеть новое значение расстояния, записанное другим процессом), за счёт, может быть, большего количества глобальных итераций.<br /> <br /> == Масштабируемость реализации алгоритма ==<br /> <br /> Проведём исследование масштабируемости параллельной реализации алгоритма Беллмана-Форда согласно [[Scalability methodology|методике]]. Исследование проводилось на суперкомпьютере &quot;Ломоносов-2 [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].<br /> <br /> Набор и границы значений изменяемых [[Глоссарий#Параметры запуска|параметров запуска]] реализации алгоритма: <br /> <br /> * число процессоров [1 : 28] с шагом 1;<br /> * размер графа [2^20 : 2^27].<br /> <br /> Производительность определена как TEPS (от англ. Traversed Edges Per Second), то есть число ребер графа, который алгоритм обрабатывает в секунду. С помощью данной метрики можно сравнивать производительность для различных размеров графа, оценивая, насколько понижается эффективность обработки графа при увеличении его размера.<br /> <br /> [[file:Сильная_масштабируемость_вширь_алгоритма_Беллмана-Форда.png|thumb|center|700px|Рисунок 1. Параллельная реализация алгоритма Беллмана-Форда масштабируемость различных версий реализации алгоритма: производительность в зависимости от размера графа]]<br /> <br /> = Динамические характеристики и эффективность реализации алгоритма =<br /> <br /> Для проведения экспериментов использовалась реализация алгоритма Беллмана-Форда, реализованная для CPU. Все результаты получены на суперкомпьютере «Ломоносов-2». Использовались процессоры Intel Xeon E5-2697v3, задача решалась для графа большого размера на одном узле. <br /> На рисунках показана эффективность реализации алгоритма Беллмана-Форда, запуск проводился на 1 узле для графа 2^27, выполнялась 1 итерация.<br /> [[file:Bellman-Ford cpu.png|thumb|center|700px|Рисунок 2. График загрузки CPU при выполнении алгоритма Беллмана-Форда]]<br /> <br /> На графике загрузки процессора видно, что почти все время работы программы не загружены и средний уровень загрузки составляет около 5%. Это достаточно неэффективная картина даже для программ, запущенных с использованием одного ядра в реализации. <br /> <br /> [[file:Bellman-Ford LoadAvg.png|thumb|center|700px|Рисунок 3. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма Беллмана-Форда]]<br /> <br /> На графике числа процессов, ожидающих вхождения в стадию счета (Loadavg), видно, что на протяжении всей работы программы значение этого параметра постоянно на уровне 1. Это указывает на постоянную загрузку аппаратных ресурсов не более чем 1 процессом, однако это число для узла слишком мало, что может указывать на не очень рациональное использование ресурсов.<br /> <br /> [[file:Bellman-Ford L1.png|thumb|center|700px|Рисунок 4. График кэш-промахов L1 в секунду при работе алгоритма Беллмана-Форда]]<br /> <br /> На графике кэш-промахов первого уровня видно, что число промахов очень высокое и находится на уровне 140 млн/сек. Это очень высокий показатель, показывающий потенциальную причину неэффективности.<br /> <br /> [[file:Bellman-Ford L2.png|thumb|center|700px|Рисунок 5. График кэш-промахов L2 в секунду при работе алгоритма Беллмана-Форда]]<br /> <br /> На графике кэш-промахов второго уровня видно, что число таких промахов тоже крайне высокое и находится на уровне 140 млн/сек, что указывает на крайне неэффективную работу с памятью.<br /> <br /> [[file:Bellman-Ford-L3.png|thumb|center|700px|Рисунок 6. График кэш-промахов L3 в секунду при работе алгоритма Беллмана-Форда]]<br /> <br /> На графике кэш-промахов последнего уровня видно, что число промахов тоже достаточно большое и составляет около 30 млн/сек по всем узлам. Это указывает на то, что задача очень плохо укладывается в кэш-память, и программа постоянно работает с оперативной памятью, что объясняется очень большим размером использованного графа.<br /> <br /> [[file:Bellman-Ford Inf Data.png|thumb|center|700px|Рисунок 7. График скорости передачи по сети Infiniband в байт/сек при работе алгоритма Беллмана-Форда]]<br /> <br /> На графике скорости передачи данных по сети Infiniband наблюдается достаточно высокая интенсивность использования сети на первом этапе. Это объясняется программной логикой, которая предполагает чтение графа из файла с диска, коммуникации с которым происходят на Ломоносов-2 через выделенную для этих задач сеть Infiniband.<br /> <br /> [[file:Bellman-Ford Inf Pckts.png|thumb|center|700px|Рисунок 8. График скорости передачи по сети Infiniband в пакетах/сек при работе алгоритма Беллмана-Форда]]<br /> <br /> На графике скорости передачи данных в пакетах в секунду наблюдается аналогичная картина очень высокой интенсивности на первом этапе выполнения задачи. Далее сеть почти не используется.<br /> <br /> В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала стабильно интенсивно, однако очень неэффективно использовала память из-за очень большого размера графа.<br /> <br /> = Результаты прогонов =<br /> <br /> [[Категория:Статьи в работе]]<br /> <br /> [[En:Bellman-Ford, scalability]]</div>

ASA