https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?action=history&feed=atom&title=Floyd-Warshall%2C_scalability 2026-10-22T17:27:03Z История изменений этой страницы в вики MediaWiki 1.43.5 https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Floyd-Warshall,_scalability&diff=28945&oldid=prev 2022-07-05T07:49:37Z

<p>Новая страница: «{{level-i}} Основные авторы описания: Екатерина Шевченко = Ссылки = = Локальность данных и вы...»</p> <p><b>Новая страница</b></p><div>{{level-i}}<br /> <br /> Основные авторы описания: Екатерина Шевченко<br /> <br /> = Ссылки =<br /> <br /> = Локальность данных и вычислений =<br /> == Локальность реализации алгоритма ==<br /> === Структура обращений в память и качественная оценка локальности ===<br /> === Количественная оценка локальности ===<br /> = Масштабируемость алгоритма и его реализации =<br /> == Масштабируемость алгоритма ==<br /> <br /> Возможность обрабатывать фрагменты независимо означает хорошую масштабируемость алгоритма. Сдерживающие факторы: &lt;br&gt;<br /> 1)Пропускная способность памяти при чтении данных графа.&lt;br&gt;<br /> 2)Соперничество потоков при выполнении атомарных операций с памятью. &lt;br&gt;<br /> 3)Синхронизация после каждого подшага алгоритма. &lt;br&gt;<br /> <br /> Алгоритм Флойда-Уоршелла обладает большим потенциалом масштабируемости, так как вычисление кратчайших путей можно распределить между независимыми процессами вплоть до вычисления каждым отдельным процессом одного элемента матрицы смежности.<br /> <br /> == Масштабируемость реализации алгоритма ==<br /> <br /> Проведём исследование масштабируемости параллельной реализации алгоритма. Работа выполнена с использованием оборудования Центра коллективного пользования сверхвысокопроизводительными вычислительными ресурсами МГУ имени М.В. Ломоносова.<br /> Сильная масштабируемость показывает, как меняется время решения задачи с увеличением количества процессоров (или вычислительных узлов) при неизменном общем объёме задачи.<br /> <br /> [[file: Pic1.jpg|thumb|center|700px|Сравнение времени параллельной работы алгоритма Флойда-Уоршелла в зависимости от количества процессоров.]]<br /> <br /> [[file: Pic3.jpg|thumb|center|700px|Ускорение параллельного алгоритма Флойда-Уоршелла с ростом числа процессоров.]]<br /> <br /> Как видно из представленных графиков параллельный алгоритм сильно масштабируем.<br /> <br /> = Динамические характеристики и эффективность реализации алгоритма =<br /> = Результаты прогонов =<br /> <br /> [[Категория:Статьи в работе]]<br /> <br /> [[En:Floyd-Warshall, scalability]]</div>

ASA