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