Сеть сортировки Bitonic с использованием параллельных вычислений

Что такое сети сортировки в параллельных вычислениях?

Сортировочные сети — это сети сравнения, которые всегда сортируют свои входные данные. Они также известны как сети сравнения. Сети сравнения состоят из проводов и компараторов. Провода отвечают за передачу значения от одного узла к другому, а компаратор отвечает за сравнение двух входов для получения двух выходов.

Базовая блок-схема компаратора показана ниже:

На приведенной выше диаграмме:

• x и y являются входными данными
• x' и y' являются выходами
• х' = мин (х, у)
• у' = макс (х, у)

В сортировочной сети выходная последовательность монотонно возрастает. Сеть сравнения похожа на процедуру, которая определяет, как происходит сравнение.

Глубина сортировочной сети – это минимальное количество компараторов на пути от входных проводов к выходному проводу.

Сортировочная сеть Bitonic

Это особый тип сортировочной сети. Он состоит из битонического сортировщика и битонической последовательности. Давайте посмотрим, что такое битонический сортировщик и битонная последовательность.

Bitonic Sorter — Bitonic Sorter состоит из нескольких этапов, каждый из которых называется полуочистителем. Полуочиститель — это сеть сравнения глубины 1. Битонический сортировщик получается путем рекурсивного объединения полуочистителей, в котором строка i сравнивается со строкой (i + n/2) для всех i в диапазоне [1, n/2] .

Bitonic Sequence — битоническая последовательность представляет собой последовательность битов, т. е. 0 и 1. Это последовательность, которая монотонно возрастает, а затем монотонно убывает или может быть циклически сдвинута, чтобы стать монотонно возрастающей, а затем монотонно убывающей.

Как работает сортировочная сеть bitonic?

Когда битоническая последовательность 0 и 1 применяется в качестве входных данных для полуочистителя в битонической сети, полуочиститель создает выходную последовательность, в которой меньшие значения находятся в верхней половине, а большие значения — в нижней половине, и обе половины битонический. Работу битонической сортировочной сети можно увидеть на примере.

Пример:

Учитывая последовательность {0, 0, 1, 1, 1, 0, 0, 0}, что будет на выходе, когда она будет передана через битоническую сортировочную сеть?

Решение:

В данном примере ввод делится на две половины, и входы каждой половины сравниваются по порядку и рекурсивно, пока ввод не будет полностью отсортирован. Сравнения происходят для log ₂ x, где x — количество входных данных.

Свойства выхода битонической сортировочной сети:

• И верхняя и нижняя половина чистые.
• Каждый элемент в верхней половине по крайней мере так же мал, как и каждый элемент в нижней половине.
• По крайней мере, одна половина чистая (либо все 0, либо все 1).