https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?action=history&feed=atom&title=Tarjan-Vishkin_biconnected_components%2C_scalability 2026-10-22T15:12:41Z История изменений этой страницы в вики MediaWiki 1.43.5 https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Tarjan-Vishkin_biconnected_components,_scalability&diff=28998&oldid=prev 2022-07-06T12:43:43Z

<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;">Версия от 12:43, 6 июля 2022</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l34">Строка 34:</td> <td colspan="2" class="diff-lineno">Строка 34:</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>[[En:<del style="font-weight: bold; text-decoration: none;">The computational core of the Graph500 benchmark on MPI</del>]]</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>[[En:<ins style="font-weight: bold; text-decoration: none;">Tarjan-Vishkin biconnected components, scalability</ins>]]</div></td></tr> </table>

ASA https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Tarjan-Vishkin_biconnected_components,_scalability&diff=28997&oldid=prev 2022-07-06T12:43:04Z

<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 /> = Локальность данных и вычислений =<br /> == Локальность реализации алгоритма ==<br /> === Структура обращений в память и качественная оценка локальности ===<br /> === Количественная оценка локальности ===<br /> = Масштабируемость алгоритма и его реализации =<br /> == Масштабируемость алгоритма ==<br /> == Масштабируемость реализации алгоритма ==<br /> <br /> Проведём исследование масштабируемости параллельной реализации алгоритма Тарьяна-Вишкина согласно [[Scalability methodology|методике]]. Исследование проводилось на суперкомпьютере &quot;Ломоносов-2&quot; [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].<br /> <br /> Набор и границы значений изменяемых [[Глоссарий#Параметры запуска|параметров запуска]] реализации алгоритма: <br /> <br /> <br /> * размер графа [2^18 : 2^26].<br /> <br /> Проведем отдельные исследования масштабируемости вширь реализации алгоритма Тарьяна-Вишкина.<br /> <br /> Основной характеристикой для сравнения было выбрано время выполнения, так как производительность (определения как TEPS то есть число ребер графа, которое алгоритм обрабатывает в секунду) для данной операции не отражает реальную эффективность обработки.<br /> <br /> Анализируя время выполнения можно оценить, насколько понижается эффективность обработки графа при увеличении его размера (данные перестают помещаться в кэш, в память GPU, узла и т.д.). <br /> <br /> <br /> [[file:Tarjan vishkin scaling wide.png|thumb|center|700px|Рисунок 1. Параллельная реализация алгоритма Тарьяна-Вишкина масштабируемость вширь: производительность в зависимости от размера графа]]<br /> <br /> = Динамические характеристики и эффективность реализации алгоритма =<br /> = Результаты прогонов =<br /> <br /> [[Категория:Статьи в работе]]<br /> <br /> [[En:The computational core of the Graph500 benchmark on MPI]]</div>

ASA