ПРЕОБРАЗОВАНИЕ СОРТИРУЮЩИХ СЕТЕЙ ДЛЯ РАЗНОЙ СТЕПЕНИ ПАРАЛЛЕЛИЗМА

Аннотация

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