ASA: Новая страница: «{{level-i}} Основные авторы описания: И.В.Афанасьев = Ссылки = Основной фрагме...»

2022-07-05T10:45:29Z

Новая страница: «{{level-i}} Основные авторы описания: И.В.Афанасьев = Ссылки = Основной фрагме...»

Новая страница

{{level-i}}

Основные авторы описания: [[Участник:Elijah|И.В.Афанасьев]]

= Ссылки =

Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [https://gitlab.srcc.msu.ru/shvets.pavel.srcc/locality/-/blob/master/benchmarks/boruvka/boruvka.h здесь] (функция Kernel).

= Локальность данных и вычислений =
== Локальность реализации алгоритма ==
=== Структура обращений в память и качественная оценка локальности ===

[[file:boruvka_1.png|thumb|center|700px|Рисунок 1. Алгоритм Борувки. Общий профиль обращений в память]]

На рис. 1 представлен профиль обращений в память для реализации алгоритма Борувки. Этот алгоритм, как и большинство графовых алгоритмов, обладает нерегулярной структурой. Сразу нужно отметить, что локальность реализаций таких алгоритмов во многом зависит от структуры входного графа и может существенно меняться. В данном случае мы рассматриваем лишь один из возможных вариантов.

Можно увидеть, что общий профиль состоит из 4 достаточно схожих этапов (разделены на рис. 1 вертикальными линиями). Однако поскольку этот профиль не обладает регулярной структурой, лучше рассмотреть все этапы.

Начнем с изучения верхней части профиля (фрагмент 1 на рис. 1), которая показана на рис. 2. На каждом этапе большую часть обращений занимает последовательный перебор всех элементов данного фрагмента (выделен на рис. 2 желтым). Остальные обращения на разных этапах устроены по-разному. Если на первом этапе эти обращения разбросаны достаточно далеко друг от друга, что приводит к низкой пространственной и временной локальности, то на последнем этапе почти все обращения (не считая последовательного перебора) выполняются к одному и тому же элементу, что, естественно, характеризуется очень высокой локальностью. Подобное строение всего фрагмента приводит, скорее всего, к средним значениям и по пространственной, и по временной локальности.

[[file:boruvka_2.png|thumb|center|700px|Рисунок 2. Профиль обращений, фрагмент 1]]

Далее перейдем к изучению фрагмента 2 (рис. 3). Здесь можно увидеть, что строение каждого из 4 этапов отличается достаточно сильно. Как и в случае с фрагментом 1, каждый следующий этап обладает более высокой локальностью, однако здесь это заметно сильнее. При этом отметим, что данный фрагмент задействует всего около 60 элементов, а обращений к ним выполняется достаточно много, так что локальность в данном случае будет высока.

[[file:boruvka_3.png|thumb|center|700px|Рисунок 3. Профиль обращений, фрагмент 2]]

В целом похожая картинка наблюдается и во фрагменте 3. На рис. 4 видны 4 этапа со схожей структурой, и также задействовано около 60 элементов, что позволяет говорить о высокой локальности данного фрагмента.

[[file:boruvka_4.png|thumb|center|700px|Рисунок 4. Профиль обращений, фрагмент 3]]

Отдельное рассмотрение фрагмента 4 (рис. 5) позволяет увидеть, что локальность здесь определяется 4 последовательными переборами всех элементов данного фрагмента. Эти переборы обладают стандартной структурой – шаг по памяти 1, только 1 обращение к каждому элементу; небольшое искривление данных переборов вызвано нерегулярной активностью в других фрагментах, которая приводит к искажению визуального представления профиля. Подобный набор обращений обладает высокой пространственной, но низкой временной локальностью.

[[file:boruvka_5.png|thumb|center|500px|Рисунок 5. Профиль обращений, фрагмент 4]]

Таким образом, фрагменты 2 и 3 характеризуются высокой локальностью, другие 2 фрагмента – средней локальностью. А поскольку большая часть обращений приходится именно на фрагменты 2 и 3, можно предположить, что общая локальность должна быть достаточно высока.

=== Количественная оценка локальности ===

Оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.

На рисунке 6 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что производительность работы с памятью в данном случае достаточно неплоха – значение daps сравнимо, например, со значением для реализации метода Холецкого. Однако это значение заметно ниже самых производительных реализаций алгоритмов (например, теста Linpack), что в целом неудивительно в случае графовых алгоритмов, традиционно неэффективно работающих с памятью.

[[file:boruvka_daps.png|thumb|center|700px|Рисунок 6. Сравнение значений оценки daps]]

= Масштабируемость алгоритма и его реализации =
== Масштабируемость алгоритма ==
== Масштабируемость реализации алгоритма ==
= Динамические характеристики и эффективность реализации алгоритма =
= Результаты прогонов =

[[Категория:Статьи в работе]]

[[En:Boruvka's, locality]]

Boruvka's, locality - История изменений

ASA: Новая страница: «{{level-i}} Основные авторы описания: И.В.Афанасьев = Ссылки = Основной фрагме...»