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

Аннотация

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