Участник:Lizord/Алгоритм Джонса Плассмана - История изменений

Lizord в 10:30, 29 ноября 2025

2025-11-29T10:30:20Z

← Предыдущая версия		Версия от 10:30, 29 ноября 2025
Строка 1:		Строка 1:
	~~{{in use\|[[Участник:Lizord\|Lizord]] ([[Обсуждение участника:Lizord\|обсуждение]])}}~~

	Основные авторы описания: [[Участник:Lizord\|Демаков М. А.]]		Основные авторы описания: [[Участник:Lizord\|Демаков М. А.]]

Lizord: /* Схема реализации последовательного алгоритма */

2025-11-29T10:23:19Z

Схема реализации последовательного алгоритма

← Предыдущая версия		Версия от 10:23, 29 ноября 2025
Строка 75:		Строка 75:

	=== Схема реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===
	Последовательной версией алгоритма Джонса-Плассмана является обычная жадная раскраска графа.		Последовательной версией алгоритма Джонса-Плассмана является обычная жадная раскраска графа. Описание её алгоритма можно получить, убрав параллельные секции из описания алгоритма Джонса-Плассмана (т.е исполняя их последовательно).

	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

Lizord: /* Результаты прогонов */

2025-11-29T10:21:53Z

Результаты прогонов

← Предыдущая версия		Версия от 10:21, 29 ноября 2025
Строка 126:		Строка 126:

	Из результатов прогонов видно, что несмотря на ожидаемый рост потенциальной производительности (скорости вычислений без учёта затрат на коммуникацию) с увеличением количества процессов, реальная производительность показывает прямо противоположную картину, с незначительным ростом производительности лишь на большом количестве процессов.		Из результатов прогонов видно, что несмотря на ожидаемый рост потенциальной производительности (скорости вычислений без учёта затрат на коммуникацию) с увеличением количества процессов, реальная производительность показывает прямо противоположную картину, с незначительным ростом производительности лишь на большом количестве процессов.

			Тесты проводились на синтетических графах с 8 миллионами вершинами и количеством ребёр равным 40, 60, 80, 100, 120, 140 и 160 миллионам.

	Производительность в данном случае измеряется в GTEPS - миллиардах обработанных ребёр в секунду. Это классическая метрика производительности для задач на графах.		Производительность в данном случае измеряется в GTEPS - миллиардах обработанных ребёр в секунду. Это классическая метрика производительности для задач на графах.

Lizord: /* Результаты прогонов */

2025-11-29T10:17:47Z

Результаты прогонов

← Предыдущая версия		Версия от 10:17, 29 ноября 2025
Строка 123:		Строка 123:

	=== Результаты прогонов ===		=== Результаты прогонов ===
			[[Файл:Результаты прогона алгоритма Джонса-Плассмана.png\|center\|800px\|Рисунок 2. Результаты прогона алгоритма Джонса-Плассмана]]

			Из результатов прогонов видно, что несмотря на ожидаемый рост потенциальной производительности (скорости вычислений без учёта затрат на коммуникацию) с увеличением количества процессов, реальная производительность показывает прямо противоположную картину, с незначительным ростом производительности лишь на большом количестве процессов.

			Производительность в данном случае измеряется в GTEPS - миллиардах обработанных ребёр в секунду. Это классическая метрика производительности для задач на графах.

	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===

Lizord: /* Ресурс параллелизма алгоритма */

2025-11-23T13:58:18Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 13:58, 23 ноября 2025
Строка 100:		Строка 100:

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
	~~Параллелизм~~ достигается за счёт выделения из множества вершин независимых подмножеств, между которыми нет ребёр. Очевидно, что вершинам из таких подмножеств можно назначить цвет независимо, т.е параллельно.		Как видно из информационного графа, параллелизм достигается за счёт выделения из множества вершин независимых подмножеств, между которыми нет ребёр. Очевидно, что вершинам из таких подмножеств можно назначить цвет независимо, т.е параллельно.

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===

Lizord в 13:45, 23 ноября 2025

2025-11-23T13:45:29Z

← Предыдущая версия		Версия от 13:45, 23 ноября 2025
Строка 129:		Строка 129:
	== Литература ==		== Литература ==
	<references />		<references />
	~~Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020~~

Lizord: Updated references

2025-11-23T13:44:50Z

Updated references

← Предыдущая версия		Версия от 13:44, 23 ноября 2025
Строка 6:		Строка 6:
	\| name = Алгоритм Джонса-Плассмана		\| name = Алгоритм Джонса-Плассмана
	\| serial_complexity = <math>O(\|V\| + \|E\|)</math>		\| serial_complexity = <math>O(\|V\| + \|E\|)</math>
	\| pf_height = <math>O(\frac{log(V)}{log log(V)})</math>		\| pf_height = <math>O(\frac{log(V)}{log log(V)})</math> <ref name="compl">Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020</ref>
	\| pf_width = <math>O(log(V))</math>		\| pf_width = <math>O(log(V))</math> <ref name="compl"></ref>
	\| input_data = <math>8\|E\|</math>		\| input_data = <math>8\|E\|</math>
	\| output_data = <math>\|V\|</math>		\| output_data = <math>\|V\|</math>

Lizord: /* Выводы для классов архитектур */

2025-11-23T13:38:11Z

Выводы для классов архитектур

← Предыдущая версия		Версия от 13:38, 23 ноября 2025
Строка 124:		Строка 124:
	=== Результаты прогонов ===		=== Результаты прогонов ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===

			Несмотря на хорошую масштабируемость в рамках одного устройства (без необходимости обмениваться данными с другими процессами), алгоритм обладает слабой масштабируемостью на кластере ввиду роста расходов на коммуникацию между независимыми потоками (после каждой итерации каждый из потоков должен синхронизировать своё состояние с остальными). Для раскраски графов на распределенных системах следует использовать специализированные алгоритмы, основанные на разбиении графа <ref>Ian Bogle and George M. Slota, Parallel Graph Coloring Algorithms for Distributed GPU Environments</ref>.

	== Литература ==		== Литература ==
	<references />		<references />
	Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020		Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020

Lizord: /* Возможные способы и особенности параллельной реализации алгоритма */

2025-11-23T13:29:43Z

Возможные способы и особенности параллельной реализации алгоритма

← Предыдущая версия		Версия от 13:29, 23 ноября 2025
Строка 119:		Строка 119:

	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===

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

	=== Результаты прогонов ===		=== Результаты прогонов ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===

Lizord: /* Особенности реализации последовательного алгоритма */

2025-11-23T13:23:17Z

Особенности реализации последовательного алгоритма

← Предыдущая версия		Версия от 13:23, 23 ноября 2025
Строка 113:		Строка 113:
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===

			Для вычисления доступного вершине цвета имеет смысл использовать битмап, где каждый установленный бит означает доступный цвет. На большинстве вычислительных архитектур получить первый установленный бит в числе можно одной аппаратной инструкцией.

			Эту же оптимизацию можно перенести и на ядра для параллельной реализации.

	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== Результаты прогонов ===		=== Результаты прогонов ===