Участница:Полина Кривуля/Сеть битонной сортировки - История изменений

Полина Кривуля: /* Информационный граф */

2023-12-05T08:37:24Z

Информационный граф

← Предыдущая версия		Версия от 08:37, 5 декабря 2023
Строка 56:		Строка 56:
	На рисунке 1 изображена работа битонной сортировки. Красные элементы соответствуют возрастающей последовательности, зеленые – убывающей. Операции min и max соответствуют операциям сравнения двух чисел и, при необходимости, обмену местами двух чисел. Можно заметить, что работу алгоритма можно представить в виде выполнения двух шагов: создание битонных последовательностей и их слияние.		На рисунке 1 изображена работа битонной сортировки. Красные элементы соответствуют возрастающей последовательности, зеленые – убывающей. Операции min и max соответствуют операциям сравнения двух чисел и, при необходимости, обмену местами двух чисел. Можно заметить, что работу алгоритма можно представить в виде выполнения двух шагов: создание битонных последовательностей и их слияние.

	[[Файл:BitonicSort1.svg\|~~500px~~\|thumb\|center\|рис.2: Битонная сортировка для 16 элементов]]		[[Файл:BitonicSort1.svg\|700px\|thumb\|center\|рис.2: Битонная сортировка для 16 элементов]]

	На рисунке 2 изображена битонная сортировочная сеть для 16 элементов, которая сортирует множество по возрастанию. Красные прямоугольники скомбинированы в зеленые и голубые прямоугольники. В синих прямоугольниках стрелки компараторов направлены вниз (создают возрастающие последовательности), в зеленых — вверх (создают убывающие последовательности). Каждый из таких прямоугольников имеет одинаковую структуру: красный прямоугольник применяется ко всей последовательности, затем к каждой половине полученных результатов и так далее. Если на входы такого прямоугольника подается битонная последовательность, то на выходе она преобразуется в полностью отсортированную. Объединенные результаты синего и зеленого прямоугольника является битонной последовательностью.		На рисунке 2 изображена битонная сортировочная сеть для 16 элементов, которая сортирует множество по возрастанию. Красные прямоугольники скомбинированы в зеленые и голубые прямоугольники. В синих прямоугольниках стрелки компараторов направлены вниз (создают возрастающие последовательности), в зеленых — вверх (создают убывающие последовательности). Каждый из таких прямоугольников имеет одинаковую структуру: красный прямоугольник применяется ко всей последовательности, затем к каждой половине полученных результатов и так далее. Если на входы такого прямоугольника подается битонная последовательность, то на выходе она преобразуется в полностью отсортированную. Объединенные результаты синего и зеленого прямоугольника является битонной последовательностью.

Полина Кривуля: /* Ресурс параллелизма алгоритма */

2023-12-05T08:36:54Z

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

← Предыдущая версия		Версия от 08:36, 5 декабря 2023
Строка 62:		Строка 62:

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
	~~[[Файл:Bitonic sort.svg\|обрамить\|рис.3: Битонная сортировочная сеть]]~~
	Алгоритм дает большой выигрыш при использовании параллелизма. В общем случае можно распараллелить данный алгоритм на любое число процессов являющееся степенью числа 2. Однако следует учитывать накладные расходы на создание MPI процессов и обмен сообщениями между ними. Если их будет достаточно много для сравнительно небольшой длины массива, то выигрыш в производительности будет очень маленьким, либо может отсутствовать вовсе.		Алгоритм дает большой выигрыш при использовании параллелизма. В общем случае можно распараллелить данный алгоритм на любое число процессов являющееся степенью числа 2. Однако следует учитывать накладные расходы на создание MPI процессов и обмен сообщениями между ними. Если их будет достаточно много для сравнительно небольшой длины массива, то выигрыш в производительности будет очень маленьким, либо может отсутствовать вовсе.
	На ~~диаграмме~~ 3 каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.
			[[Файл:Bitonic sort.svg\|thumb\|center\|700px\|рис.3: Битонная сортировочная сеть]]

			На рисунке 3 каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

	При последовательной реализации каждый шаг рекурсии занимает <math>O(nlog(n))</math> времени, а всего шагов рекурсии <math>log(n)</math>.		При последовательной реализации каждый шаг рекурсии занимает <math>O(nlog(n))</math> времени, а всего шагов рекурсии <math>log(n)</math>.

Полина Кривуля: /* Информационный граф */

2023-12-05T08:35:08Z

Информационный граф

← Предыдущая версия		Версия от 08:35, 5 декабря 2023
Строка 52:		Строка 52:

	=== Информационный граф ===		=== Информационный граф ===
	[[Файл:Graph bitonic.png\|~~мини~~\|рис.1: Информационный граф битонной сортировки]]		[[Файл:Graph bitonic.png\|500px\|thumb\|center\|рис.1: Информационный граф битонной сортировки]]

	На рисунке 1 изображена работа битонной сортировки. Красные элементы соответствуют возрастающей последовательности, зеленые – убывающей. Операции min и max соответствуют операциям сравнения двух чисел и, при необходимости, обмену местами двух чисел. Можно заметить, что работу алгоритма можно представить в виде выполнения двух шагов: создание битонных последовательностей и их слияние.		На рисунке 1 изображена работа битонной сортировки. Красные элементы соответствуют возрастающей последовательности, зеленые – убывающей. Операции min и max соответствуют операциям сравнения двух чисел и, при необходимости, обмену местами двух чисел. Можно заметить, что работу алгоритма можно представить в виде выполнения двух шагов: создание битонных последовательностей и их слияние.

	[[Файл:BitonicSort1.svg\|~~без~~\|рис.2: Битонная сортировка для 16 элементов]]		[[Файл:BitonicSort1.svg\|500px\|thumb\|center\|рис.2: Битонная сортировка для 16 элементов]]

	На рисунке 2 изображена битонная сортировочная сеть для 16 элементов, которая сортирует множество по возрастанию. Красные прямоугольники скомбинированы в зеленые и голубые прямоугольники. В синих прямоугольниках стрелки компараторов направлены вниз (создают возрастающие последовательности), в зеленых — вверх (создают убывающие последовательности). Каждый из таких прямоугольников имеет одинаковую структуру: красный прямоугольник применяется ко всей последовательности, затем к каждой половине полученных результатов и так далее. Если на входы такого прямоугольника подается битонная последовательность, то на выходе она преобразуется в полностью отсортированную. Объединенные результаты синего и зеленого прямоугольника является битонной последовательностью.		На рисунке 2 изображена битонная сортировочная сеть для 16 элементов, которая сортирует множество по возрастанию. Красные прямоугольники скомбинированы в зеленые и голубые прямоугольники. В синих прямоугольниках стрелки компараторов направлены вниз (создают возрастающие последовательности), в зеленых — вверх (создают убывающие последовательности). Каждый из таких прямоугольников имеет одинаковую структуру: красный прямоугольник применяется ко всей последовательности, затем к каждой половине полученных результатов и так далее. Если на входы такого прямоугольника подается битонная последовательность, то на выходе она преобразуется в полностью отсортированную. Объединенные результаты синего и зеленого прямоугольника является битонной последовательностью.

Полина Кривуля: /* Информационный граф */

2023-12-04T18:31:58Z

Информационный граф

← Предыдущая версия		Версия от 18:31, 4 декабря 2023
Строка 56:		Строка 56:
	На рисунке 1 изображена работа битонной сортировки. Красные элементы соответствуют возрастающей последовательности, зеленые – убывающей. Операции min и max соответствуют операциям сравнения двух чисел и, при необходимости, обмену местами двух чисел. Можно заметить, что работу алгоритма можно представить в виде выполнения двух шагов: создание битонных последовательностей и их слияние.		На рисунке 1 изображена работа битонной сортировки. Красные элементы соответствуют возрастающей последовательности, зеленые – убывающей. Операции min и max соответствуют операциям сравнения двух чисел и, при необходимости, обмену местами двух чисел. Можно заметить, что работу алгоритма можно представить в виде выполнения двух шагов: создание битонных последовательностей и их слияние.

	[[Файл:BitonicSort1.svg\|~~мини~~\|рис.2: Битонная сортировка для 16 элементов]]		[[Файл:BitonicSort1.svg\|без\|рис.2: Битонная сортировка для 16 элементов]]

	На рисунке 2 изображена битонная сортировочная сеть для 16 элементов, которая сортирует множество по возрастанию. Красные прямоугольники скомбинированы в зеленые и голубые прямоугольники. В синих прямоугольниках стрелки компараторов направлены вниз (создают возрастающие последовательности), в зеленых — вверх (создают убывающие последовательности). Каждый из таких прямоугольников имеет одинаковую структуру: красный прямоугольник применяется ко всей последовательности, затем к каждой половине полученных результатов и так далее. Если на входы такого прямоугольника подается битонная последовательность, то на выходе она преобразуется в полностью отсортированную. Объединенные результаты синего и зеленого прямоугольника является битонной последовательностью.		На рисунке 2 изображена битонная сортировочная сеть для 16 элементов, которая сортирует множество по возрастанию. Красные прямоугольники скомбинированы в зеленые и голубые прямоугольники. В синих прямоугольниках стрелки компараторов направлены вниз (создают возрастающие последовательности), в зеленых — вверх (создают убывающие последовательности). Каждый из таких прямоугольников имеет одинаковую структуру: красный прямоугольник применяется ко всей последовательности, затем к каждой половине полученных результатов и так далее. Если на входы такого прямоугольника подается битонная последовательность, то на выходе она преобразуется в полностью отсортированную. Объединенные результаты синего и зеленого прямоугольника является битонной последовательностью.

Полина Кривуля: /* Ресурс параллелизма алгоритма */

2023-12-04T18:30:27Z

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

← Предыдущая версия		Версия от 18:30, 4 декабря 2023
Строка 62:		Строка 62:

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
	[[Файл:Bitonic sort.svg\|обрамить\|Битонная сортировочная сеть]]		[[Файл:Bitonic sort.svg\|обрамить\|рис.3: Битонная сортировочная сеть]]
	Алгоритм дает большой выигрыш при использовании параллелизма. В общем случае можно распараллелить данный алгоритм на любое число процессов являющееся степенью числа 2. Однако следует учитывать накладные расходы на создание MPI процессов и обмен сообщениями между ними. Если их будет достаточно много для сравнительно небольшой длины массива, то выигрыш в производительности будет очень маленьким, либо может отсутствовать вовсе.		Алгоритм дает большой выигрыш при использовании параллелизма. В общем случае можно распараллелить данный алгоритм на любое число процессов являющееся степенью числа 2. Однако следует учитывать накладные расходы на создание MPI процессов и обмен сообщениями между ними. Если их будет достаточно много для сравнительно небольшой длины массива, то выигрыш в производительности будет очень маленьким, либо может отсутствовать вовсе.
	На диаграмме каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.		На диаграмме 3 каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

	При последовательной реализации каждый шаг рекурсии занимает <math>O(nlog(n))</math> времени, а всего шагов рекурсии <math>log(n)</math>.		При последовательной реализации каждый шаг рекурсии занимает <math>O(nlog(n))</math> времени, а всего шагов рекурсии <math>log(n)</math>.

Полина Кривуля: /* Информационный граф */

2023-12-04T18:29:50Z

Информационный граф

← Предыдущая версия		Версия от 18:29, 4 декабря 2023
Строка 52:		Строка 52:

	=== Информационный граф ===		=== Информационный граф ===
	[[Файл:Graph bitonic.png\|мини\|Информационный граф битонной сортировки]]		[[Файл:Graph bitonic.png\|мини\|рис.1: Информационный граф битонной сортировки]]

	На рисунке изображена работа битонной сортировки. Красные элементы соответствуют возрастающей последовательности, зеленые – убывающей. Операции min и max соответствуют операциям сравнения двух чисел и, при необходимости, обмену местами двух чисел. Можно заметить, что работу алгоритма можно представить в виде выполнения двух шагов: создание битонных последовательностей и их слияние.		На рисунке 1 изображена работа битонной сортировки. Красные элементы соответствуют возрастающей последовательности, зеленые – убывающей. Операции min и max соответствуют операциям сравнения двух чисел и, при необходимости, обмену местами двух чисел. Можно заметить, что работу алгоритма можно представить в виде выполнения двух шагов: создание битонных последовательностей и их слияние.

			[[Файл:BitonicSort1.svg\|мини\|рис.2: Битонная сортировка для 16 элементов]]

			На рисунке 2 изображена битонная сортировочная сеть для 16 элементов, которая сортирует множество по возрастанию. Красные прямоугольники скомбинированы в зеленые и голубые прямоугольники. В синих прямоугольниках стрелки компараторов направлены вниз (создают возрастающие последовательности), в зеленых — вверх (создают убывающие последовательности). Каждый из таких прямоугольников имеет одинаковую структуру: красный прямоугольник применяется ко всей последовательности, затем к каждой половине полученных результатов и так далее. Если на входы такого прямоугольника подается битонная последовательность, то на выходе она преобразуется в полностью отсортированную. Объединенные результаты синего и зеленого прямоугольника является битонной последовательностью.
			Каждый столбец синих и зеленых прямоугольников принимает N отсортированных последовательностей (на самом первом шаге 16 отсортированных последовательностей, состоящих из 1 элемента) и преобразует их в N/2 отсортированных последовательностей. <ref> Википедия: [https://ru.wikipedia.org/wiki/Битонная_сортировка#:~:text=Битонная%20сортировка%20(англ.,лежит%20понятие%20«битонной%20последовательности». Битонная сортировка] </ref>.

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

Полина Кривуля: /* Свойства и структура алгоритмов */

2023-12-04T18:20:51Z

Свойства и структура алгоритмов

← Предыдущая версия		Версия от 18:20, 4 декабря 2023
Строка 52:		Строка 52:

	=== Информационный граф ===		=== Информационный граф ===
	[[Файл:~~Bitonic sort~~.~~svg~~\|~~обрамить~~\|Информационный граф битонной сортировки]]		[[Файл:Graph bitonic.png\|мини\|Информационный граф битонной сортировки]]

	~~Диаграмма~~ сортировки ~~для 16 сортируемых элементов~~.		На рисунке изображена работа битонной сортировки. Красные элементы соответствуют возрастающей последовательности, зеленые – убывающей. Операции min и max соответствуют операциям сравнения двух чисел и, при необходимости, обмену местами двух чисел. Можно заметить, что работу алгоритма можно представить в виде выполнения двух шагов: создание битонных последовательностей и их слияние.
	~~Горизонтальные линии представляют индексы массива в нашем массиве сортируемых элементов~~, ~~каждая вертикальная линия представляет один рабочий поток, выполняющий операцию~~ сравнения и ~~замены.~~

	На диаграмме каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, ~~находящиеся в одном столбце~~, ~~образуют шаг, который можно выполнять параллельно~~. ~~Из диаграммы видно~~, что ~~количество потоков на шаг постоянно~~ и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
			[[Файл:Bitonic sort.svg\|обрамить\|Битонная сортировочная сеть]]
	Алгоритм дает большой выигрыш при использовании параллелизма. В общем случае можно распараллелить данный алгоритм на любое число процессов являющееся степенью числа 2. Однако следует учитывать накладные расходы на создание MPI процессов и обмен сообщениями между ними. Если их будет достаточно много для сравнительно небольшой длины массива, то выигрыш в производительности будет очень маленьким, либо может отсутствовать вовсе.		Алгоритм дает большой выигрыш при использовании параллелизма. В общем случае можно распараллелить данный алгоритм на любое число процессов являющееся степенью числа 2. Однако следует учитывать накладные расходы на создание MPI процессов и обмен сообщениями между ними. Если их будет достаточно много для сравнительно небольшой длины массива, то выигрыш в производительности будет очень маленьким, либо может отсутствовать вовсе.
			На диаграмме каждый рабочий поток нарисован в виде вертикальной линии, начальная и конечная точки обозначают индексы текущей пары сортируемых элементов. Все цветные блоки, находящиеся в одном столбце, образуют шаг, который можно выполнять параллельно. Из диаграммы видно, что количество потоков на шаг постоянно и всегда равно <math> n/2</math>, где <math> n</math> — количество сортируемых элементов <ref> Ponies&Light: [https://poniesandlight.co.uk/reflect/bitonic_merge_sort/. Implementing Bitonic Merge Sort in Vulkan Compute] </ref>.

	При последовательной реализации каждый шаг рекурсии занимает <math>O(nlog(n))</math> времени, а всего шагов рекурсии <math>log(n)</math>.		При последовательной реализации каждый шаг рекурсии занимает <math>O(nlog(n))</math> времени, а всего шагов рекурсии <math>log(n)</math>.

Полина Кривуля: /* Свойства и структура алгоритмов */

2023-12-04T17:06:12Z

Свойства и структура алгоритмов

← Предыдущая версия		Версия от 17:06, 4 декабря 2023
Строка 1:		Строка 1:
			Автор: Полина Кривуля

	== Свойства и структура алгоритмов ==		== Свойства и структура алгоритмов ==

Полина Кривуля: /* Существующие реализации алгоритма */

2023-12-03T15:51:07Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 15:51, 3 декабря 2023
Строка 108:		Строка 108:

	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===
	[https://www.geeksforgeeks.org/bitonic-sort/ ~~Реализация битонной сортировки от~~ GeeksforGeeks]		Наиболее используемый "классический" вариант битонной сортировки предложен [https://www.geeksforgeeks.org/bitonic-sort/ GeeksforGeeks]. Здесь его реализации предложены на языках C++, Java, Python3, C#, Javascript. Время работы составляет [math] O(log^2n) [/math], объем занимаемой памяти [math] O(nlogn) [/math]. Авторы отмечают, что у алгоритма число сравнений больше, чем у других сортировок.

	[https://people.cs.rutgers.edu/~venugopa/parallel_summer2012/bitonic_openmp.html ~~Реализация битонной сортировки, найденная на сайте~~ Parallel Computing]		Также реализация битонной сортировки предложена на сайте [https://people.cs.rutgers.edu/~venugopa/parallel_summer2012/bitonic_openmp.html Parallel Computing]. Здесь данная сортировка реализована в трех вариантах с использованием технологий MPI, OpenMP и Cuda.

	[https://www.sortvisualizer.com/bitonicsort/ Реализация битонной сортировки с красивым интерфейсом сайта, где можно наглядно увидеть как работает последовательный алгоритм сортировки]		В статье [https://ieeexplore.ieee.org/document/16506 K-Way Bitonic Sort] предложена модификация битонной сортировки, позволяющая более эффективно сортировать последовательности произвольной размерности.

			На сайте [https://www.sortvisualizer.com/bitonicsort/ Sort Visualizer] предложена визуализация работы алгоритма.

	== Литература ==		== Литература ==

Полина Кривуля: /* Свойства алгоритма */

2023-12-03T12:22:54Z

Свойства алгоритма

← Предыдущая версия		Версия от 12:22, 3 декабря 2023
Строка 84:		Строка 84:

	Недостатки:		Недостатки:
	* Количество сравнений в алгоритме ~~бетонной~~ сортировки обычно больше, чем в других более популярных алгоритмах сортировки		* Количество сравнений в алгоритме битонной сортировки обычно больше, чем в других более популярных алгоритмах сортировки

	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==