https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?action=history&feed=atom&title=Boruvka%27s%2C_scalability 2026-10-23T05:58:05Z История изменений этой страницы в вики MediaWiki 1.43.5 https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Boruvka%27s,_scalability&diff=28954&oldid=prev 2022-07-05T10:31:40Z

<p>Новая страница: «{{level-i}} Основные авторы описания: <a href="/ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Elijah" title="Участник:Elijah">И.В.Афанасьев</a> = Ссылки = Для проведения...»</p> <p><b>Новая страница</b></p><div>{{level-i}}<br /> <br /> Основные авторы описания: [[Участник:Elijah|И.В.Афанасьев]]<br /> <br /> = Ссылки =<br /> <br /> Для проведения экспериментов использовалась реализация алгоритма Борувки, реализованная для CPU.<br /> <br /> = Локальность данных и вычислений =<br /> == Локальность реализации алгоритма ==<br /> === Структура обращений в память и качественная оценка локальности ===<br /> === Количественная оценка локальности ===<br /> = Масштабируемость алгоритма и его реализации =<br /> == Масштабируемость алгоритма ==<br /> <br /> Возможность обрабатывать фрагменты независимо означает хорошую масштабируемость алгоритма. Сдерживающими факторами являются<br /> # пропускная способность памяти при чтении данных графа<br /> # соперничество потоков при выполнении атомарных операций с памятью<br /> # барьерная синхронизация после каждого подшага алгоритма.<br /> <br /> == Масштабируемость реализации алгоритма ==<br /> <br /> Проведём исследование масштабируемости параллельной реализации алгоритма Борувки согласно [[Scalability methodology|методике]]. Исследование проводилось на суперкомпьютере &quot;Ломоносов-2&quot; [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].<br /> <br /> Набор и границы значений изменяемых [[Глоссарий#Параметры запуска|параметров запуска]] реализации алгоритма: <br /> <br /> * число процессоров [1 : 28] с шагом 1;<br /> * размер графа [2^20 : 2^27].<br /> <br /> Проведем отдельные исследования сильной масштабируемости и масштабируемости вширь реализации алгоритма Борувки.<br /> <br /> Производительность определена как TEPS (от англ. Traversed Edges Per Second), то есть число ребер графа, который алгоритм обрабатывает в секунду. С помощью данной метрики можно сравнивать производительность для различных размеров графа, оценивая, насколько понижается эффективность обработки графа при увеличении его размера<br /> <br /> [[file:MST scaling strong.png|thumb|center|700px|Рисунок 1. Параллельная реализация алгоритма Борувки масштабируемость CPU версии: производительность в зависимости от числа запущенных CPU-потоков.]]<br /> <br /> [[file:MST scaling wide.png|thumb|center|700px|Рисунок 2. Параллельная реализация алгоритма Борувки масштабируемость различных версий реализации алгоритма: производительность в зависимости от размера графа]]<br /> <br /> = Динамические характеристики и эффективность реализации алгоритма =<br /> <br /> Все результаты получены на суперкомпьютере «Ломоносов-2». Использовались процессоры Intel Xeon E5-2697v3, задача решалась для графа большого размера на одном узле. <br /> На рисунках показана эффективность реализации алгоритма Борувки, запуск проводился на 1 узле для графа 2^27, выполнялась 1 итерация.<br /> [[file:Boruvka cpu.png|thumb|center|700px|Рисунок 3. График загрузки CPU при выполнении алгоритма Борувки]]<br /> <br /> На графике загрузки процессора видно, что почти все время работы программы не загружены и средний уровень загрузки составляет около 10%. Это нормальная картина для программ, запущенных c использованием одного ядра в реализации. <br /> <br /> [[file:Boruvka Loadavg.png|thumb|center|700px|Рисунок 4. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма Борувки]]<br /> <br /> На графике числа процессов, ожидающих вхождения в стадию счета (Loadavg), видно, что на протяжении всей работы программы значение этого параметра постоянно на уровне 2. Это указывает на постоянную загрузку аппаратных ресурсов не более чем 2 процессами, однако их число для узла слишком мало, что с одной стороны может указывать на не очень рациональное использование ресурсов.<br /> <br /> [[file:Boruvka L1.png|thumb|center|700px|Рисунок 5. График кэш-промахов L1 в секунду при работе алгоритма Борувки]]<br /> <br /> На графике кэш-промахов первого уровня видно, что число промахов очень высокое и находится на уровне 40 млн/сек . Интересен факт увеличения числа промахов к концу итерации до уровня в 70 млн/сек.<br /> <br /> [[file:Boruvka L2.png|thumb|center|700px|Рисунок 6. График кэш-промахов L1 в секунду при работе алгоритма Борувки]]<br /> <br /> На графике кэш-промахов второго уровня видно, что число промахов тоже достаточно высокое и находится на уровне 30 млн/сек . На графике промахов второго уровня факт увеличения числа промахов к концу итерации проявляется более явно и увеличивается до значения в 50млн/сек.<br /> <br /> [[file:Boruvka L3.png|thumb|center|700px|Рисунок 7. График кэш-промахов L3 в секунду при работе алгоритма Борувки]]<br /> <br /> На графике кэш-промахов последнего уровня видно, что число промахов тоже достаточно большое и составляет около 30 млн/сек по всем узлам. Это указывает на то, что задача очень плохо укладывается в кэш-память, и программа постоянно работает с оперативной памятью, что объясняется очень большим размером использованного графа.<br /> <br /> [[file:Boruvka Inf data.png|thumb|center|700px|Рисунок 8. График скорости передачи по сети Infiniband в байт/сек при работе алгоритма Борувки]]<br /> <br /> На графике скорости передачи данных по сети Infiniband наблюдается достаточно высокая интенсивность использования сети на первом этапе. Это объясняется программной логикой, которая предполагает чтение графа из файла с диска, коммуникации с которым происходят на Ломоносов-2 через выделенную для этих задач сеть Infiniband.<br /> <br /> [[file:Boruvka inf pckts.png|thumb|center|700px|Рисунок 9. График скорости передачи по сети Infiniband в пакетах/сек при работе алгоритма Борувки]]<br /> <br /> На графике скорости передачи данных в пакетах в секунду наблюдается аналогичная картина очень высокой интенсивности на первом этапе выполнения задачи. Далее сеть почти не используется.<br /> <br /> В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала стабильно интенсивно, однако очень неэффективно использовала память из-за очень большого размера графа.<br /> <br /> = Результаты прогонов =<br /> <br /> [[Категория:Статьи в работе]]<br /> <br /> [[En:Boruvka&#039;s, scalability]]</div>

ASA