2. Михаль О.Ф. Моделирование распределенных информационно-управляющих систем средствами локально-параллельных
алгоритмов обработки нечеткой информации / / Проблемы бионики. Всеукраинский межведомственный научно-технический сборник. Харьков: ХНУРЭ. 2001. Вып. 54. С. 28-34.
- 864 с.
-□ □Процедуру сортування проаналiзовано на KOM6i-наторному piem для 4-елементних послидовностей. Подано алгоpитмiчне забезпечення локально-пара-лельного сортування. В ходi моделювання мовою Python з&ясовано, що локально-паралельний алгоритм максимально эфективний щодо сортування виборок в межах pозpядностi процесора
Ключовi слова: локальна паралельтсть, сортування даних
Процедура сортировки проанализирована на комбинаторном уровне на примере 4-элементных числовых последовательностей. Описана работа алгоритма локально-параллельной сортировки. Моделированием на языке Python показано, что алгоритм эффективен применительно к малым выборкам
сортировка данных
The Procedures of the sorting is analysed on combinatorial level for 4-element sequences. Algorithmic provision of local-parallel sorting is presented. In the course of modeling in language Python is revealled that local-parallel algorithm is greatly efficient with reference to sorting the samples within processor register size
ЛОКАЛЬНО-ПАРАЛЛЕЛЬНАЯ СОРТИРОВКА МАЛЫХ НАБОРОВ ДАННЫХ
Мохамад Али
Аспирант*
О.Ф. М ихал ь
Доктор технических наук, доцент, профессор*
*Кафедра Электронно-вычислительных
машин
Харьковский национальный университет радиоэлектроники пр. Ленина, 14, г. Харьков, 61166 Контактный тел. (057) 40-93-54 Е-mail: fuzzy16@pisem.net
Сортировка данных - классическая задача, сочетающая в себе прозрачность общей концепции и многовариантность решений. Алгоритмы сортировки подробно изучены для вычислительных систем (ВС) последовательного действия. Параллельные ВС до недавнего времени были исключительно многопроцессорными и разрабатывались для специальных приложений. Задачи параллельной сортировки рассматривалась в них преимущественно в контексте общих принципов распараллеливания алгоритмов. С распространением многоядерных процессоров и сетевых вычислительных структур [1]: приобрела актуальность сортировка ограниченных малых наборов данных [2, 3]. Эта задача эффективно решается с использованием, локально-параллельных (ЛП) алгоритмов обработки информации [4, 5].
В настоящей работе развиваются рассмотренные ранее [1-3] принципы сортировки на ЛП алгоритмах, проводится детальное сравнение с последовательными алгоритмическими процедурами и формулируются направления использования выявленных закономерностей в прикладных задачах.
Будем рассматривать набор данных А - множество, состоящее из элементов: А: {а1,а2,а3,...,а!,...,ап}, где а1 еА; 1 е(1,2,...,п) , - объект произвольной природы: число, фрагмент текста, запись в БД и др. Элементы множества А могут быть самими объектами набора данных, либо указателями на них, позволяющими взаимно-однозначно соотносить а1 еА и соответствующий объект. Термин «ограниченный» предполагает конечное число п элементов, неизменное в
процессе сортировки; термин «малый» - количество элементов при котором не требуется использование видов (типов) памяти, существенно замедляющих информационный обмен в процессе выполнения сортировки.
Отношение порядка (наличие упорядоченности) на множестве А предполагает указание для некоторых элементов а^ еА; 1,] е(1,2,3,...,п) ; 1 ф одного из следующих соотношений: а! а], а! >■ а]. Символы « » и « >■ » есть отношения следования: «предшествует» и «следует за». В частности они могут интерпретироваться как арифметические соотношения между числами - бинарные отношения «меньше» (<) и «больше» (>). Множество А является упорядоченным, если отношение порядка определено для любых а1,а] еА. Множество А является частично упорядоченным, если отношение порядка определено для некоторых пар а^ еА.
Будем различать множество А , как совокупность элементов, и последовательность элементов множества, как выборку элементов множества с учётом порядка размещения. Для последовательности, включающей все элементы А , допустимо упорядочение по возрастанию а1 < а2 < а3 <... < а! <... < ап, либо по убыванию а1 > а2 > а3 >... > а! >... > ап. При этом для любой пары элементов справедливо а! < а] ( а! > а]), где 1,] е(1,2,3,...,п) , 1 < Если хотя бы для одной пары условие а! < а] ( а! > а]) не выполняется, последовательность является не упорядоченной по возрастанию (убыванию). Процесс упорядочения - переход от одной расстановки к другой иллюстрируется графом рис. 1 для множества из четырёх элементов.
ТТЭТ
ащнзщкш:
&2341 к
X 3241 >
& 3214 У
У 2431 > а 3421;
,2413 К Л •*•
У 4213> Н 4231 &
&3142&к I ......
К 3412 V —14312 &
X 4132 У
Рис. 1. Структуры частично упорядоченных множеств перестановок четырёхэлементной последовательности
Вводится мера разупорядоченности, как число перестановок соседних элементов, которое необходимо произвести чтобы прийти к упорядоченной последовательности элементов. Может быть показано, что множества, упорядоченные по возрастанию и убыванию максимально взаимно разупорядочены. Для данного множества число перестановок в парах соседствующих элементов является максимальным при переупорядочении множества из упорядоченности по возрастанию в упорядоченность по убыванию.
При рассмотрении цепочек перестановок необходимо исключить циклы, ограничившись только продуктивными перестановками. Графы рис. 1 а, б позволяют проследить различные варианты таких цепочек, поскольку охватывают все возможные варианты связей по перестановкам в парах соседствующих элементов. Так, для 4-элементной последовательности (рис. 1 б) одна из цепочек преобразования (1,2,3,4)^(4,3,2,1) имеет вид:
(1,2,3,4) ^ (2,1,3,4) ^ (2,1,4,3) ^ ^ (274,1,3) ^ (4,2,173) ^ (4,273,1) ^ (4,3,2,1)
Две соседние последовательности, разделённые знаком «^ », различаются перестановкой местами одной (обозначенной « 7 ») пары двух соседних элементов (цифр). Процедура сортировки - последовательная, поэтому соседствующие пары переставляются по одной. В результате, (1,2,3,4)^(4,3,2,1) реализуется за 6 шагов.
В отличие от последовательной процедуры сортировки, ЛП процедура поддерживает обмен местами сразу нескольких (всех имеющихся) пар соседствующих элементов последовательности. Вследствие этого число переходов « ^ » может быть существенно сокращено.
Принцип ЛП обработки информации, может быть проиллюстрирован вычислительным примером. Имеется п выражений с = а! + Ь ; 1 = 1,2,...,п . Значения а! и Ь заданы, требуется найти с . В последовательном варианте задача разрешима за 4п шагов: загрузить а! , загрузить Ь , произвести суммирование, выгрузить результат с . Если а! , Ь и с положительные и имеют ограниченную разрядность, исходные данные могут быть конкатенированы: А = а1 © а2 ©... © а! ©... Ф ап ; В = Ь1 © Ь2 ©... © Ь ©... © Ьп .
Результат С = А + В так же может быть интерпретирован как конкатенация. При этом весь набор значений с может быть получен за 4 шага. п-крат-ный выигрыш достигнут без учёта «окаймляющих» операций конкатенации и деконкатенации. Если в реальном случае вычислительный блок сложный и включает последовательное применение нескольких операций без промежуточных конкатенаций-декон-катенаций, - выигрыш может быть значительным. Выигрыш растёт с ростом разрядности процессора и с сокращением размеров конкатенируемых сегментов. При этом снижается точность представления данных (система «загрубляется»), что в ряде конкретных приложений бывает допустимо.
Проиллюстрируем работу алгоритма ЛП сортировки. Имеется множество элементов А: {а1,а2,...,ап}, на котором определено отношение порядка а1 > а2 >... > ап. Из элементов множества А составлена разупорядо-ченная последовательность В:{Ьп,Ьп-1,...,Ь2,Ь1}; Ь = а]; 1,] е(1,2,3,...,п); 1 ф
Максимально разупорядоченный случай соответствует обратной упорядоченности: В: {ап,ап-1,...,а2,а1}. Требуется привести последовательность к правильной исходной упорядоченности: В ^ А .
Производим конкатенацию элементов Ь согласно их расположению в последовательности. В вербальном описании ЛП процедура сортировки включает 4 шага.
Шаг 1. Скопировать текущее В для последующего сравнения: В1 = В.
Шаг 2. Сравнить попарно нечётные элементы В с чётными, стоящими слева от них. В каждой сравниваемой паре больший из элементов поставить на нечётное место, а меньший - на чётное.
Шаг 3. Сравнить попарно чётные элементы В с нечётными, стоящими слева от них. В каждой сравниваемой паре больший из элементов поставить на чётное место, а меньший - на нечётное.
Шаг 4. Сравнить В и В1. Если В1 = В, ЛП процедура сортировки закончена. Результат содержится в В . Если В1 Ф В - перейти к Шагу.1.
Основные черты ЛП сортировки могут быть прослежены на примере.
циклов сортировки не меняется и результат - нижняя строка - одинаков. Пример соответствует графу рис. 1. ЛП алгоритм преобразования (1,2,3,4)^(4,3,2,1) в варианте, обозначенном (а), соответствует вершинам графа, выделенным жирным пунктиров; в варианте, обозначенном (б), - вершинам, выделенным мелким пунктиров. Сопоставление с графом рис. 1 показывает сокращение числа проходимых вершин, за счёт чего достигается выигрыш в производительности ЛП сортировки по сравнению с традиционной последовательной.
(а) (б)
(4,3,2,1) (4,3,2,1)
В столбце, обозначенном (а), представлены 4 последовательных цикла ЛП сортировки начиная со строки обменов «чётный-нечётный»; в столбце (б) -начиная со строки обменов «нечётный-чётный». При изменении порядка чередования обменов общее число
Выводы
Локально-параллельное представление информации обеспечивает повышенную эффективность работы программного обеспечения. Принципы локально-параллельной обработки применимы к задачам сортировки наборов данных. Процедуры сортировки рассмотрены на комбинаторном уровне для 4-элементных последовательностей. Разработано алгоритмическое обеспечение локально-параллельной сортировки. В ходе моделирования, проведенного на языке Python, выявлено, что локально-параллельный алгоритм максимально эффективен применительно к сортировке малых (в пределах разрядности процессора) выборок.
Радиоэлектронные и компьютерные системы. - 2008. - № 6 (33). - с. 234-237.
"Проблемы бионики", Вып. 55, Харьков, 2001, с. 80-90.
алгоритмах // Управляющие системы и машины. 2001. № 3. с. 3-10.