ПРЕОБРАЗОВАНИЕ ПРОСТЕЙШИХ СОРТИРУЮЩИХ СЕТЕЙ К НЕЧЕТНО-ЧЕТНОЙ СЕТИ БАТЧЕРА

Аннотация

Все алгоритмы сортировки являются информационно-эквивалентными, поэтому выбор наи-
более эффективного алгоритма обычно зависит от скорости его работы и от количества ис-
пользуемой памяти. При параллельной, аппаратной реализации на эффективность алгоритмов
сортировки также влияют: степень утилизации аппаратных ресурсов; латентность результи-
рующей вычислительной структуры; количество и разрядность сортируемых элементов. Задача
сортировки или упорядочивания данных не формализована в виде математических преобразова-
ний, поэтому каждый из известных алгоритмов ее решения принято рассматривать как атомар-
ную, независимую единицу. Переход от одного алгоритма решения задачи к другому возможен при
описании задачи в виде информационного графа, вершины которого отражают элементарные
выполняемые операции, а дуги – информационные зависимости между ними. Имея набор элемен-
тарных преобразований, можно влиять на функциональную регулярность связей информационного
графа, латентность вычислительной структуры, коэффициент параллелизма и т.д. К преимуще-
ствам работы с информационным графом задачи также можно отнести сравнительную про-
стоту используемого понятийного аппарата. Информационный граф задачи сортировки «пузырь-
ком» представляет собой простейшую сортирующую сеть, построенную по принципу объедине-
ния ступеней «голова-хвост». В данной работе показана и обоснована функциональная избыточ-
ность подобных сортирующих сетей; приведены способы оптимизации числа операций и измене-
ния порядка их следования. Основным результатом работы является методика преобразования
сортирующих сетей в нечетно-четную сеть слияния Батчера. Разработана программа, автома-
тически выполняющая преобразование сортирующих сетей и позволяющая подстраивать тополо-
гию информационного графа под наиболее эффективный вид в зависимости от результирующей
степени параллелизма вычислительной структуры. Обобщая полученные результаты, можно
отметить, что автоматизированное приведение известных алгоритмов к «быстрым» может
обеспечить получение оптимальной параллельно-конвейерной программы при заданных ограниче-
ниях, что позволит значительно ускорить процесс их разработки.